Abstract
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 ⩾(1 +d2) (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 Ks,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.
Original language | English (US) |
---|---|
Article number | #4 |
Journal | Combinatorial Theory |
Volume | 4 |
Issue number | 1 |
DOIs | |
State | Published - 2024 |
Keywords
- Hilton–Milner
- Nontrivial intersecting family
- forbidden intersection
- graph intersection
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics