Erdős‐Rogers Functions for Arbitrary Pairs of Graphs
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.
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}
}
EUVIMED