irregular pairs in half graphs - Szemeredi regularity

Question

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just refer to the the Wikipedia link.

My question is about the part of the lemma saying "all except $\epsilon k^2$ of the pairs $V_i$, $V_j$ are $\epsilon$-pseudo random". (Note: "pseudo-random" and "regular" seem to be somewhat interchangeable in this context.) Concerning the necessity of these "irregular" pairs, a frequently cited example is the "half-graph".

In particular, given $n>0$, the half-graph of height $n$, $H_n$, is described as follows:

• $V(H_n)=\{v_1,\ldots,v_n,w_1,\ldots,w_n\}$,

• given, $1\leq i,j\leq n$, $(v_i,w_j)\in E(H_n)$ if and only if $i\leq j$,

• no other edges are present in $H_n$ (so $(\{v_1,\ldots,v_n\},\{w_1,\ldots,w_n\})$ is a bipartition for $H_n$).

The graphs $H_n$ were the first observed example of where irregular pairs in Szemeredi's Lemma are necessary. I have two questions about this.

1) What is the precise statement of this claim about irregular pairs in half graphs?

2) Is there a source where this claim is explained in detail?

Remarks:

Concerning question 1, the closest thing I have found is Section 2.1.2 of this survey paper, which says:

"The reader is invited to prove that, for small enough $\epsilon>0$, any $(\epsilon,k)$-equitable, $\epsilon$-regular partition of $H_n$ requires at least $ck$ $\epsilon$-irregular pairs, where $c=c(\epsilon)>0$ is some constant that depends only on $\epsilon$."

But I am still uncertain on exactly how $n$ and $k$ are being quantified in this statement. My best guess is:

"For any small enough $\epsilon>0$, there is $c=c(\epsilon)>0$ such that for all $k$ there is some large enough $n$ such that any $(\epsilon,k)$-equitable, $\epsilon$-regular partition of $H_n$ requires at least $ck$ $\epsilon$-irregular pairs."

Concerning question 2, I have only found sources that mention half-graphs as examples of irregular pairs. So it would be nice to know if this is worked out in detail somewhere.

Answer 1

Your guess at the quantification for (1) is correct. I don't know anywhere where this is explicitly worked out. It is a fairly tedious analysis, more or less you need to argue that the partition sets essentially respect the bipartition and that if a part among the $v_i$ isn't adjacent to any irregular pairs then its largest and smallest elements in the $v_i$ are not too far apart and the corresponding interval in the $w_j$ is split among too many parts to apply regularity. From this you conclude that either you have the desired irregular pairs or that the parts among the $v_i$ are closer to linear order than those in the $w_j$, and then you conclude that each part in the $w_i$ gives you an irregular pair.

However there is now a stronger statement available: in

http://arxiv.org/pdf/1107.4829v1.pdf

the authors construct graphs needing about as many irregular pairs as the Regularity Lemma will give you (one can take $\varepsilon$ to be something like $\log_* k$) in the Regularity Lemma).

Answer 2

It is worth mentioning that in a strong sense half-graphs are the only thing which can cause irregular pairs. In the paper Regularity lemma for stable graphs by Malliaris and Shelah it is shown that when you bound the size of the half-graphs which can occur in your graph four remarkable things happen:

(1) Irregular pairs are not needed.

(2) The density of edges across regular pairs is very close to either 0 or 1, i.e. for any regular pair "almost surely" there is an edge connecting any two elements or "almost surely" there is no edge connecting two elements.

(3) Every element of the partition is very close to either a complete graph or an independent set.

(4) Then number of pieces needed to get an epsilon-regular partition is only approximately (1/epsilon)^k where k depends on the maximum size of the half graph which can exist.

Answer 3

I had been stuck on this same problem for a while as well and asked Dr. Rödl about it. He gave me the following solution:

1. Suppose for $1/4>\epsilon >0$, we get $M$ as the upper bound on the number of partitions by applying the regularity lemma. We can take $N = kM$ and define the Half Graph $H_N$ that you mention here.

2. An equivalent version of the regularity lemma allows us to form equipartition on each of the halves (call them $V$ and $W$ and denote partitions by $V_i, W_j$), such that $|V_i| = |W_j| = k$ for all $i,j$

3. Delete the top and bottom $\epsilon k$ elements from each $W_i$ to form $W_i'$. Do the same to form $V_i'$. Then we delete $4\epsilon kM$ elements at most (at most half the number of total vertices). Then consider $W'$ as the union of $W_i'$. And similarly $V'$. Find a vertex in $V_i'$ called $v'_h$ and select $j$ such that $w'_h$ in $W'_j$ is below it (on re-indexing both $V'$, $W'$).

4. Then consider $(V_i,W_j)$. The part of $V_i$ below $v'_h$ with the part of $W_j$ above $w'_h$ is a 0 density graph. While the part of $V_i$ above $v_h'$ with the part of $W'_j$ below $w'_h$ is a density 1 graph. Both of these parts are not too small ($>\epsilon k$) in size because of how we constructed $V', W'$. Thus we have that $(V_i, W_j)$ is an irregular pair.

5. For every $V_i$, we can pick some $v'_h\in V_i'$, and find an irregular pair. Thus we have at least $M$ irregular pairs.