CanaDAM 2021
En ligne, 25 - 28 mai 2021

Extremal problems for hypergraphs
Org: Frederik Garbe (Masaryk University)

The intersection spectrum of 3-chromatic intersecting hypergraphs  [PDF]

The intersection spectrum of a hypergraph is the set of all intersection sizes of pairs of edges. In their seminal paper from 1973 which introduced the local lemma, Erd\H{o}s and Lov\'asz asked: how large must the intersection spectrum of a $k$-uniform $3$-chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with $k$. We prove this conjecture in a strong form, by showing that there are at least $k^{1/2-o(1)}$ intersection sizes. Joint work with Matija Buci\'c and Benny Sudakov

TOM KELLY, University of Birmingham
A proof of the Erdős–Faber–Lovász conjecture  [PDF]

The Erdős-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. We prove this conjecture for sufficiently large n. Joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

ANDER LAMAISON, Masaryk University
Hypergraphs with minimum uniform Turán density  [PDF]

Reiher, Rödl and Schacht showed that the uniform Turán density of every $3$-uniform hypergraph is either $0$ or at least $1/27$, and asked whether there exist $3$-uniform hypergraphs with uniform Turán density equal or arbitrarily close to $1/27$. We construct $3$-uniform hypergraphs with uniform Turán density equal to $1/27$. Joint work with Frederik Garbe and Dan Král.

RICHARD LANG, Heidelberg University
Minimum degree conditions for tight Hamilton cycles  [PDF]

We study the existence of tight Hamilton cycles in $k$-uniform hypergraphs under minimum $d$-degree conditions. The case of $k=2$ and $d=k-1$ corresponds to Dirac's classic theorem. A well-known result of Rödl, Ruciński and Szemerédi extends this to all $k \geq 3$. Here, we develop a general framework to approach this problem and use it to resolve the case of $d=k-2$ and $k \geq 3$.

NICOLÁS SANHUEZA-MATAMALA, Czech Academy of Sciences
Spanning bounded-degree tight $k$-trees  [PDF]

A $k$-graph is a tight $k$-tree if its edges can be ordered such that the following holds for all edges $e$ except the first: $e$ has a vertex $v$ which is not in any previous edge, and $e \setminus \{v\}$ is contained in some previous edge. We determine asymptotically-optimal codegree conditions which ensure the containment of all spanning bounded-degree tight $k$-trees. This generalises a well-known result of Komlós, Sárközy and Szemerédi. Joint work with Matías Pavez-Signé and Maya Stein.