A note on \(G\)-intersecting families (Q1861255)

Let \(G\) be a simple graph on vertex set \([n]\) and let \({\mathcal H}\) be a \(k\)-uniform hypgergraph on \([n]\). \({\mathcal H}\) is said to be \(G\)-intersecting if for any \(e,f\in{\mathcal H}\), either \(e\cap f\neq\emptyset\) or there are vertices \(u\in e\) and \(v\in f\) that are adjacent in \(G\). In this note, the authors compute bounds for the value of \[ N(G,k)=\max\left\{|{\mathcal H}|:{\mathcal H} \subseteq{[n] \choose k}\text{ and }{\mathcal H} \text{ is } G\text{-intersecting} \right\} \] for sparse graphs \(G\), and investigate the structure of the maximum \(G\)-intersecting hypergraphs, improving previous results of \textit{T. Bohman}, \textit{A Frieze}, \textit{M. Ruszinkó} and \textit{L. Thoma} [Comb. Probab. Comput. 10, 367-384 (2001; Zbl 0998.05063)]. The main result reads: Let \(G\) be a graph on \(n\) vertices with maximum degree \(\Delta\) and clique number \(w\). There exists a constant \(C\) (depending only on \(\Delta\) and \(\omega)\) such that if \({\mathcal H}\) is a \(G\)-intersecting \(k\)-uniform hypergraph and \(k<Cn^{1/2}\) then \[ |{\mathcal H}|\leq{n\choose k}-{n-\omega\choose k}+{\omega(\Delta-\omega+1)\choose 2}{n-\omega-2\choose k-2}. \]