## Events Search and Views Navigation

## June 2019

### Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube

Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them "stability" results for maximal independent set counts and old…

Find out more »### Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues

An odd $$-factor of a graph is a spanning subgraph $H$ such that for every vertex $v \in V(G)$, $1 \le d_H(v) \le b$, and $d_H(v)$ is odd. For positive integers $r \ge 3$ and $b \le r$, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of vertices to guarantee the existence of an odd -factor. In this talk, we improve their bound.

Find out more »### Patrice Ossona de Mendez, A model theoretical approach to sparsity

We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.

Find out more »## July 2019

### 2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures

An invitation-only summer research program will be held in the summer of 2019. There will be 10-20 participants to work together at DIMAG. More details will be posted later. Registered Participants Nick Brettell (Eindhoven University of Technology) Yixin Cao (Hong Kong Polytechnic University) Archontia Giannopoulou (National and Kapodistrian University of Athens) Mamadou M. Kante (University Clermont Auvergne) Michael Dobbins (Binghamton University) Pierre Aboulker (ENS) Benjamin Bergougnoux (University of Paris Diderot) Michael Lampis (Université Paris-Dauphine) Valia Mitsou (Université Paris-Diderot) Stefan Kratsch (Humboldt-Universität zu…

Find out more »## August 2019

### 2019 Combinatorics Workshop

The annual conference on Combinatorics Workshop (조합론 학술대회) began in 2004 by the Yonsei University BK21 Research Group. This year it will take place in Songdo, Incheon, August 13-15, 2019. Due to the capacity (50 persons) of the place, we are able to limit your registration. In principle, registration is on a first-come, first-served basis. Title 2019 Combinatorics Workshop (2019 조합론 학술대회) Date August 13-15 (Tue-Thu), 2019 Venue Hotel Skypark, Songdo, Incheon Web https://cw2019.combinatorics.kr We are going to give six…

Find out more »