EUVIMEDEUVIMED entdecken
Crossref

Improved bounds for the Erdős-Rogers function

Timothy Gowers, Oliver Janzer

Advances in Combinatorics · 2020

DOI: 10.19086/aic.12048 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Advances in Combinatorics, 2020. Verfasst von Timothy Gowers und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

[Ramsey's Theorem](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) is one of the most prominent results in graph theory. In its simplest form, it asserts that every sufficiently large two-edge-colored complete graph contains a large monochromatic complete subgraph. This theorem has been generalized to a plethora of statements asserting that every sufficiently large structure of a given kind contains a large "tame" substructure. The article concerns a closely related problem: for a structure with a given property, find a substructure possessing an even stronger property. For example, what is the largest $K_3$-free induced subgraph of an $n$-vertex $K_4$-free graph? The answer to this question is approximately $n^{1/2}$. The lower bound is easy. If a given graph has a vertex of degree at least $n^{1/2}$, then its neighbors induce a $K_3$-free subgraph with at least $n^{1/2}$ vertices. Otherwise, a greedy procedure yields an independent set of size almost $n^{1/2}$. The argument generalizes to $K_s$-free induced subgraphs of $K_{s+1}$-free graphs. Dudek, Retter and Rödl provided a construction showing that the exponent $1/2$ cannot be improved and asked whether the same is the case for $K_s$-free induced subgraphs of $K_{s+2}$-free graphs. The authors answer this question by providing a construction of $K_{s+2}$-free $n$-vertex graphs with no $K_s$-free induced subgraph with $n^{\alpha_s}$ vertices with $\alpha_s

Zitieren

APA

Gowers, T., & Janzer, O. (2020). Improved bounds for the Erdős-Rogers function. Advances in Combinatorics. https://doi.org/10.19086/aic.12048

Vancouver

Gowers T, Janzer O. Improved bounds for the Erdős-Rogers function. Advances in Combinatorics. 2020. doi:10.19086/aic.12048

BibTeX
@article{Gowers2020,
  author = {Gowers, Timothy and Janzer, Oliver},
  title = {Improved bounds for the Erdős-Rogers function},
  journal = {Advances in Combinatorics},
  year = {2020},
  doi = {10.19086/aic.12048}
}
Kostenlos starten →