Short proofs of three results about intersecting systems

József Balogh, William Linz

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number#4
JournalCombinatorial Theory
Volume4
Issue number1
DOIs
StatePublished - 2024

Keywords

  • Hilton–Milner
  • Nontrivial intersecting family
  • forbidden intersection
  • graph intersection

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Short proofs of three results about intersecting systems'. Together they form a unique fingerprint.

Cite this