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.