A note on hypergraphs without non-trivial intersecting subgraphs

DOI10.1017/S096354832200013XMaRDI QIDQ6345581arXivFDO

Authors Xizhi Liu

Publication date 21 July 2020

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Extremal set theory (05D05) Triple systems (05B07)

Abstract: A hypergraph $mathcalF$ is non-trivial intersecting if every two edges in it have a nonempty intersection but no vertex is contained in all edges of $mathcalF$. Mubayi and Verstra"{e}te showed that for every $kged+1ge3$ and $nge(d+1)n/d$ every $k$-graph $mathcalH$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $$ edges. They conjectured that the same conclusion holds for all $dgekge4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $mge4$ and sufficiently large $n$ the maximum size of a $3$-graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner systems. We give a construction with more edges showing that their conjecture is not true in general.

This page was built for publication: A note on hypergraphs without non-trivial intersecting subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345581)