Stability theorems for the feasible region of cancellative hypergraphs

Xizhi Liu

Published 2019-12-26Version 1

A hypergraph is cancellative if it does not contain three sets $A,B,C$ such that the symmetric difference of $A$ and $B$ is contained in $C$. We show that for every $r\ge 3$ a cancellative $r$-graph $\mathcal{H}$ has a stability property whenever the sizes of $\mathcal{H}$ and the shadow of $\mathcal{H}$ satisfy certain inequalities. In particular, our result for $r=3$ generalizes a stability theorem of Keevash and Mubayi and it shows that for every $k\equiv 1$ or $3$ (mod $6$) a $3$-graph $\mathcal{H}$ is structurally close to a balanced blow up of a Steiner triple system on $k$ vertices whenever the shadow density of $\mathcal{H}$ is close to $(k-1)/k$ and the edge density of $\mathcal{H}$ is close to $(k-1)/k^2$. Our result for $r \ge 3$ extends a stability theorem of Keevash about the Kruskal-Katona theorem to cancellative hypergraphs, and also addresses an old conjecture of Bollob\'{a}s about the maximum size of a cancellative $r$-graph.