EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Erdős‐Rogers Functions for Arbitrary Pairs of Graphs

Dhruv Mubayi, Jacques Verstraëte

Random Structures & Algorithms · 2026-05 · 68 (3)

DOI: 10.1002/rsa.70078 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 25.05.2026. Verfasst von Dhruv Mubayi und 1 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let be the largest size of an induced ‐free subgraph that every ‐vertex ‐free graph is guaranteed to contain. We prove that for any triangle‐free graph , Along the way we give a slight improvement of a construction of Erdős‐Frankl‐Rödl for the Brown‐Erdős‐Sós ‐problem when is large. In contrast to our result for , for any ‐free graph containing a cycle, we prove there exists such that For every graph , we prove that there exists such that whenever is a non‐empty graph such that is not contained in any blowup of , then . On the other hand, for graph that is not a clique, and every , we exhibit a ‐free graph such that .

Förderung

  • National Science Foundation

Zitieren

APA

Mubayi, D., & Verstraëte, J. (2026). Erdős‐Rogers Functions for Arbitrary Pairs of Graphs. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70078

Vancouver

Mubayi D, Verstraëte J. Erdős‐Rogers Functions for Arbitrary Pairs of Graphs. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70078

BibTeX
@article{Mubayi2026,
  author = {Mubayi, Dhruv and Verstraëte, Jacques},
  title = {Erdős‐Rogers Functions for Arbitrary Pairs of Graphs},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {3},
  doi = {10.1002/rsa.70078}
}
Kostenlos starten →