I am not very sure how to approach the following questions regarding $\epsilon$-regularity of graphs. Any help would be greatly appreciated!

  1. For a graph G and disjoint vertex sets A and B, given (A, B) is an $\epsilon$-regular pair with density $d$. Also $Y \subset B$ with $(d-\epsilon)^{m-1} |Y| > \epsilon |B|$ where $m \in \mathbb{N}$. Show that $|\{(x_1, x_2, ..., x_m) \in A^{m} : | \bigcap_{i=1}^m \{y \in Y : \{ (x_i, y) \in E(G)\}| \le (d-\epsilon)^{m}|Y|\}| \le m\epsilon |A|^m $

  2. Let $k$ and $k'$ be two positive integers. If (A, B) is an $\epsilon$ regular pair with density d, suppose $d >> \epsilon$ and $|A|=|B|=n$ where n is sufficiently large integer, show that (A, B) has a copy of $\mathcal{K}_{k,k'}$ (the complete bipartite graph on k and k' vertices).

My thoughts: the first question requires us to find a bound for the size of all possible m-tuples of the vertex set A, so that the number of common neighbors for each coordinate vertex of a tuple does not exceed that given value. I think it's wise to start counting the number of neighbors in A of each vertex in Y, and check that it does not exceed the total number of edges. but I'm not sure how to proceed from there.

The second problem only tells us if we take a sufficiently large chunk of vertices from (A, B) it's density essentially remains the same. The problem is trivial when $d \approx 1$ but for any $d \in (0, 1)$ I'm not sure how this observation would lead us to find a copy of $\mathcal{K}_{k,k'}$

  • $\begingroup$ 1. For $m=1$ this follows directly from $\epsilon$-regularity, since otherwise the sets $\{ x_1 \in A : x_1 \text{ has at most } (d-\epsilon)|Y| \text{ neighbors in } Y \}$ and $Y$ would witness $\epsilon$-irregularity. $\endgroup$
    – ploosu2
    Commented Sep 2, 2021 at 8:18

1 Answer 1


Question $1$:

Induction on $m$. The case $m=1$ is by ploose2 in the above comment, that is, all but $\epsilon |A|$ elements in $A$ have degree $\ge (d-\epsilon)|Y|$ in $Y$. Let's prove only the case $m=2$, since the same argument holds for general $m$.

We want to prove that $Y\subseteq B$, $(d-\epsilon)|Y|>\epsilon B$, then $$\#\{ (a,a')\in A\times A: d_Y(a,a')\le (d-\epsilon)^2|Y|\}\le 2\epsilon |A|^2.$$ There are $\ge (1-\epsilon)|A|$ vertex $a\in A$ with deg. $\ge (d-\epsilon)|Y|$ in $Y$, i.e. $|N_Y(a)|\ge (d-\epsilon)|Y|>\epsilon B$.

Fix some $a_0$, then again by $m=1$, we see that all but $\epsilon |A|$ vts in $A$ have degree $\ge (d-\epsilon)|N_Y(a_0)|$ in $N_Y(a_0)$, i.e. the number of vts $a'\in A$ s.t. $d(a_0,a')\ge (d-\epsilon)^2|Y|$ is at least $(1-\epsilon)|A|$.

Thus, the number of total $(a,a')$ s.t. $d(a,a')\le (d-\epsilon)^2|Y|$ is at most $\epsilon |A| |A|+(1-\epsilon)|A|\epsilon|A|\le 2\epsilon |A|^2$.

Question $2$:

Let's show only the case $K_{2,k'}$, since the same arguement holds for general $K_{k,k'}$.

Since $d(A,B)=d$, there is some vtx $a_1\in A$ with $d_B(a_1)\ge (d-\epsilon)|B|>\epsilon|B|$. So there is a $K_{1,k'}$ when $n$ is large enough with $(d-\epsilon)|B|\ge k$.

Set $m=1$ in Question $1$, we see that all but $\epsilon |A|$ vts in $A$ have degree $\ge (d-\epsilon)|N_B(a_1)|$ in $N_B(a_1)$. Take such a vtx $a_2\in A$. $d(a_1,a_2)\ge (d-\epsilon)^2|B|>\epsilon |B|$. So there is a $K_{2,k'}$ when $n$ is large enough.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .