Portal de Periódicos da CAPES

Holes in Graphs

2001; Electronic Journal of Combinatorics; Volume: 9; Issue: 1 Linguagem: Inglês

10.37236/1618

1097-1440

Yuejian Peng, Vojtěch Rödl, Andrzej Ruciński,

Advanced Topology and Set Theory

The celebrated Regularity Lemma of Szemerédi asserts that every sufficiently large graph $G$ can be partitioned in such a way that most pairs of the partition sets span $\epsilon$-regular subgraphs. In applications, however, the graph $G$ has to be dense and the partition sets are typically very small. If only one $\epsilon$-regular pair is needed, a much bigger one can be found, even if the original graph is sparse. In this paper we show that every graph with density $d$ contains a large, relatively dense $\epsilon$-regular pair. We mainly focus on a related concept of an $(\epsilon,\sigma)$-dense pair, for which our bound is, up to a constant, best possible.