Concise proofs concerning the size and structure of large intersecting $$k$$-graphs
Abstract Let $$n > 2k \geq 4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>></mml:mo> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> and let $$\mathcal F \subset {[n]\choose k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>⊂</mml:mo> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>k</mml:mi> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> be an intersecting $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -graph on $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> vertices, that is, $$F\cap F' \neq \emptyset$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>∩</mml:mo> <mml:msup> <mml:mi>F</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>≠</mml:mo> <mml:mi>∅</mml:mi> </mml:mrow> </mml:math> for all $$F, F' \in \mathcal F$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>,</mml:mo> <mml:msup> <mml:mi>F</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>∈</mml:mo> <mml:mi>F</mml:mi> </mml:mrow> </mml:math> . By the Erd\H{o}s--Ko--Rado Theorem $$|\mathcal F| \leq { n - 1\choose k - 1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>F</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> with equality holding only for the full-star, $$\mathcal S_x$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>x</mml:mi> </mml:msub> </mml:math> , the family of all $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -sets containing the vertex $$x$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>x</mml:mi> </mml:math> . If we exclude stars, that is, subfamilies of $$\mathcal S_x$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>x</mml:mi> </mml:msub> </mml:math> then $$|\mathcal F| \leq { n - 1\choose k - 1} - { n - k - 1\choose k - 1} + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>F</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mfenced> <mml:mo>-</mml:mo> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac>
Authors
- P. Frankl
Institutions
- HUN-REN Alfréd Rényi Institute of Mathematics (HU)
Publication Details
- Journal
- Acta Mathematica Academiae Scientiarum Hungaricae
- Published
- 2026-02-09
- DOI
- https://doi.org/10.1007/s10474-025-01547-x
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00