PreprintCC BY-NC-SA 4.0arXiv
Alon's conjecture on intersecting families of graphs
Abstract
Given a graph F, a family ℱ of graphs on [n] is \emph{F-intersecting} if G∩ H contains a copy of F for every G,H∈ℱ. We prove that there exists an absolute constant ε>0 such that every P4-intersecting family ℱ satisfies |ℱ|≤(1/2−ε)2binom n2, which resolves a conjecture of Alon. Combined with Alon's reduction, this proves that a graph F admits F-intersecting families of asymptotic density 1/2 if and only if F is a star forest. Multi-colored versions are also considered.
Related
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- Domination and maximal intersecting families in comaximal graphs of commutative rings
- Intersecting families with large covering number - On a conjecture of Frankl, Ota, and Tokushige
- The Alon-Tarsi number of 4-regular circulant graphs
- Three-Layer Intersecting Temperate Families
BibTeX
@misc{han2026alons,
title = {{Alon's conjecture on intersecting families of graphs}},
author = {Jie Han and Bin Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.13145},
eprint = {2609.13145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13145},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Alon's conjecture on intersecting families of graphs
AU - Jie Han
AU - Bin Wang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.13145
UR - https://arxiv.org/abs/2609.13145
AB - Given a graph F, a family ℱ of graphs on [n] is \emph{F-intersecting} if G∩ H contains a copy of F for every G,H∈ℱ. We prove that there exists an absolute constant ε>0 such that every P_4-intersecting family ℱ satisfies |ℱ|≤(1/2−ε)2^binom n2, which resolves a conjecture of Alon. Combined with Alon's reduction, this proves that a graph F admits F-intersecting families of asymptotic density 1/2 if and only if F is a star forest. Multi-colored versions are also considered.
ER -