Monday, June 30, 2008

Most degrees into a large set are large (the proof is worked out!)

Theorem: Let (A,B) be an ɛ-regular pair with density d. Then for any $Y\subset B, \; |Y| > \epsilon |B|$, we have

$|\{x\in A\:\mid\: \mbox{deg}(x,Y)\leq (d-\epsilon)|Y|\}|\leq \epsilon|A|.$

Proof:

Let $1 > \delta > \epsilon$ be a constant. Let
$X = \{\x\in A : \mbox{deg}(x,Y)\leq (d-\epsilon) |Y|}$

and assume that

$|X| = \delta |A|$. ..................... (*)

Hence we have
$d(X,Y)\leq\frac{\delta|A|\cdot (d-\epsilon)|Y|}{\delta|A|\cdot |Y|}\leq d-\epsilon$......................(1)

But $|X| > \epsilon |A|, |Y| > \epsilon |B|$, since (A,B) are ɛ-regular, we have
$d-\epsilon < d(X,Y) < d+\epsilon$..........................(2)

(2) contradicts (1), therefore the theorem is then proved.
$\qed$

J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szemerédi: The regularity lemma and its applications in graph theory. Theoretical Aspects of Computer Science, Lecture Notes Comput. Sci., Vol. 2292, pp. 84--112, 2002.

BarrosH said...

Joseph, Chuang-Chieh Lin said...