Small subsets inherit sparse ε-regularity

In this paper we investigate the behaviour of subgraphs of sparse ε-regular bipartite graphs G = ( V 1 ∪ V 2 , 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 ⊆ V 1 of size s ≫ 1 / d contains a subset S ′ with | S ′ | ⩾ ( 1 − ε ′ ) | S | that induces together with V 2 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. e 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 ℓ.