Blow-Up Lemma
المؤلف:
Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E
المصدر:
"Blow-Up Lemma." Combinatorica 17
الجزء والصفحة:
...
18-5-2022
1847
Blow-Up Lemma
The blow-up lemma essentially says that regular pairs in Szemerédi's regularity lemma behave like complete bipartite graphs from the point of view of embedding bounded degree subgraphs.
In particular, given a graph 
of order 
, minimal vertex degree 
and maximal vertex degree 
, then there exists an 
such that the following holds. Let 
be an arbitrary positive integer, and replace the vertices of 
with pairwise disjoint 
-sets 
, 
, ..., 
(blowing up). Now construct two graphs on the same vertex set 
. The graph 
is obtained by replacing all edges of 
with copies of the complete bipartite graph 
, and construct a sparser graph by replacing the edges of 
with some 
-superregular pair. If a graph 
with 
is embeddable into 
, then it is already embeddable into 
(Komlós et al. 1998).
REFERENCES
Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Blow-Up Lemma." Combinatorica 17, 109-123, 1997.
Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
