Small subsets inherit sparse ε-regularity

In this paper we investigate the behaviour of subgraphs of sparse ε-regular bipartite graphs G=(V1∪V2,E) with vanishing density d that are induced by small subsets of vertices. In particular, we show that, with overwhelming probability, a random set S⊆V1 of size s≫1/d contains a subset S′ with |S′|⩾(1−ε′)|S| that induces together with V2 an ε′-regular bipartite graph of density (1±ε′)d, where ε′→0 as ε→0. The necessity of passing to a subset S′ is demonstrated by a simple example.We give two applications of our methods and results. First, we show that, under a reasonable technical condition, “robustly high-chromatic” graphs contain small witnesses for their high chromatic number. Secondly, we give a structural result for almost all Cℓ-free graphs on n vertices and m edges for odd ℓ, as long as m is not too small, and give some bounds on the number of such graphs for arbitrary ℓ.