Talk information

Date: Sunday, January 02, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Lior Gishboliner (ETH Zurich)
Title: On $3$-graphs with no four vertices spanning exactly two edges

Abstract:

Let $D_2$ denote the $3$-uniform hypergraph with $4$ vertices and $2$ edges. Answering a question of Alon and Shapira, we prove an induced removal lemma for $D_2$ having polynomial bounds. We also prove an Erdős-Hajnal-type result: every induced $D_2$-free hypergraph on $n$ vertices contains a clique or an independent set of size $n^{c}$ for some absolute constant $c > 0$. For both problems, $D_2$ is the only nontrivial $k$-uniform hypergraph with $k \geq 3$ which admits a polynomial bound.

Joint work with István Tomon.