5
$\begingroup$

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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.