Improved bounds for the Erdős-Rogers function
- Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, UK
- ORCID iD: 0000-0002-5168-0785
- Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, UK
Editorial introduction
Ramsey’s 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 K3-free induced subgraph of an n-vertex K4-free graph? The answer to this question is approximately n1/2. The lower bound is easy. If a given graph has a vertex of degree at least n1/2, then its neighbors induce a K3-free subgraph with at least n1/2 vertices. Otherwise, a greedy procedure yields an independent set of size almost n1/2. The argument generalizes to Ks-free induced subgraphs of Ks+1-free graphs. Dudek, Retter and Rödl provided a construction showing that the exponent 1/2 cannot be improved and asked whether it is the correct exponent in the case of Ks-free induced subgraphs of Ks+2-free graphs as well. The authors answer this question in the negative by providing a construction of Ks+2-free n-vertex graphs with no Ks-free induced subgraph with nαs vertices with αs<1/2 for every s≥3. Their arguments extend to the case of Kt-free graphs with no large Ks-free induced subgraph for s+2≤t≤2s−1 and s≥3.