Holes in graphs (Q5954318): Difference between revisions

In variation of Szemerédi's regularity lemma (for this see [\textit{J. Komlós} and \textit{M. Simonovits}, Bolyai Soc. Math. Stud. 2, 295-352 (1996; Zbl 0851.05065)]) the authors ask for a large nearly regular subgraph instead of a partition into nearly regular parts: In a bipartite graph \(G= (V_1,V_2; E)\) the density of a pair \(U_1\subseteq V_1\), \(U_2\subseteq U_2\) is defined as \(d(U_1, U_2)= e(U_1, U_2)\cdot|U_1|^{-1}\cdot |U_2|^{- 1}\) (\(e\) denoting the number of edges), and this pair is called \(\varepsilon\)-regular, where \(0< \varepsilon< 1\), if for every pair \(W_1\subseteq U_1\), \(W_2\subseteq U_2\) with \(|W_1|\geq \varepsilon|U_1|\) and \(|W_2|\geq \varepsilon|U_2|\) one has \((1-\varepsilon) d(U_1, U_2)\leq d(W_1, W_2)\leq (1+ \varepsilon) d(U_1, U_2)\). \(d\) and \(\varepsilon\) being given it is shown that every bipartite graph \(G= (V_1, V_2; E)\) with \(|V_1|=|V_2|= n\) contains an \(\varepsilon\)-regular pair \((U_1, U_2)\) with density \(\geq (1-{\varepsilon\over 3})d\) and \(|U_1|=|U_2|\geq {n\over 2} d^{c/\varepsilon^2}\), where \(c\) is an absolute constant. More generally \((\varepsilon,\sigma)\)-dense pairs are considered---\(\sigma\) bounding the density from below---and especially for \(\sigma={d\over 2}\) bounds for the number of vertices of such pairs in \(G\) are given.