Combinatorial Theory

In this note, we give short proofs of three theorems about intersection problems. The first one is a determination of the maximum size of a nontrivial \(k\)-uniform, \(d\)-wise intersecting family for \(n\ge \left(1+\frac{d}{2}\right)(k-d+2)\), which improves the range of \(n\) of a recent result of O'Neill and Verstraëte. Our proof also extends to \(d\)-wise, \(t\)-intersecting families, and from this result we obtain a version of the Erdős-Ko-Rado theorem for \(d\)-wise, \(t\)-intersecting families.

Our second result partially proves a conjecture of Frankl and Tokushige about \(k\)-uniform families with restricted pairwise intersection sizes.

Our third result is about intersecting families of graphs. Answering a question of Ellis, we construct \(K_{s, t}\)-intersecting families of graphs which have size larger than the Erdős-Ko-Rado-type construction, whenever \(t\) is sufficiently large in terms of \(s\). The construction is based on nontrivial \((2s)\)-wise \(t\)-intersecting families of sets.

Mathematics Subject Classifications: 05D05, 05D99

Keywords: Nontrivial intersecting family, Hilton-Milner, forbidden intersection, graph intersection