A Generalized Turán Extension of the Deza–Erdős–Frankl Theorem
Journal of Graph Theory · 2026-06 · 112 (2) · 161-171
DOI: 10.1002/jgt.70023 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 20.03.2026. Verfasst von Charlotte Helliar und 1 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Gefördert von: H2020 European Research Council.
Abstract (Originalsprache)
For an integer and a subset , a graph is ‐intersecting if the number of vertices in the intersection of every pair of in belongs to . We study the maximum number of in an ‐vertex ‐intersecting graphs. The celebrated Ruzsa–Szemerédi Theorem corresponds to the case and . For general with , we establish the upper bound for large , which improves the bound provided by the celebrated Deza–Erdős–Frankl Theorem by a factor of . In the special case where , we derive the tight upper bound for large and establish a corresponding stability result. This is an extension of the seminal Erdős–Ko–Rado Theorem on ‐intersecting systems to the generalized Turán setting. Our proof for the Deza–Erdős–Frankl part involves an interesting combination of the ‐system method and Turán's theorem. Meanwhile, for the Erdős–Ko–Rado part, we employ the stability method, which relies on a theorem of Frankl regarding ‐intersecting systems.
Förderung
- H2020 European Research Council
Zitieren
APA
Helliar, C., & Liu, X. (2026). A Generalized Turán Extension of the Deza–Erdős–Frankl Theorem. Journal of Graph Theory, 112(2), 161-171. https://doi.org/10.1002/jgt.70023
Vancouver
Helliar C, Liu X. A Generalized Turán Extension of the Deza–Erdős–Frankl Theorem. Journal of Graph Theory. 2026;112(2):161-171. doi:10.1002/jgt.70023
BibTeX
@article{Helliar2026,
author = {Helliar, Charlotte and Liu, Xizhi},
title = {A Generalized Turán Extension of the Deza–Erdős–Frankl Theorem},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {2},
pages = {161--171},
doi = {10.1002/jgt.70023}
}
EUVIMED