Skip to main content
2 of 2
fixed typo
YCor
  • 63.9k
  • 5
  • 187
  • 286

Sufficiently large $\varepsilon$-regularity pairs and subsets in graphs

Let $G$ be a graph and $X,Y \subset V(G)$. Say that $(X,Y)$ is an $\varepsilon$-regular pair if for all $A \subset X$ and $B \subset Y$ with $|A| \geqslant \varepsilon|X|$ and $|B| \geqslant \varepsilon|Y|$, one has $$\left| d(A,B) - d(X,Y) \right| \leqslant \varepsilon,$$where $d(\cdot,\cdot)$ denotes the edge density. Moreover, if $(X,X)$ is an $\varepsilon$-regular pair, we say $X$ is an $\varepsilon$-regular subset. We also define $\varepsilon$-regular partition as partition $\{ V_1, V_2, \ldots, V_n \}$, $$\sum_{\textrm{parts }(V_i,V_j)\textrm{ are irregular}} \frac{|V_i||V_j|}{|V(G)|^2} \leqslant \varepsilon. $$

I wonder if there exists some result about $\varepsilon$-regular pairs or subsets with a given size such as $O(n)$, and whether we can say more about the coefficients of it.

(A little deviation.) Moreover, I can find few contexts about regular subsets. And I wish to know if there are some survey or brief introductions about this topic? In particular, is there any correlation between $\varepsilon$-regular partition and it, i.e. is it possible that each part of such a partition is $\varepsilon$-regular?

Thanks for any enlightenment.