PIMS-CORDS SFU Operations Research Seminar: Nitya Mani
Topic
Tetrahedron intersecting families of hypergraphs
Speakers
Details
An $H$-intersecting family of 3-uniform hypergraphs on $n$ labelled vertices is a family of hypergraphs $\mathcal{F}$ such that for any pair of hypergraphs $G_1, G_2 \in \mathcal{F}$, the intersection $G_1 \cap G_2$ contains a copy of $H$ as a subgraph. One can construct a large such family $\mathcal{F}$ by choosing all of the hypergraphs that contain a fixed copy of $H$, a family with size $2^{{n \choose 3} - e(H)}$. Understanding for which cases such a family is asymptotically maximal is a very old and well-studied question, and it has been conjectured that this lower bound is tight whenever $H$ is a complete graph. The case of triangle intersecting families of graphs was studied by Shearer and was one of the first application's of Shearer’s entropy inequality to a combinatorial problem. This triangle-intersecting problem was fully resolved by Ellis, Filmus, and Friedgut, and more recently the case of $K_4$-intersecting graphs was resolved by Berger and Zhao, both using linear programming bounds. Despite this progress, understanding the maximal size of an $H$-intersecting family remains open for every other complete (hyper)graph. In join work with Owen Zhang, we resolve the case of $K_5$-intersecting families and provide the first resolution of an instance in the hypergraph setting, showing that the conjecture holds for tetrahedron-intersecting families of 3-uniform hypergraphs.
Additional Information
This event is UBC-O hosted.