Concise proofs concerning the size and structure of large intersecting $$k$$-graphs

Abstract Let $$n &gt; 2k \geq 4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&gt;</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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Concise proofs concerning the size and structure of large intersecting $$k$$-graphs

P. Frankl
Acta Mathematica Academiae Scientiarum Hungaricae
Limits and Structures in Graph Theory
article

Concise proofs concerning the size and structure of large intersecting $$k$$-graphs

P. Frankl
article en

Abstract

Abstract Let $$n &gt; 2k \geq 4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&gt;</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>

Acta Mathematica Academiae Scientiarum Hungaricae
HUN-REN Alfréd Rényi Institute of Mathematics (HU)
Openalex Percentile: Top 59%
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.