×

Hypergraphs of bounded disjointness. (English) Zbl 1296.05196

A \(k\)-uniform hypergraph \(H\) is said to be \(s\)-almost intersecting if every edge is disjoint from exactly \(s\) other edges and \(H\) is \([a,b]\)-almost intersecting if for all \(A\in E(H)\), \(a\leq |\{B\in E(H): A\cap B=\emptyset\}|\leq b\) holds. D. Gerbner et al. [SIAM J. Discrete Math. 26, No. 4, 1657–1669 (2012; Zbl 1261.05126)] conjectured that for every \(k\), and \(s>s_0(k)\), every \(k\)-uniform \(s\)-almost intersecting hypergraph has at most \((s+1){{2k-2}\choose{k-1}}\) edges. In this paper a strengthened version of this conjecture is proved: for every \(k\geq 2\) there are \(R=R(k)\) and \(s_0(k)\) such that, for \(s>s_0\), every \(k\)-uniform \([R,s]\)-almost intersecting hypergraph has at most this number of edges. All the extremal hypergraphs are determined; among the extremal hypergraphs, one family, described here, minimizes the number of elements in the base set. Sharp bounds are also proved for multihypergraphs. Some related problems and conjectures are given.

MSC:

05D05 Extremal set theory
05C65 Hypergraphs

Citations:

Zbl 1261.05126
PDFBibTeX XMLCite
Full Text: DOI arXiv