\(G\)-intersecting families (Q2777889)

Let \([n]= \{1,\dots, n\}\). For a graph \(G\) on the set of vertices \([n]\) and \(X\subseteq [n]\), \(N(X)\) denote \(X\cup\{y\in [n]\mid\) there is \(x\in X\) such that \(xy\) is an edge in \(G\}\). A family of sets \({\mathcal F}\subseteq 2^{[n]}\) is said to be \(G\)-intersecting if \(X,Y\in{\mathcal F}\Rightarrow N(X)\cap Y\neq\emptyset\). Intuitively, sets \(X\) and \(Y\) saisfying the condition above are `close' to each other. (The `closeness' relation is captured by the adjacency relation in \(G\).) Notice that in a special case when \(G\) has no edges the definition of a \(G\)-intersecting family coincides with the definition of a widely studied intersecting family. The celebrated Erdős-Ko-Rado theorem describes the largest \(k\)-uniform intersecting families. In this paper the authors study the largest \(k\)-uniform \(G\)-intersecting families, for several families of graphs \(G\). One can readily observe that there are \(k\)-uniform \(G\)-intersecting families consisting of at least \({n\choose k}-{n-\omega\choose k}\) sets, where \(\omega= \omega(G)\) is the cardinality of a largest clique in \(G\). Let \(K\) be a clique in \(G\). Moreover, let \(M_1,\dots, M_r\subseteq [n]\setminus K\) satisfy \(K\subseteq N(M_i)\), for \(i= 1,\dots, r\) and \(M_i\cap N(M_j)\neq\emptyset\), for \(i\neq j\). The collection \({\mathcal F}(K; M_1,\dots, M_r)= \{X\subseteq {[n]\choose k}\mid X\cap K\neq\emptyset\) or \(M_i\subseteq X\) for some \(i\}\) is obviously \(G\)-intersecting. One of the main results of the authors says that for `sparse' (in a sense defined in the paper) graphs \(G\), every \(k\)-uniform \(G\)-intersecting family of cardinality larger than \({n\choose k}- {n-\omega\choose k}\) is of the form \({\mathcal F}(K; M_1,\dots, M_r)\). This general result allows the authors to find the largest \(k\)-uniform \(G\)-intersecting families for large graphs \(G\) being powers of cycles (with fixed degrees of vertices) and regular graphs with no cycles on less than 6 vertices (with fixed degrees of vertices). The authors also obtain several results on the size of the largest \(k\)-uniform \(G\)-intersecting families for random graphs \(G\).