EUVIMEDEUVIMED entdecken
Crossref

A Generalized Turán Extension of the Deza–Erdős–Frankl Theorem

Charlotte Helliar, Xizhi Liu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →