CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Extremal combinatorics
Responsable et président: Deryk Osthus (University of Birmingham)

Comparable pairs in families of sets  [PDF]

We consider a problem posed by Erd\H{o}s and Daykin and Frankl in the early '80s. They asked for the maximum number of comparable pairs ($A\subseteq B$ or $B \subseteq A$) that can appear in a family of $m$ subsets of $[n]$, a quantity we denote by $c(n,m)$. We first resolve an old conjecture of Alon and Frankl, showing that $c(n,m)=o(m^2)$ when $m=n^{\omega(1)}2^{n/2}$. We also obtain more accurate bounds for $c(n,m)$ for sparse and dense families, characterize the extremal constructions for certain values of $m$, and sharpen some other known results.

Joint work with Noga Alon, Shagnik Das, and Benny Sudakov.

DERYK OSTHUS, University of Birmingham
On the typical structure of triangle-free oriented graphs and digraphs  [PDF]

There has been a huge body of work on the typical structure of H-free graphs, starting with a result of Erdos, Kleitman and Rothschild, who settled the case when H is a triangle. However, much less is known for oriented or directed graphs.

Motivated by his work on the classification of countable homogeneous oriented graphs, Cherlin asked about the typical structure of oriented graphs without (i) transitive triangles or (ii) oriented triangles. We give an answer to these questions (which is not quite the predicted one). Numerous open problems remain.

Joint work with Daniela K\"uhn, Timothy Townsend and Yi Zhao

Decomposition of bounded degree graphs into $C_4$-free subgraphs  [PDF]

We prove that every graph with maximum degree $\Delta$ admits a partition of its edges into $O(\sqrt{\Delta})$ parts (as $\Delta\to\infty$) none of which contains $C_4$ as a subgraph. The bound is sharp up to a constant factor and settles a conjecture of Jiang, Milans and West. This is a joint work with Ross Kang.

YURY PERSON, Goethe University Frankfurt
Minimum degrees of minimal Ramsey graphs and hypergraphs  [PDF]

A (uniform hyper-)graph $G$ is called $H$-Ramsey if no matter how one colors its edges red/blue, there is a monochromatic copy of $H$. We say that $G$ is minimal $H$-Ramsey if $G$ is $H$-Ramsey, but no proper subgraph of it is. Burr, Erd\H{o}s and Lovász studied the smallest minimum degree among all minimal $K_t$-Ramsey graphs and showed that it equals $(t-1)^2$. I discuss generalizations of their result to more colors and to hypergraphs.

Joint work with Dennis Clemens, Jacob Fox, Andrey Grinshpun, Anita Liebenau and Tibor Szabó.

DIANA PIGUET, Czech Academy of Sciences
The Loebl-Komlós-Sós Conjecture  [PDF]

The Loebl-Komlós-Sós Conjecture relates the median degree of a graph with the containment of any tree of a fixed size. Szemerédi's Regularity Lemma was used to prove this conjecture for dense graphs, but is void for sparse ones. We shall briefly introduce novel techniques that allow to prove an approximate version of this conjecture in the sparse setting. This is a joint work with Hladký, Komlós, Simonovits, Stein, and Szemerédi.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan