Intersection property of Szemerédi's regularity condition

Question

We adopt common notations in the study of Szemerédi's regularity lemma and only focus on simple graph $G(V,E)$. For any two disjoint vertex sets $A,B\subset V$, we say the pair $(A,B)$ is $\varepsilon-$regular if for every $X\subset A$, $Y\subset B$ satisfying $|X|>\varepsilon|A|$ and $|Y|>\varepsilon|B|$, we have $$|d(X,Y)-d(A,B)|<\varepsilon,$$ where $d(X,Y)$ is the density defined by$$d(X,Y)=\frac{e(X,Y)}{|X||Y|}$$ and $e(X,Y)$ is the number of edges between $X$ and $Y$.

Here,I have difficult to prove the following Intersection Property:

Let $(A,B)$ be an $\varepsilon-$regular pair with density $d$. If $Y\subset B$ and $(d-\varepsilon)^l|Y|>\varepsilon|B|$ for some $l\geq1$, then $$\#\{(x_1,x_2,\ldots,x_l):x_i\in A,\left|Y\cap(\cap_{i=1}^lN(x_i))\right|\leq(d-\varepsilon)^l|Y|\}\leq l\varepsilon|A|^l,$$ where $N(x)$ is the set of neighbors of the vertex $x$.

Maybe the following fact will give some hints but I still don't know how to use it.

Let $(A,B)$ be an $\varepsilon-$regular pair with density $d$. Then for any $Y\subset B$, $|Y|>\varepsilon|B|$ we have $$\#\{x\in A: \left|Y\cap N(x)\right|\leq(d-\varepsilon)|Y|\}\leq \varepsilon|A|.$$

Apparently, this fact is special case of Intersection Property when $l=1$.

Answer 1

The regularity lemma has the unfortunate feature that, whilst it is conceptually extremely simple, there doesn't seem to be a terribly compact way of specifying regularity arguments precisely. This leads to the situation where lots of things are obvious to experts, and have obvious (to experts) proofs, but nobody really wants to write the details down.

In this situation all that's going on is that every $l$-tuple of points from $A$ should have about $d^l|Y|$ common neighbours in $Y$, "up to epsilons". Slightly more precisely, all but an $\epsilon$ fraction of $A$ has more than $(d-\epsilon)|Y|$ neighbours in $Y$. (This is just your second fact.) And given a vertex $x$ for which that holds, all but an $\epsilon$ fraction of $A$ has the property that it shares at least a $d-\epsilon$ fraction of the neighbours of $x$ in $Y$. If you keep going like this you get the statement you're looking for.

So that's a couple of sentences with all the ideas, and it should just take a bit of scribbling on scrap paper to convince yourself that everything works out. Formalised it looks exactly like Andrew's argument, but trying to read something like that is exactly the wrong thing to do. More so than in many other areas of mathematics, regularity proofs should be seen as cheat sheets in case you get stuck, rather than something to be read line by line.

Of course, you need some degree of familiarity before you're able to reconstruct arguments in this way. For example, here it's essential that applying the second fact is like breathing, as you'll be doing it constantly. If you don't yet have that level of familiarity, then first concentrate on understanding why it follows directly from the definition, as this is the fundamental observation that makes regularity so useful.