Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand the statement of the Szemerédi's Regularity Lemma as explained here, but am not able to wrap my head around to what it really means. In particular the concept of $\epsilon$-regularity and how it relates to drawing edges at random is not clear to me. If someone can explain the statement and the meaning of the theorem (not the proof) I would be most obliged.

Thanks.

share|improve this question
2  
This is going to be just a comment since it will be very inprecise. The regularity lemma tells you that the vertices of any large enough graph can be partitioned into classes of equal size (except for a $f(\epsilon)$ number of them) so that the number of outedges from each class is almost constant (the $\epsilon$ constant tells you in what range is the number of outedges) –  Jernej Jul 16 '12 at 7:19

1 Answer 1

up vote 6 down vote accepted
+50

In a sense $\epsilon-$regularity is one way of capturing what it means for a graph to be "random-like". For comparison, let's suppose that $G$ is a random bipartite graph on two large subsets $A$ and $B$ having edge probability $p$ (meaning that every edge appears with probability $p$ independently; here $p$ is fixed). Here's several ways in which you might try and say $G$ really does "look random".

-The edges of $G$ are spread out evenly -- there aren't any huge clusters or huge empty spaces in the graph.

-Each small bipartite graph $H$ appears in $G$ about the number of times you expect it to (roughly $p^{E(H)}$ times the number of appearances in the complete bipartite graph).

-Almost all vertices in $A$ have degree roughly $p |B|$, and almost all pairs of vertices in $A$ have roughly $p^2 |B|$ common neighbors (being a neighbor of one vertex doesn't make you significantly more or less likely to be a neighbor of another vertex). The same holds if you swap $A$ and $B$.

As it turns out, the above three characterizations are actually equivalent, if quantified in the right way (this is a phenomenon known as "quasirandomness"). The idea of $\epsilon-$regularity is to quantify the first of these properties.

For each $S \subseteq A$ and $T \subseteq B$, our random graph is expected to have $p|S| |T|$ edges connecting $S$ with $T$. Rewording this slightly, the density $d(S,T):=\frac{|E(S,T)|}{|S||T|}$ is on average equal to $p$. So we might hope to make our "random-like" definition something like

"For every $S$ and $T$, we have $|d(S,T)-p|<\epsilon$"

But there's a problem here...if $S$ and $T$ are too small, there's no hope for this to hold (imagine the extreme case where $|S|=|T|=1$). So we'll add one additional condition: We only want the above bound to hold for subsets of size at least $\epsilon n$. The idea is that if a small subset is off, it won't have too much impact on things like subset counts anyway, so we might as well worry only about the large subsets. This modified definition is what is used for $\epsilon$-regularity in Szemerédi's Lemma.

What the Lemma itself says is that any dense graph can be approximated by a bounded number of these $\epsilon-$regular graphs (depending only on $\epsilon$, not on the size of the original graph). "Approximated by" here means that you may need to delete a small number ($\epsilon n^2$) edges, but once you delete them you'll be left with a graph on $k$ subsets $A_1, A_2, \dots, A_k$ of vertices, so that for every $i$ and $j$ the graph between $A_i$ and $A_j$ is random-like in all of the ways above [The value of $p$ may be different for each pair $(i,j)$].

share|improve this answer
    
Shouldn't you say $S\subset A$? –  Shahab Jul 25 '12 at 13:01
    
Yes, both of the $\in$ should read $\subseteq$. –  Kevin Costello Jul 26 '12 at 2:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.