5143:
greedy algorithm to embed the majority of vertices, and then using a KĹ‘nig-Hall like argument to find an embedding for the remaining vertices. The first proof of the blow-up lemma also used a similar argument. Later in 1997, however, the same authors published another paper that found an improvement
5126:
The blow-up lemma, first published in 1997 by Komlós, Sárközy, and Szemerédi, emerged as a refinement of existing proof techniques using the regularity method to embed spanning graphs, as in the proof of the Bollobás conjecture on spanning trees, work on the Pósa-Seymour conjecture about the minimum
3595:
The only way that the first phase could fail is if it aborts, since by the first step we know that there is always a sufficient choice of good vertices. The program aborts only when the queue is too long. The argument then proceeds by
2091:
4420:
799:
3712:
5545:
5049:
4796:
4310:
4176:
3969:
3312:
1756:
3010:
1055:
996:
917:
858:
363:
1420:
1311:
290:
241:
137:
1975:
497:
420:
1650:
2164:
1551:
in this manner does not work because the algorithm may get stuck when only a small number of vertices are left. Instead, we set aside a small fraction of the vertex set, called
4580:
4098:
3345:
4496:
1816:
1279:
1159:
1091:
752:
4065:
3630:
2287:
1692:
1442:
1113:
4848:
3902:
3837:
that no vertices get added to the queue during the initial phase. It follows that all of the neighbors of the buffer vertices get added before the rest of the vertices.
3233:
1869:
189:
163:
5092:
4025:
3188:
3072:
2798:
2759:
2683:
3803:
3745:
3585:
3408:
678:
3869:
3461:
3036:
646:
620:
562:
523:
446:
3488:
2867:
2554:
2527:
2380:
1923:
1896:
1365:
1338:
1233:
1206:
594:
105:
4905:
1526:
4340:
4236:
4206:
3375:
5372:
5112:
4985:
4965:
4945:
4925:
4876:
4732:
4712:
4684:
4644:
4624:
4600:
4540:
4464:
3989:
3835:
3813:
Recall that the list was set up so that neighbors of vertices in the buffer get embedded first. The time until all of these vertices get embedded is called the
3765:
3548:
3528:
3508:
3432:
3253:
3148:
3128:
3108:
2958:
2929:
2909:
2889:
2840:
2818:
2723:
2703:
2649:
2627:
2607:
2584:
2500:
2480:
2460:
2440:
2420:
2400:
2350:
2327:
2307:
2258:
2238:
2218:
2184:
2114:
1836:
1670:
1581:
1549:
1497:
1477:
1385:
1179:
937:
726:
706:
5592:
4511:
1528:) for an appropriate choice of parameters. This means that there is a non-zero chance for the algorithm to succeed, so an embedding must exist.
5388:
2800:, and put vertices whose free sets have become too small with respect to their size in the last update in the set of prioritized vertices
5608:
5299:
5265:
5203:
1983:
24:
4345:
757:
3635:
1499:
sequentially. The argument then proceeds by bounding the failure rate of the algorithm such that it is less than 1 (and in fact
5701:
4035:
By Hall's marriage theorem, phase 2 fails if and only if Hall's condition is violated. For this to happen, there must be some
5696:
4990:
4737:
4606:
The blow-up lemma was used by Komlós, Sárközy, and Szemerédi to prove the conjecture for all sufficiently large values of
4443:
40:
3082:
The proof of correctness is technical and quite involved, so we omit the details. The core argument proceeds as follows:
4515:
4241:
4103:
3907:
3266:
1697:
1556:
5269:
5207:
28:
2963:
44:
1001:
942:
863:
804:
301:
5416:
2462:
could be mapped to without violating any of the adjacency conditions from the already-embedded neighbors of
1390:
1284:
246:
197:
110:
5135:, and the proof of the Alon-Yuster conjecture on the minimum degree needed for a graph to have a perfect H-
1928:
451:
374:
1594:
2119:
1555:, and attempt to embed the rest of the vertices. The buffer vertices are subsequently embedded by using
52:
36:
4545:
4423:
4070:
3317:
5140:
4507:
4469:
1761:
1453:
1238:
1118:
1060:
731:
4659:
5669:; HĂ n, Hiep; Kohayakawa, Yoshiharu; Person, Yury (2019-03-19). "Blow-up lemmas for sparse graphs".
5136:
4687:
4038:
3603:
2266:
1675:
1425:
1096:
5670:
5647:
5573:
5441:
5350:
5332:
5285:
5243:
5173:
4801:
4663:
5273:
5211:
3874:
3196:
1841:
168:
142:
43:. It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like
32:
5666:
5612:
5565:
5526:
5482:
5433:
5392:
5161:
5132:
5118:
This conjecture was proven by Komlós, Sárközy, and Szemerédi in 2001 using the blow-up lemma.
5054:
4503:
3994:
3157:
3041:
2767:
2728:
2725:
randomly from the set of "good" choices, where a choice is good iff none of the new free-sets
2659:
3770:
3717:
3557:
3380:
651:
5639:
5604:
5557:
5516:
5472:
5425:
5384:
5342:
5295:
5225:
5154:
4854:
They also conjectured that the result holds with only a constant (instead of linear) error:
3848:
3440:
3015:
1560:
1456:
625:
599:
532:
502:
425:
5307:
5239:
3466:
2845:
2532:
2505:
2358:
1901:
1874:
1343:
1316:
1211:
1184:
567:
78:
5303:
5235:
4881:
3805:
satisfy the conditions of the "main lemma", and thus have a low probability of occurring.
1502:
48:
4315:
4211:
4181:
3350:
3074:, and find a perfect matching in this bipartite graph. Embed according to this matching.
5097:
4970:
4950:
4930:
4910:
4861:
4717:
4697:
4669:
4629:
4609:
4585:
4525:
4449:
3974:
3820:
3750:
3533:
3513:
3493:
3417:
3238:
3133:
3113:
3093:
2943:
2914:
2894:
2874:
2825:
2803:
2708:
2688:
2634:
2612:
2592:
2569:
2485:
2465:
2445:
2425:
2405:
2385:
2335:
2312:
2292:
2243:
2223:
2203:
2169:
2099:
1821:
1655:
1566:
1534:
1482:
1462:
1370:
1164:
922:
711:
691:
5521:
5504:
5690:
5651:
5216:
5147:
5577:
5445:
5354:
5247:
5169:
5165:
5128:
4499:
3597:
5561:
5616:
5569:
5530:
5486:
5437:
5396:
5389:
10.1002/(SICI)1098-2418(199608/09)9:1/2<193::AID-RSA12>3.0.CO;2-P
63:
To formally state the blow-up lemma, we first need to define the notion of a
4655:
5477:
5460:
5153:
Stefan Glock and Felix Joos discovered a variant of the blow-up lemma for
4434:
The blow-up lemma has a number of applications in embedding dense graphs.
5609:
10.1002/(SICI)1097-0118(199811)29:3<167::AID-JGT4>3.0.CO;2-O
5300:
10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W
5168:
analogues of the blow-up lemma for embedding bounded degree graphs into
1181:
with the complete bipartite graph between the corresponding vertex sets
5429:
5230:
4690:(instead of just complete graphs), and proved the following statement:
3904:, we can find a sufficiently large lower bound on the probability that
5643:
5346:
2096:
denotes the density of edges between the corresponding vertex sets of
5411:
5290:
2940:
Consider the set of vertices left to be embedded, which is precisely
5630:
Glock, Stefan; Joos, Felix (2020-02-20). "A rainbow blow-up lemma".
5150:
found a generalization of the blow-up lemma to hypergraphs in 2010.
3600:
over all modes of failure, noting that for any particular choice of
5675:
5337:
2609:
of prioritized vertices is non-empty, then choose the vertex from
5410:
Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1998-03-01).
4422:
is a large set of unused vertices, we can use the main lemma and
4312:, so the probability of failure in such a case would be low. If
2871:
If there are non-buffer vertices left to be embedded in either
2086:{\displaystyle d_{xy}={\frac {e(V_{i},V_{j})}{|V_{i}||V_{j}|}}}
860:
be arbitrary positive integers and let us replace the vertices
5503:
Komlós, János; Sárközy, Gábor; Szemerédi, Endre (2001-05-28).
4734:
vertices, any graph G with n vertices and with minimum degree
4415:{\displaystyle A:=V_{i}(T)\setminus \bigcup _{z\in S}F_{z}(T)}
3012:. Form a bipartite graph between these two sets, joining each
1057:(blowing up). We construct two graphs on the same vertex set
3086:
Step 1: most vertices are good, and enough vertices are free
2352:
of presently prioritized vertices, which is initially empty.
1591:
We borrow all notation introduced in previous sections. Let
794:{\displaystyle \varepsilon =\varepsilon (\delta ,\Delta ,r)}
5591:
Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1998).
5544:
Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1995).
5371:
Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1996).
5323:
Keevash, Peter (2011-05-10). "A hypergraph blow-up lemma".
4208:
cannot be too small by largeness of free sets (step 1). If
3767:
representing a subset of the queue that failed, the triple
3707:{\displaystyle Y\subseteq X_{i},|Y|\geq \delta _{Q}|X_{i}|}
2842:
contains a sufficiently large fraction of any of the sets
1563:
between the buffer vertices and the remaining vertices of
1235:. A sparser graph G is constructed by replacing each edge
5164:, Hiep HĂ n, Yoshiharu Kohayakawa, and Yury Person, found
5139:. The proofs of all of these theorems relied on using a
5276:(1998), "An algorithmic version of the blow-up lemma",
2186:
is the final time after which the algorithm concludes.
5373:"On the square of a Hamiltonian cycle in dense graphs"
5144:
to the randomized algorithm to make it deterministic.
5100:
5057:
5044:{\displaystyle d\geq {\frac {\chi (H)-1}{\chi (H)}}n}
4993:
4973:
4953:
4933:
4913:
4884:
4864:
4804:
4791:{\displaystyle d\geq {\frac {\chi (H)-1}{\chi (H)}}n}
4740:
4720:
4700:
4672:
4632:
4612:
4588:
4548:
4528:
4472:
4452:
4348:
4342:
is neither too small nor too large, then noting that
4318:
4244:
4214:
4184:
4106:
4073:
4041:
3997:
3977:
3910:
3877:
3851:
3823:
3773:
3753:
3720:
3638:
3606:
3560:
3536:
3516:
3496:
3469:
3443:
3420:
3383:
3353:
3320:
3269:
3241:
3199:
3160:
3136:
3116:
3096:
3044:
3018:
2966:
2946:
2917:
2897:
2877:
2848:
2828:
2806:
2770:
2731:
2711:
2691:
2662:
2637:
2615:
2595:
2572:
2535:
2508:
2488:
2468:
2448:
2428:
2408:
2388:
2361:
2338:
2315:
2295:
2269:
2246:
2226:
2206:
2172:
2122:
2102:
1986:
1931:
1904:
1877:
1844:
1824:
1764:
1700:
1678:
1658:
1597:
1569:
1537:
1505:
1485:
1465:
1428:
1393:
1373:
1346:
1319:
1287:
1241:
1214:
1187:
1167:
1121:
1099:
1063:
1004:
945:
925:
866:
807:
760:
734:
714:
694:
654:
628:
602:
570:
535:
505:
454:
428:
377:
304:
249:
200:
171:
145:
113:
81:
2931:
and go back to step 1; otherwise move on to phase 2.
2936:
Phase 2: KĹ‘nig-Hall matching for remaining vertices
1452:The proof of the blow-up lemma is based on using a
5412:"Proof of the Seymour conjecture for large graphs"
5106:
5086:
5043:
4979:
4959:
4939:
4919:
4899:
4870:
4842:
4790:
4726:
4706:
4678:
4638:
4618:
4594:
4574:
4534:
4490:
4458:
4414:
4334:
4305:{\displaystyle \bigcup _{z\in S}F_{z}(T)=V_{i}(T)}
4304:
4230:
4200:
4171:{\displaystyle |\bigcup _{z\in S}F_{z}(T)|<|S|}
4170:
4092:
4059:
4019:
3983:
3963:
3896:
3863:
3829:
3797:
3759:
3739:
3706:
3624:
3579:
3542:
3522:
3502:
3482:
3455:
3426:
3402:
3369:
3339:
3306:
3247:
3227:
3182:
3142:
3122:
3102:
3066:
3030:
3004:
2952:
2923:
2903:
2883:
2861:
2834:
2812:
2792:
2753:
2717:
2697:
2677:
2643:
2621:
2601:
2578:
2548:
2521:
2494:
2474:
2454:
2434:
2414:
2394:
2374:
2344:
2321:
2301:
2281:
2252:
2232:
2212:
2178:
2158:
2108:
2085:
1969:
1917:
1890:
1863:
1830:
1810:
1750:
1686:
1664:
1644:
1575:
1543:
1520:
1491:
1471:
1436:
1414:
1379:
1359:
1332:
1305:
1273:
1227:
1200:
1173:
1153:
1107:
1085:
1049:
990:
931:
911:
852:
793:
746:
720:
700:
672:
640:
614:
588:
556:
517:
491:
440:
414:
357:
284:
235:
183:
157:
131:
99:
3964:{\displaystyle \phi (N_{H}(x))\subseteq N_{G}(v)}
1531:Attempting to directly embed all the vertices of
4662:considered the generalization of the well-known
2761:differ too much in size from the expected value.
2586:from the set of remaining vertices as follows:
2240:as a maximal set of vertices distance at least
4031:Step 6: phase 2 succeeds with high probability
3841:Step 5: buffer vertices have enough free spots
3591:Step 3: phase 1 succeeds with high probability
3307:{\displaystyle 1\leq i\leq r,Y\subseteq X_{i}}
2402:, representing the set of all "free spots" of
1751:{\displaystyle V(H)=X=\bigcup _{i\leq r}X_{i}}
5498:
5496:
5260:
5258:
5256:
2422:, that is, the set of unoccupied vertices in
8:
5318:
5316:
2166:is the embedding that we wish to construct.
1268:
1242:
1148:
1122:
667:
655:
5546:"Proof of a Packing Conjecture of Bollobás"
4466:-vertex graph with minimum degree at least
3490:such that the fraction of free vertices of
2200:Greedily choose the set of buffer vertices
5459:Alon, Noga; Yuster, Raphael (1996-03-01).
5674:
5520:
5476:
5465:Journal of Combinatorial Theory, Series B
5336:
5289:
5229:
5198:
5196:
5194:
5192:
5190:
5188:
5099:
5061:
5056:
5000:
4992:
4972:
4952:
4932:
4912:
4883:
4863:
4832:
4803:
4747:
4739:
4719:
4699:
4671:
4631:
4611:
4587:
4549:
4547:
4527:
4514:. The conjecture was further extended by
4473:
4471:
4451:
4397:
4381:
4359:
4347:
4327:
4319:
4317:
4287:
4265:
4249:
4243:
4238:is too large, then with high probability
4223:
4215:
4213:
4193:
4185:
4183:
4163:
4155:
4147:
4132:
4116:
4107:
4105:
4084:
4072:
4040:
4002:
3996:
3976:
3946:
3921:
3909:
3888:
3876:
3850:
3822:
3772:
3752:
3731:
3719:
3699:
3693:
3684:
3678:
3666:
3658:
3649:
3637:
3605:
3565:
3559:
3535:
3515:
3495:
3474:
3468:
3442:
3419:
3388:
3382:
3362:
3354:
3352:
3331:
3319:
3298:
3268:
3240:
3235:are fairly large for unembedded vertices
3204:
3198:
3165:
3159:
3135:
3115:
3095:
3049:
3043:
3017:
3005:{\displaystyle \bigcup _{b\in B}F_{b}(T)}
2987:
2971:
2965:
2945:
2916:
2896:
2876:
2853:
2847:
2827:
2805:
2775:
2769:
2736:
2730:
2710:
2690:
2661:
2636:
2631:Otherwise, choose a vertex from the list
2614:
2594:
2571:
2540:
2534:
2513:
2507:
2487:
2467:
2447:
2427:
2407:
2387:
2366:
2360:
2337:
2314:
2294:
2268:
2245:
2225:
2205:
2171:
2121:
2101:
2075:
2069:
2060:
2055:
2049:
2040:
2029:
2016:
2003:
1991:
1985:
1961:
1942:
1930:
1909:
1903:
1882:
1876:
1855:
1843:
1823:
1803:
1797:
1788:
1780:
1774:
1765:
1763:
1742:
1726:
1699:
1679:
1677:
1657:
1636:
1621:
1604:
1596:
1568:
1536:
1504:
1484:
1464:
1429:
1427:
1392:
1372:
1351:
1345:
1324:
1318:
1286:
1262:
1249:
1240:
1219:
1213:
1192:
1186:
1166:
1142:
1129:
1120:
1100:
1098:
1077:
1062:
1041:
1022:
1009:
1003:
982:
963:
950:
944:
924:
903:
884:
871:
865:
844:
825:
812:
806:
759:
733:
713:
693:
653:
627:
601:
569:
534:
504:
484:
476:
453:
427:
407:
399:
376:
350:
342:
337:
329:
303:
277:
269:
258:
250:
248:
228:
220:
209:
201:
199:
170:
144:
112:
80:
39:, particularly within the context of the
5550:Combinatorics, Probability and Computing
3154:only a small fraction of the choices in
1050:{\displaystyle n_{1},n_{2},\dots ,n_{r}}
991:{\displaystyle V_{1},V_{2},\dots ,V_{r}}
912:{\displaystyle v_{1},v_{2},\dots ,v_{r}}
853:{\displaystyle n_{1},n_{2},\dots ,n_{r}}
16:Important lemma in extremal graph theory
5184:
4374:
3991:was free before any of the vertices in
3554:Then, we prove that the probability of
2273:
2263:Order the remaining vertices (those in
358:{\displaystyle e(X,Y)>\delta |X||Y|}
107:of subsets of the vertex set is called
5366:
5364:
4542:vertices with minimum degree at least
1444:then it is already embeddable into G.
1415:{\displaystyle \Delta (H)\leq \Delta }
1306:{\displaystyle (\varepsilon ,\delta )}
285:{\displaystyle |Y|>\varepsilon |B|}
236:{\displaystyle |X|>\varepsilon |A|}
132:{\displaystyle (\varepsilon ,\delta )}
5505:"Proof of the Alon–Yuster conjecture"
5127:degree necessary to contain the k-th
3971:, conditional on the assumption that
3377:is not too small. Consider the event
3090:Prove simultaneously by induction on
1970:{\displaystyle x\in X_{i},y\in X_{j}}
492:{\displaystyle \deg(b)>\delta |A|}
415:{\displaystyle \deg(a)>\delta |B|}
7:
2561:Phase 1: Randomized Greedy Embedding
1645:{\displaystyle n=|V(G)|=\sum n_{i}}
1115:is obtained by replacing each edge
801:such that the following holds. Let
35:in 1997, is an important result in
5632:Random Structures & Algorithms
5377:Random Structures & Algorithms
5325:Random Structures & Algorithms
5278:Random Structures & Algorithms
2159:{\displaystyle \phi :V(G)\to V(H)}
1409:
1394:
779:
741:
14:
4987:vertices and with minimum degree
4602:-th power of a Hamiltonian cycle.
4575:{\displaystyle {\frac {kn}{k+1}}}
3809:Step 4: no queue in initial phase
5593:"On the PĂłsa-Seymour conjecture"
4093:{\displaystyle S\subseteq X_{i}}
3340:{\displaystyle A\subseteq V_{i}}
1680:
1430:
1101:
4491:{\displaystyle {\frac {2n}{3}}}
3130:is the vertex embedded at time
1811:{\displaystyle |X_{i}|=|V_{i}|}
1459:(RGA) to embed the vertices of
1274:{\displaystyle \{v_{i},v_{j}\}}
1154:{\displaystyle \{v_{i},v_{j}\}}
1086:{\displaystyle V=\bigcup V_{i}}
747:{\displaystyle \delta ,\Delta }
5081:
5075:
5032:
5026:
5012:
5006:
4894:
4888:
4826:
4823:
4817:
4805:
4779:
4773:
4759:
4753:
4409:
4403:
4371:
4365:
4328:
4320:
4299:
4293:
4277:
4271:
4224:
4216:
4194:
4186:
4164:
4156:
4148:
4144:
4138:
4108:
4014:
4008:
3958:
3952:
3936:
3933:
3927:
3914:
3792:
3774:
3700:
3685:
3667:
3659:
3363:
3355:
3222:
3210:
3177:
3171:
3061:
3055:
2999:
2993:
2787:
2781:
2748:
2742:
2672:
2666:
2153:
2147:
2141:
2138:
2132:
2076:
2061:
2056:
2041:
2035:
2009:
1804:
1789:
1781:
1766:
1710:
1704:
1622:
1618:
1612:
1605:
1515:
1509:
1403:
1397:
1300:
1288:
788:
770:
684:Statement of the Blow-up Lemma
583:
571:
551:
539:
485:
477:
467:
461:
408:
400:
390:
384:
351:
343:
338:
330:
320:
308:
278:
270:
259:
251:
229:
221:
210:
202:
126:
114:
94:
82:
1:
5522:10.1016/S0012-365X(00)00279-X
4060:{\displaystyle 1\leq i\leq r}
3625:{\displaystyle 1\leq i\leq r}
4850:vertex disjoint copies of H.
3414:no vertices are embedded in
2960:, and the set of free spots
2282:{\displaystyle H\setminus B}
1687:{\displaystyle \mathbf {R} }
1437:{\displaystyle \mathbf {R} }
1313:-super-regular pair between
1108:{\displaystyle \mathbf {R} }
939:with pairwise disjoint sets
564:denotes the number of pairs
139:-super-regular if for every
5461:"H-Factors in Dense Graphs"
4843:{\displaystyle (1-o(1))n/h}
4518:in 1974 to the following:
2382:indexed by the vertices of
2309:, placing the neighbors of
51:spanning graphs of bounded
5718:
5094:vertex disjoint copies of
4907:such that for every graph
3897:{\displaystyle v\in V_{x}}
3228:{\displaystyle F_{z}(t+1)}
1864:{\displaystyle x\in X_{i}}
754:, there exists a positive
184:{\displaystyle Y\subset B}
158:{\displaystyle X\subset A}
5562:10.1017/S0963548300001620
5214:(1997), "Blow-up lemma",
4426:the failure probability.
2355:Declare an array of sets
59:Definitions and Statement
45:complete bipartite graphs
5087:{\displaystyle n/h-c(h)}
4878:there exists a constant
4664:Hajnal–Szemerédi theorem
4020:{\displaystyle N_{H}(x)}
3817:. Prove by induction on
3259:Step 2: the "main lemma"
3183:{\displaystyle F_{x}(t)}
3067:{\displaystyle F_{b}(T)}
2793:{\displaystyle F_{z}(t)}
2754:{\displaystyle F_{z}(t)}
2678:{\displaystyle \phi (x)}
2190:Outline of the algorithm
728:and positive parameters
5597:Journal of Graph Theory
5417:Annals of Combinatorics
4446:conjectured that every
4438:PĂłsa-Seymour Conjecture
3798:{\displaystyle (i,Y,A)}
3740:{\displaystyle A=V_{i}}
3580:{\displaystyle E_{A,Y}}
3403:{\displaystyle E_{A,Y}}
2195:Phase 0: Initialization
1557:Hall's marriage theorem
673:{\displaystyle \{x,y\}}
5702:Lemmas in graph theory
5511:. Chech and Slovak 3.
5478:10.1006/jctb.1996.0020
5160:In 2019, Peter Allen,
5108:
5088:
5045:
4981:
4961:
4941:
4921:
4901:
4872:
4844:
4792:
4728:
4708:
4694:For every fixed graph
4680:
4650:Alon-Yuster Conjecture
4640:
4620:
4596:
4576:
4536:
4492:
4460:
4416:
4336:
4306:
4232:
4202:
4172:
4094:
4061:
4021:
3985:
3965:
3898:
3865:
3864:{\displaystyle x\in B}
3831:
3799:
3761:
3741:
3708:
3626:
3581:
3544:
3524:
3504:
3484:
3457:
3456:{\displaystyle y\in Y}
3434:during the first phase
3428:
3404:
3371:
3341:
3308:
3249:
3229:
3184:
3144:
3124:
3104:
3068:
3032:
3031:{\displaystyle b\in B}
3006:
2954:
2925:
2905:
2885:
2863:
2836:
2814:
2794:
2755:
2719:
2699:
2679:
2645:
2623:
2603:
2580:
2550:
2523:
2496:
2476:
2456:
2436:
2416:
2396:
2376:
2346:
2323:
2303:
2283:
2254:
2234:
2214:
2180:
2160:
2110:
2087:
1971:
1919:
1892:
1865:
1832:
1812:
1752:
1688:
1666:
1646:
1577:
1545:
1522:
1493:
1473:
1438:
1416:
1381:
1361:
1334:
1307:
1275:
1229:
1202:
1175:
1155:
1109:
1087:
1051:
992:
933:
913:
854:
795:
748:
722:
702:
674:
642:
641:{\displaystyle y\in Y}
616:
615:{\displaystyle x\in X}
590:
558:
557:{\displaystyle e(X,Y)}
519:
518:{\displaystyle b\in B}
493:
442:
441:{\displaystyle a\in A}
416:
359:
286:
237:
185:
159:
133:
101:
5697:Extremal graph theory
5109:
5089:
5046:
4982:
4962:
4942:
4922:
4902:
4873:
4845:
4793:
4729:
4709:
4681:
4641:
4621:
4597:
4577:
4537:
4493:
4461:
4417:
4337:
4307:
4233:
4203:
4173:
4095:
4062:
4022:
3986:
3966:
3899:
3866:
3832:
3800:
3762:
3742:
3709:
3627:
3582:
3545:
3525:
3505:
3485:
3483:{\displaystyle t_{y}}
3458:
3429:
3405:
3372:
3342:
3309:
3250:
3230:
3193:all of the free sets
3185:
3145:
3125:
3105:
3069:
3033:
3007:
2955:
2926:
2906:
2886:
2864:
2862:{\displaystyle X_{i}}
2837:
2815:
2795:
2764:Update the free sets
2756:
2720:
2700:
2680:
2651:of remaining vertices
2646:
2624:
2604:
2581:
2551:
2549:{\displaystyle V_{z}}
2524:
2522:{\displaystyle F_{z}}
2497:
2477:
2457:
2437:
2417:
2397:
2377:
2375:{\displaystyle F_{z}}
2347:
2324:
2304:
2284:
2255:
2235:
2220:from the vertices of
2215:
2181:
2161:
2111:
2088:
1972:
1920:
1918:{\displaystyle V_{i}}
1893:
1891:{\displaystyle V_{x}}
1866:
1833:
1813:
1753:
1689:
1672:can be embedded into
1667:
1647:
1578:
1546:
1523:
1494:
1474:
1439:
1417:
1382:
1362:
1360:{\displaystyle V_{j}}
1335:
1333:{\displaystyle V_{i}}
1308:
1276:
1230:
1228:{\displaystyle V_{j}}
1203:
1201:{\displaystyle V_{i}}
1176:
1156:
1110:
1088:
1052:
993:
934:
914:
855:
796:
749:
723:
703:
675:
643:
617:
591:
589:{\displaystyle (x,y)}
559:
520:
494:
443:
417:
360:
287:
238:
186:
160:
134:
102:
100:{\displaystyle (A,B)}
37:extremal graph theory
5509:Discrete Mathematics
5122:History and Variants
5098:
5055:
4991:
4971:
4951:
4947:vertices, any graph
4931:
4911:
4900:{\displaystyle c(h)}
4882:
4862:
4802:
4738:
4718:
4698:
4670:
4630:
4610:
4586:
4546:
4526:
4470:
4450:
4346:
4316:
4242:
4212:
4182:
4104:
4071:
4039:
3995:
3975:
3908:
3875:
3849:
3821:
3771:
3751:
3718:
3636:
3604:
3558:
3534:
3514:
3494:
3467:
3441:
3418:
3381:
3351:
3318:
3267:
3239:
3197:
3158:
3134:
3114:
3094:
3078:Proof of correctness
3042:
3016:
2964:
2944:
2915:
2895:
2875:
2846:
2826:
2804:
2768:
2729:
2709:
2689:
2660:
2635:
2613:
2593:
2570:
2533:
2506:
2486:
2466:
2446:
2426:
2406:
2386:
2359:
2336:
2313:
2293:
2267:
2244:
2224:
2204:
2170:
2120:
2100:
1984:
1929:
1902:
1875:
1842:
1822:
1762:
1698:
1676:
1656:
1595:
1567:
1535:
1521:{\displaystyle o(1)}
1503:
1483:
1463:
1426:
1391:
1371:
1344:
1317:
1285:
1239:
1212:
1185:
1165:
1119:
1097:
1061:
1002:
943:
923:
864:
805:
758:
732:
712:
692:
652:
626:
600:
568:
533:
503:
452:
426:
375:
302:
247:
198:
169:
143:
111:
79:
5174:pseudorandom graphs
4335:{\displaystyle |S|}
4231:{\displaystyle |S|}
4201:{\displaystyle |S|}
3370:{\displaystyle |A|}
2822:Abort if the queue
1422:is embeddable into
71:Super-regular pairs
5430:10.1007/BF01626028
5231:10.1007/BF01196135
5104:
5084:
5051:contains at least
5041:
4977:
4957:
4937:
4917:
4897:
4868:
4858:For every integer
4840:
4788:
4724:
4704:
4676:
4636:
4616:
4592:
4572:
4532:
4488:
4456:
4412:
4392:
4332:
4302:
4260:
4228:
4198:
4168:
4127:
4090:
4057:
4017:
3981:
3961:
3894:
3861:
3827:
3795:
3757:
3737:
3704:
3622:
3587:happening is low.
3577:
3540:
3520:
3500:
3480:
3453:
3424:
3400:
3367:
3337:
3304:
3245:
3225:
3180:
3140:
3120:
3100:
3064:
3028:
3002:
2982:
2950:
2921:
2901:
2881:
2859:
2832:
2810:
2790:
2751:
2715:
2695:
2675:
2641:
2619:
2599:
2576:
2546:
2529:is initialized to
2519:
2492:
2472:
2452:
2432:
2412:
2392:
2372:
2342:
2319:
2299:
2279:
2250:
2230:
2210:
2176:
2156:
2106:
2083:
1967:
1915:
1888:
1861:
1828:
1808:
1748:
1737:
1684:
1662:
1642:
1573:
1541:
1518:
1489:
1469:
1434:
1412:
1377:
1357:
1330:
1303:
1271:
1225:
1198:
1171:
1151:
1105:
1093:. The first graph
1083:
1047:
988:
929:
909:
850:
791:
744:
718:
698:
670:
638:
612:
586:
554:
515:
489:
438:
412:
355:
282:
233:
181:
155:
129:
97:
65:super-regular pair
47:in the context of
5644:10.1002/rsa.20907
5347:10.1002/rsa.20362
5270:Sárközy, Gábor N.
5208:Sárközy, Gábor N.
5133:Hamiltonian cycle
5107:{\displaystyle H}
5036:
4980:{\displaystyle n}
4960:{\displaystyle G}
4940:{\displaystyle h}
4920:{\displaystyle H}
4871:{\displaystyle h}
4783:
4727:{\displaystyle h}
4707:{\displaystyle H}
4679:{\displaystyle H}
4639:{\displaystyle k}
4619:{\displaystyle n}
4595:{\displaystyle k}
4570:
4535:{\displaystyle n}
4504:Hamiltonian cycle
4486:
4459:{\displaystyle n}
4377:
4245:
4112:
3984:{\displaystyle v}
3830:{\displaystyle t}
3760:{\displaystyle Y}
3543:{\displaystyle t}
3523:{\displaystyle A}
3503:{\displaystyle y}
3427:{\displaystyle A}
3248:{\displaystyle z}
3143:{\displaystyle t}
3123:{\displaystyle x}
3103:{\displaystyle t}
2967:
2953:{\displaystyle B}
2924:{\displaystyle t}
2904:{\displaystyle q}
2884:{\displaystyle L}
2835:{\displaystyle q}
2813:{\displaystyle q}
2718:{\displaystyle x}
2698:{\displaystyle G}
2656:Choose the image
2644:{\displaystyle L}
2622:{\displaystyle q}
2602:{\displaystyle q}
2579:{\displaystyle x}
2495:{\displaystyle H}
2475:{\displaystyle z}
2455:{\displaystyle z}
2435:{\displaystyle G}
2415:{\displaystyle z}
2395:{\displaystyle H}
2345:{\displaystyle q}
2322:{\displaystyle B}
2302:{\displaystyle L}
2253:{\displaystyle 4}
2233:{\displaystyle H}
2213:{\displaystyle B}
2179:{\displaystyle T}
2109:{\displaystyle G}
2081:
1831:{\displaystyle i}
1722:
1665:{\displaystyle H}
1576:{\displaystyle G}
1544:{\displaystyle H}
1492:{\displaystyle G}
1472:{\displaystyle H}
1380:{\displaystyle H}
1174:{\displaystyle R}
932:{\displaystyle R}
721:{\displaystyle r}
701:{\displaystyle R}
368:and furthermore,
41:regularity method
5709:
5681:
5680:
5678:
5662:
5656:
5655:
5638:(4): 1031–1069.
5627:
5621:
5620:
5588:
5582:
5581:
5541:
5535:
5534:
5524:
5500:
5491:
5490:
5480:
5456:
5450:
5449:
5407:
5401:
5400:
5383:(1–2): 193–211.
5368:
5359:
5358:
5340:
5320:
5311:
5310:
5293:
5274:Szemerédi, Endre
5262:
5251:
5250:
5233:
5212:Szemerédi, Endre
5200:
5157:graphs in 2018.
5113:
5111:
5110:
5105:
5093:
5091:
5090:
5085:
5065:
5050:
5048:
5047:
5042:
5037:
5035:
5021:
5001:
4986:
4984:
4983:
4978:
4966:
4964:
4963:
4958:
4946:
4944:
4943:
4938:
4926:
4924:
4923:
4918:
4906:
4904:
4903:
4898:
4877:
4875:
4874:
4869:
4849:
4847:
4846:
4841:
4836:
4797:
4795:
4794:
4789:
4784:
4782:
4768:
4748:
4733:
4731:
4730:
4725:
4713:
4711:
4710:
4705:
4685:
4683:
4682:
4677:
4645:
4643:
4642:
4637:
4625:
4623:
4622:
4617:
4601:
4599:
4598:
4593:
4581:
4579:
4578:
4573:
4571:
4569:
4558:
4550:
4541:
4539:
4538:
4533:
4497:
4495:
4494:
4489:
4487:
4482:
4474:
4465:
4463:
4462:
4457:
4421:
4419:
4418:
4413:
4402:
4401:
4391:
4364:
4363:
4341:
4339:
4338:
4333:
4331:
4323:
4311:
4309:
4308:
4303:
4292:
4291:
4270:
4269:
4259:
4237:
4235:
4234:
4229:
4227:
4219:
4207:
4205:
4204:
4199:
4197:
4189:
4177:
4175:
4174:
4169:
4167:
4159:
4151:
4137:
4136:
4126:
4111:
4099:
4097:
4096:
4091:
4089:
4088:
4066:
4064:
4063:
4058:
4026:
4024:
4023:
4018:
4007:
4006:
3990:
3988:
3987:
3982:
3970:
3968:
3967:
3962:
3951:
3950:
3926:
3925:
3903:
3901:
3900:
3895:
3893:
3892:
3870:
3868:
3867:
3862:
3836:
3834:
3833:
3828:
3804:
3802:
3801:
3796:
3766:
3764:
3763:
3758:
3746:
3744:
3743:
3738:
3736:
3735:
3713:
3711:
3710:
3705:
3703:
3698:
3697:
3688:
3683:
3682:
3670:
3662:
3654:
3653:
3631:
3629:
3628:
3623:
3586:
3584:
3583:
3578:
3576:
3575:
3549:
3547:
3546:
3541:
3529:
3527:
3526:
3521:
3509:
3507:
3506:
3501:
3489:
3487:
3486:
3481:
3479:
3478:
3463:there is a time
3462:
3460:
3459:
3454:
3433:
3431:
3430:
3425:
3409:
3407:
3406:
3401:
3399:
3398:
3376:
3374:
3373:
3368:
3366:
3358:
3346:
3344:
3343:
3338:
3336:
3335:
3313:
3311:
3310:
3305:
3303:
3302:
3254:
3252:
3251:
3246:
3234:
3232:
3231:
3226:
3209:
3208:
3189:
3187:
3186:
3181:
3170:
3169:
3149:
3147:
3146:
3141:
3129:
3127:
3126:
3121:
3109:
3107:
3106:
3101:
3073:
3071:
3070:
3065:
3054:
3053:
3037:
3035:
3034:
3029:
3011:
3009:
3008:
3003:
2992:
2991:
2981:
2959:
2957:
2956:
2951:
2930:
2928:
2927:
2922:
2910:
2908:
2907:
2902:
2890:
2888:
2887:
2882:
2868:
2866:
2865:
2860:
2858:
2857:
2841:
2839:
2838:
2833:
2819:
2817:
2816:
2811:
2799:
2797:
2796:
2791:
2780:
2779:
2760:
2758:
2757:
2752:
2741:
2740:
2724:
2722:
2721:
2716:
2704:
2702:
2701:
2696:
2684:
2682:
2681:
2676:
2650:
2648:
2647:
2642:
2628:
2626:
2625:
2620:
2608:
2606:
2605:
2600:
2585:
2583:
2582:
2577:
2566:Choose a vertex
2555:
2553:
2552:
2547:
2545:
2544:
2528:
2526:
2525:
2520:
2518:
2517:
2501:
2499:
2498:
2493:
2481:
2479:
2478:
2473:
2461:
2459:
2458:
2453:
2441:
2439:
2438:
2433:
2421:
2419:
2418:
2413:
2401:
2399:
2398:
2393:
2381:
2379:
2378:
2373:
2371:
2370:
2351:
2349:
2348:
2343:
2332:Declare a queue
2328:
2326:
2325:
2320:
2308:
2306:
2305:
2300:
2288:
2286:
2285:
2280:
2259:
2257:
2256:
2251:
2239:
2237:
2236:
2231:
2219:
2217:
2216:
2211:
2185:
2183:
2182:
2177:
2165:
2163:
2162:
2157:
2115:
2113:
2112:
2107:
2092:
2090:
2089:
2084:
2082:
2080:
2079:
2074:
2073:
2064:
2059:
2054:
2053:
2044:
2038:
2034:
2033:
2021:
2020:
2004:
1999:
1998:
1976:
1974:
1973:
1968:
1966:
1965:
1947:
1946:
1924:
1922:
1921:
1916:
1914:
1913:
1897:
1895:
1894:
1889:
1887:
1886:
1870:
1868:
1867:
1862:
1860:
1859:
1837:
1835:
1834:
1829:
1817:
1815:
1814:
1809:
1807:
1802:
1801:
1792:
1784:
1779:
1778:
1769:
1757:
1755:
1754:
1749:
1747:
1746:
1736:
1693:
1691:
1690:
1685:
1683:
1671:
1669:
1668:
1663:
1651:
1649:
1648:
1643:
1641:
1640:
1625:
1608:
1582:
1580:
1579:
1574:
1561:perfect matching
1550:
1548:
1547:
1542:
1527:
1525:
1524:
1519:
1498:
1496:
1495:
1490:
1478:
1476:
1475:
1470:
1457:greedy algorithm
1443:
1441:
1440:
1435:
1433:
1421:
1419:
1418:
1413:
1386:
1384:
1383:
1378:
1366:
1364:
1363:
1358:
1356:
1355:
1339:
1337:
1336:
1331:
1329:
1328:
1312:
1310:
1309:
1304:
1280:
1278:
1277:
1272:
1267:
1266:
1254:
1253:
1234:
1232:
1231:
1226:
1224:
1223:
1207:
1205:
1204:
1199:
1197:
1196:
1180:
1178:
1177:
1172:
1160:
1158:
1157:
1152:
1147:
1146:
1134:
1133:
1114:
1112:
1111:
1106:
1104:
1092:
1090:
1089:
1084:
1082:
1081:
1056:
1054:
1053:
1048:
1046:
1045:
1027:
1026:
1014:
1013:
997:
995:
994:
989:
987:
986:
968:
967:
955:
954:
938:
936:
935:
930:
918:
916:
915:
910:
908:
907:
889:
888:
876:
875:
859:
857:
856:
851:
849:
848:
830:
829:
817:
816:
800:
798:
797:
792:
753:
751:
750:
745:
727:
725:
724:
719:
707:
705:
704:
699:
679:
677:
676:
671:
647:
645:
644:
639:
621:
619:
618:
613:
595:
593:
592:
587:
563:
561:
560:
555:
524:
522:
521:
516:
498:
496:
495:
490:
488:
480:
447:
445:
444:
439:
421:
419:
418:
413:
411:
403:
364:
362:
361:
356:
354:
346:
341:
333:
291:
289:
288:
283:
281:
273:
262:
254:
242:
240:
239:
234:
232:
224:
213:
205:
190:
188:
187:
182:
164:
162:
161:
156:
138:
136:
135:
130:
106:
104:
103:
98:
29:Gábor N. Sárközy
5717:
5716:
5712:
5711:
5710:
5708:
5707:
5706:
5687:
5686:
5685:
5684:
5667:Böttcher, Julia
5664:
5663:
5659:
5629:
5628:
5624:
5590:
5589:
5585:
5543:
5542:
5538:
5502:
5501:
5494:
5458:
5457:
5453:
5409:
5408:
5404:
5370:
5369:
5362:
5322:
5321:
5314:
5264:
5263:
5254:
5202:
5201:
5186:
5181:
5124:
5096:
5095:
5053:
5052:
5022:
5002:
4989:
4988:
4969:
4968:
4949:
4948:
4929:
4928:
4909:
4908:
4880:
4879:
4860:
4859:
4800:
4799:
4769:
4749:
4736:
4735:
4716:
4715:
4696:
4695:
4668:
4667:
4652:
4628:
4627:
4608:
4607:
4584:
4583:
4559:
4551:
4544:
4543:
4524:
4523:
4522:Every graph on
4506:, generalizing
4475:
4468:
4467:
4448:
4447:
4440:
4432:
4393:
4355:
4344:
4343:
4314:
4313:
4283:
4261:
4240:
4239:
4210:
4209:
4180:
4179:
4128:
4102:
4101:
4080:
4069:
4068:
4037:
4036:
4033:
4027:were embedded.
3998:
3993:
3992:
3973:
3972:
3942:
3917:
3906:
3905:
3884:
3873:
3872:
3847:
3846:
3843:
3819:
3818:
3811:
3769:
3768:
3749:
3748:
3727:
3716:
3715:
3689:
3674:
3645:
3634:
3633:
3602:
3601:
3593:
3561:
3556:
3555:
3532:
3531:
3512:
3511:
3492:
3491:
3470:
3465:
3464:
3439:
3438:
3416:
3415:
3384:
3379:
3378:
3349:
3348:
3327:
3316:
3315:
3294:
3265:
3264:
3261:
3237:
3236:
3200:
3195:
3194:
3161:
3156:
3155:
3132:
3131:
3112:
3111:
3092:
3091:
3088:
3080:
3045:
3040:
3039:
3014:
3013:
2983:
2962:
2961:
2942:
2941:
2938:
2913:
2912:
2893:
2892:
2873:
2872:
2849:
2844:
2843:
2824:
2823:
2802:
2801:
2771:
2766:
2765:
2732:
2727:
2726:
2707:
2706:
2705:for the vertex
2687:
2686:
2658:
2657:
2633:
2632:
2611:
2610:
2591:
2590:
2568:
2567:
2563:
2536:
2531:
2530:
2509:
2504:
2503:
2484:
2483:
2464:
2463:
2444:
2443:
2424:
2423:
2404:
2403:
2384:
2383:
2362:
2357:
2356:
2334:
2333:
2311:
2310:
2291:
2290:
2265:
2264:
2260:from each other
2242:
2241:
2222:
2221:
2202:
2201:
2197:
2192:
2168:
2167:
2118:
2117:
2098:
2097:
2065:
2045:
2039:
2025:
2012:
2005:
1987:
1982:
1981:
1957:
1938:
1927:
1926:
1905:
1900:
1899:
1878:
1873:
1872:
1851:
1840:
1839:
1838:. For a vertex
1820:
1819:
1793:
1770:
1760:
1759:
1738:
1696:
1695:
1694:, we can write
1674:
1673:
1654:
1653:
1632:
1593:
1592:
1589:
1565:
1564:
1553:buffer vertices
1533:
1532:
1501:
1500:
1481:
1480:
1461:
1460:
1450:
1424:
1423:
1389:
1388:
1369:
1368:
1347:
1342:
1341:
1320:
1315:
1314:
1283:
1282:
1258:
1245:
1237:
1236:
1215:
1210:
1209:
1188:
1183:
1182:
1163:
1162:
1138:
1125:
1117:
1116:
1095:
1094:
1073:
1059:
1058:
1037:
1018:
1005:
1000:
999:
978:
959:
946:
941:
940:
921:
920:
899:
880:
867:
862:
861:
840:
821:
808:
803:
802:
756:
755:
730:
729:
710:
709:
690:
689:
686:
650:
649:
624:
623:
598:
597:
566:
565:
531:
530:
501:
500:
450:
449:
424:
423:
373:
372:
300:
299:
245:
244:
196:
195:
167:
166:
141:
140:
109:
108:
77:
76:
73:
61:
33:Endre Szemerédi
17:
12:
11:
5:
5715:
5713:
5705:
5704:
5699:
5689:
5688:
5683:
5682:
5665:Allen, Peter;
5657:
5622:
5603:(3): 167–176.
5583:
5556:(3): 241–255.
5536:
5515:(1): 255–269.
5492:
5471:(2): 269–282.
5451:
5402:
5360:
5331:(3): 275–367.
5312:
5284:(3): 297–312,
5252:
5224:(1): 109–123,
5183:
5182:
5180:
5177:
5162:Julia Böttcher
5123:
5120:
5116:
5115:
5103:
5083:
5080:
5077:
5074:
5071:
5068:
5064:
5060:
5040:
5034:
5031:
5028:
5025:
5020:
5017:
5014:
5011:
5008:
5005:
4999:
4996:
4976:
4956:
4936:
4916:
4896:
4893:
4890:
4887:
4867:
4852:
4851:
4839:
4835:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4810:
4807:
4787:
4781:
4778:
4775:
4772:
4767:
4764:
4761:
4758:
4755:
4752:
4746:
4743:
4723:
4703:
4675:
4660:Raphael Yuster
4651:
4648:
4635:
4615:
4604:
4603:
4591:
4568:
4565:
4562:
4557:
4554:
4531:
4485:
4481:
4478:
4455:
4439:
4436:
4431:
4428:
4411:
4408:
4405:
4400:
4396:
4390:
4387:
4384:
4380:
4376:
4373:
4370:
4367:
4362:
4358:
4354:
4351:
4330:
4326:
4322:
4301:
4298:
4295:
4290:
4286:
4282:
4279:
4276:
4273:
4268:
4264:
4258:
4255:
4252:
4248:
4226:
4222:
4218:
4196:
4192:
4188:
4166:
4162:
4158:
4154:
4150:
4146:
4143:
4140:
4135:
4131:
4125:
4122:
4119:
4115:
4110:
4087:
4083:
4079:
4076:
4056:
4053:
4050:
4047:
4044:
4032:
4029:
4016:
4013:
4010:
4005:
4001:
3980:
3960:
3957:
3954:
3949:
3945:
3941:
3938:
3935:
3932:
3929:
3924:
3920:
3916:
3913:
3891:
3887:
3883:
3880:
3860:
3857:
3854:
3842:
3839:
3826:
3810:
3807:
3794:
3791:
3788:
3785:
3782:
3779:
3776:
3756:
3734:
3730:
3726:
3723:
3702:
3696:
3692:
3687:
3681:
3677:
3673:
3669:
3665:
3661:
3657:
3652:
3648:
3644:
3641:
3621:
3618:
3615:
3612:
3609:
3598:union-bounding
3592:
3589:
3574:
3571:
3568:
3564:
3552:
3551:
3539:
3519:
3499:
3477:
3473:
3452:
3449:
3446:
3435:
3423:
3397:
3394:
3391:
3387:
3365:
3361:
3357:
3334:
3330:
3326:
3323:
3301:
3297:
3293:
3290:
3287:
3284:
3281:
3278:
3275:
3272:
3260:
3257:
3256:
3255:
3244:
3224:
3221:
3218:
3215:
3212:
3207:
3203:
3191:
3179:
3176:
3173:
3168:
3164:
3139:
3119:
3099:
3087:
3084:
3079:
3076:
3063:
3060:
3057:
3052:
3048:
3027:
3024:
3021:
3001:
2998:
2995:
2990:
2986:
2980:
2977:
2974:
2970:
2949:
2937:
2934:
2933:
2932:
2920:
2911:, update time
2900:
2880:
2869:
2856:
2852:
2831:
2820:
2809:
2789:
2786:
2783:
2778:
2774:
2762:
2750:
2747:
2744:
2739:
2735:
2714:
2694:
2674:
2671:
2668:
2665:
2654:
2653:
2652:
2640:
2629:
2618:
2598:
2575:
2562:
2559:
2558:
2557:
2543:
2539:
2516:
2512:
2491:
2471:
2451:
2431:
2411:
2391:
2369:
2365:
2353:
2341:
2330:
2318:
2298:
2278:
2275:
2272:
2261:
2249:
2229:
2209:
2196:
2193:
2191:
2188:
2175:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2125:
2105:
2094:
2093:
2078:
2072:
2068:
2063:
2058:
2052:
2048:
2043:
2037:
2032:
2028:
2024:
2019:
2015:
2011:
2008:
2002:
1997:
1994:
1990:
1964:
1960:
1956:
1953:
1950:
1945:
1941:
1937:
1934:
1912:
1908:
1885:
1881:
1858:
1854:
1850:
1847:
1827:
1806:
1800:
1796:
1791:
1787:
1783:
1777:
1773:
1768:
1745:
1741:
1735:
1732:
1729:
1725:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1682:
1661:
1639:
1635:
1631:
1628:
1624:
1620:
1617:
1614:
1611:
1607:
1603:
1600:
1588:
1585:
1572:
1540:
1517:
1514:
1511:
1508:
1488:
1468:
1449:
1446:
1432:
1411:
1408:
1405:
1402:
1399:
1396:
1376:
1354:
1350:
1327:
1323:
1302:
1299:
1296:
1293:
1290:
1270:
1265:
1261:
1257:
1252:
1248:
1244:
1222:
1218:
1195:
1191:
1170:
1150:
1145:
1141:
1137:
1132:
1128:
1124:
1103:
1080:
1076:
1072:
1069:
1066:
1044:
1040:
1036:
1033:
1030:
1025:
1021:
1017:
1012:
1008:
985:
981:
977:
974:
971:
966:
962:
958:
953:
949:
928:
906:
902:
898:
895:
892:
887:
883:
879:
874:
870:
847:
843:
839:
836:
833:
828:
824:
820:
815:
811:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
743:
740:
737:
717:
697:
688:Given a graph
685:
682:
669:
666:
663:
660:
657:
637:
634:
631:
611:
608:
605:
585:
582:
579:
576:
573:
553:
550:
547:
544:
541:
538:
527:
526:
514:
511:
508:
487:
483:
479:
475:
472:
469:
466:
463:
460:
457:
437:
434:
431:
410:
406:
402:
398:
395:
392:
389:
386:
383:
380:
366:
365:
353:
349:
345:
340:
336:
332:
328:
325:
322:
319:
316:
313:
310:
307:
293:
292:
280:
276:
272:
268:
265:
261:
257:
253:
231:
227:
223:
219:
216:
212:
208:
204:
180:
177:
174:
154:
151:
148:
128:
125:
122:
119:
116:
96:
93:
90:
87:
84:
72:
69:
60:
57:
15:
13:
10:
9:
6:
4:
3:
2:
5714:
5703:
5700:
5698:
5695:
5694:
5692:
5677:
5672:
5668:
5661:
5658:
5653:
5649:
5645:
5641:
5637:
5633:
5626:
5623:
5618:
5614:
5610:
5606:
5602:
5598:
5594:
5587:
5584:
5579:
5575:
5571:
5567:
5563:
5559:
5555:
5551:
5547:
5540:
5537:
5532:
5528:
5523:
5518:
5514:
5510:
5506:
5499:
5497:
5493:
5488:
5484:
5479:
5474:
5470:
5466:
5462:
5455:
5452:
5447:
5443:
5439:
5435:
5431:
5427:
5423:
5419:
5418:
5413:
5406:
5403:
5398:
5394:
5390:
5386:
5382:
5378:
5374:
5367:
5365:
5361:
5356:
5352:
5348:
5344:
5339:
5334:
5330:
5326:
5319:
5317:
5313:
5309:
5305:
5301:
5297:
5292:
5287:
5283:
5279:
5275:
5271:
5267:
5266:Komlós, János
5261:
5259:
5257:
5253:
5249:
5245:
5241:
5237:
5232:
5227:
5223:
5219:
5218:
5217:Combinatorica
5213:
5209:
5205:
5204:Komlós, János
5199:
5197:
5195:
5193:
5191:
5189:
5185:
5178:
5176:
5175:
5171:
5167:
5163:
5158:
5156:
5151:
5149:
5148:Peter Keevash
5145:
5142:
5138:
5134:
5130:
5121:
5119:
5101:
5078:
5072:
5069:
5066:
5062:
5058:
5038:
5029:
5023:
5018:
5015:
5009:
5003:
4997:
4994:
4974:
4954:
4934:
4914:
4891:
4885:
4865:
4857:
4856:
4855:
4837:
4833:
4829:
4820:
4814:
4811:
4808:
4785:
4776:
4770:
4765:
4762:
4756:
4750:
4744:
4741:
4721:
4701:
4693:
4692:
4691:
4689:
4673:
4666:to arbitrary
4665:
4661:
4657:
4649:
4647:
4633:
4626:(for a fixed
4613:
4589:
4582:contains the
4566:
4563:
4560:
4555:
4552:
4529:
4521:
4520:
4519:
4517:
4513:
4509:
4505:
4501:
4498:contains the
4483:
4479:
4476:
4453:
4445:
4437:
4435:
4429:
4427:
4425:
4406:
4398:
4394:
4388:
4385:
4382:
4378:
4368:
4360:
4356:
4352:
4349:
4324:
4296:
4288:
4284:
4280:
4274:
4266:
4262:
4256:
4253:
4250:
4246:
4220:
4190:
4160:
4152:
4141:
4133:
4129:
4123:
4120:
4117:
4113:
4085:
4081:
4077:
4074:
4054:
4051:
4048:
4045:
4042:
4030:
4028:
4011:
4003:
3999:
3978:
3955:
3947:
3943:
3939:
3930:
3922:
3918:
3911:
3889:
3885:
3881:
3878:
3858:
3855:
3852:
3840:
3838:
3824:
3816:
3815:initial phase
3808:
3806:
3789:
3786:
3783:
3780:
3777:
3754:
3732:
3728:
3724:
3721:
3694:
3690:
3679:
3675:
3671:
3663:
3655:
3650:
3646:
3642:
3639:
3619:
3616:
3613:
3610:
3607:
3599:
3590:
3588:
3572:
3569:
3566:
3562:
3537:
3517:
3497:
3475:
3471:
3450:
3447:
3444:
3436:
3421:
3413:
3412:
3411:
3395:
3392:
3389:
3385:
3359:
3332:
3328:
3324:
3321:
3299:
3295:
3291:
3288:
3285:
3282:
3279:
3276:
3273:
3270:
3258:
3242:
3219:
3216:
3213:
3205:
3201:
3192:
3174:
3166:
3162:
3153:
3152:
3151:
3137:
3117:
3097:
3085:
3083:
3077:
3075:
3058:
3050:
3046:
3025:
3022:
3019:
2996:
2988:
2984:
2978:
2975:
2972:
2968:
2947:
2935:
2918:
2898:
2878:
2870:
2854:
2850:
2829:
2821:
2807:
2784:
2776:
2772:
2763:
2745:
2737:
2733:
2712:
2692:
2669:
2663:
2655:
2638:
2630:
2616:
2596:
2589:If the queue
2588:
2587:
2573:
2565:
2564:
2560:
2541:
2537:
2514:
2510:
2489:
2469:
2449:
2429:
2409:
2389:
2367:
2363:
2354:
2339:
2331:
2316:
2296:
2276:
2270:
2262:
2247:
2227:
2207:
2199:
2198:
2194:
2189:
2187:
2173:
2150:
2144:
2135:
2129:
2126:
2123:
2103:
2070:
2066:
2050:
2046:
2030:
2026:
2022:
2017:
2013:
2006:
2000:
1995:
1992:
1988:
1980:
1979:
1978:
1962:
1958:
1954:
1951:
1948:
1943:
1939:
1935:
1932:
1910:
1906:
1883:
1879:
1856:
1852:
1848:
1845:
1825:
1798:
1794:
1785:
1775:
1771:
1743:
1739:
1733:
1730:
1727:
1723:
1719:
1716:
1713:
1707:
1701:
1659:
1637:
1633:
1629:
1626:
1615:
1609:
1601:
1598:
1586:
1584:
1570:
1562:
1558:
1554:
1538:
1529:
1512:
1506:
1486:
1466:
1458:
1455:
1447:
1445:
1406:
1400:
1374:
1367:. If a graph
1352:
1348:
1325:
1321:
1297:
1294:
1291:
1263:
1259:
1255:
1250:
1246:
1220:
1216:
1193:
1189:
1168:
1143:
1139:
1135:
1130:
1126:
1078:
1074:
1070:
1067:
1064:
1042:
1038:
1034:
1031:
1028:
1023:
1019:
1015:
1010:
1006:
983:
979:
975:
972:
969:
964:
960:
956:
951:
947:
926:
904:
900:
896:
893:
890:
885:
881:
877:
872:
868:
845:
841:
837:
834:
831:
826:
822:
818:
813:
809:
785:
782:
776:
773:
767:
764:
761:
738:
735:
715:
695:
683:
681:
664:
661:
658:
635:
632:
629:
609:
606:
603:
580:
577:
574:
548:
545:
542:
536:
512:
509:
506:
481:
473:
470:
464:
458:
455:
435:
432:
429:
404:
396:
393:
387:
381:
378:
371:
370:
369:
347:
334:
326:
323:
317:
314:
311:
305:
298:
297:
296:
274:
266:
263:
255:
225:
217:
214:
206:
194:
193:
192:
178:
175:
172:
152:
149:
146:
123:
120:
117:
91:
88:
85:
70:
68:
66:
58:
56:
54:
50:
46:
42:
38:
34:
30:
26:
22:
21:blow-up lemma
5660:
5635:
5631:
5625:
5600:
5596:
5586:
5553:
5549:
5539:
5512:
5508:
5468:
5464:
5454:
5424:(1): 43–60.
5421:
5415:
5405:
5380:
5376:
5328:
5324:
5291:math/9612213
5281:
5277:
5221:
5215:
5159:
5152:
5146:
5125:
5117:
4853:
4653:
4605:
4516:Paul Seymour
4441:
4433:
4430:Applications
4034:
3844:
3814:
3812:
3594:
3553:
3262:
3089:
3081:
2939:
2289:) in a list
2095:
1590:
1552:
1530:
1451:
1448:Proof Sketch
687:
680:is an edge.
528:
367:
294:
74:
64:
62:
25:János Komlós
23:, proved by
20:
18:
5129:graph power
4646:) in 1998.
4424:union-bound
2442:the vertex
191:satisfying
5691:Categories
5676:1612.00622
5179:References
5141:randomized
4444:Lajos PĂłsa
4100:such that
3550:was small.
3437:for every
3347:such that
1559:to find a
1454:randomized
648:such that
5652:119737272
5617:1097-0118
5570:1469-2163
5531:0012-365X
5487:0095-8956
5438:0219-3094
5397:1098-2418
5338:1011.1355
5070:−
5024:χ
5016:−
5004:χ
4998:≥
4812:−
4798:contains
4771:χ
4763:−
4751:χ
4745:≥
4656:Noga Alon
4654:In 1995,
4442:In 1962,
4386:∈
4379:⋃
4375:∖
4254:∈
4247:⋃
4121:∈
4114:⋃
4078:⊆
4052:≤
4046:≤
3940:⊆
3912:ϕ
3882:∈
3856:∈
3676:δ
3672:≥
3643:⊆
3617:≤
3611:≤
3448:∈
3325:⊆
3292:⊆
3280:≤
3274:≤
3263:Consider
3023:∈
2976:∈
2969:⋃
2664:ϕ
2274:∖
2142:→
2124:ϕ
1955:∈
1936:∈
1849:∈
1731:≤
1724:⋃
1630:∑
1410:Δ
1407:≤
1395:Δ
1298:δ
1292:ε
1071:⋃
1032:…
998:of sizes
973:…
894:…
835:…
780:Δ
774:δ
768:ε
762:ε
742:Δ
736:δ
708:of order
633:∈
607:∈
510:∈
474:δ
459:
433:∈
397:δ
382:
327:δ
267:ε
218:ε
176:⊂
150:⊂
124:δ
118:ε
49:embedding
5578:27736891
3845:For any
3530:at time
3110:that if
1818:for all
1652:. Since
1587:Notation
1281:with an
499:for all
422:for all
295:we have
5446:9802487
5355:1395608
5308:1635264
5248:6720143
5240:1466579
5155:rainbow
4688:factors
4512:theorem
3190:are bad
3150:, then
1898:denote
75:A pair
5650:
5615:
5576:
5568:
5529:
5485:
5444:
5436:
5395:
5353:
5306:
5246:
5238:
5170:random
5166:sparse
5137:factor
4500:square
3410:where
3314:, and
2329:first.
1925:. For
1871:, let
53:degree
31:, and
5671:arXiv
5648:S2CID
5574:S2CID
5442:S2CID
5351:S2CID
5333:arXiv
5286:arXiv
5244:S2CID
5131:of a
4967:with
4927:with
4714:with
4508:Dirac
4502:of a
3747:with
1758:with
1479:into
1387:with
596:with
529:Here
5613:ISSN
5566:ISSN
5527:ISSN
5483:ISSN
5434:ISSN
5393:ISSN
5172:and
4658:and
4153:<
4067:and
3871:and
3714:and
1340:and
1208:and
622:and
471:>
448:and
394:>
324:>
264:>
243:and
215:>
165:and
19:The
5640:doi
5605:doi
5558:doi
5517:doi
5513:235
5473:doi
5426:doi
5385:doi
5343:doi
5296:doi
5226:doi
4510:'s
3510:in
3038:to
2891:or
2685:in
2482:in
1161:of
919:of
456:deg
379:deg
5693::
5646:.
5636:56
5634:.
5611:.
5601:29
5599:.
5595:.
5572:.
5564:.
5552:.
5548:.
5525:.
5507:.
5495:^
5481:.
5469:66
5467:.
5463:.
5440:.
5432:.
5420:.
5414:.
5391:.
5379:.
5375:.
5363:^
5349:.
5341:.
5329:39
5327:.
5315:^
5304:MR
5302:,
5294:,
5282:12
5280:,
5272:;
5268:;
5255:^
5242:,
5236:MR
5234:,
5222:17
5220:,
5210:;
5206:;
5187:^
4353::=
4178:.
3632:,
2502:.
2116:.
1977:,
1583:.
67:.
55:.
27:,
5679:.
5673::
5654:.
5642::
5619:.
5607::
5580:.
5560::
5554:4
5533:.
5519::
5489:.
5475::
5448:.
5428::
5422:2
5399:.
5387::
5381:9
5357:.
5345::
5335::
5298::
5288::
5228::
5114:.
5102:H
5082:)
5079:h
5076:(
5073:c
5067:h
5063:/
5059:n
5039:n
5033:)
5030:H
5027:(
5019:1
5013:)
5010:H
5007:(
4995:d
4975:n
4955:G
4935:h
4915:H
4895:)
4892:h
4889:(
4886:c
4866:h
4838:h
4834:/
4830:n
4827:)
4824:)
4821:1
4818:(
4815:o
4809:1
4806:(
4786:n
4780:)
4777:H
4774:(
4766:1
4760:)
4757:H
4754:(
4742:d
4722:h
4702:H
4686:-
4674:H
4634:k
4614:n
4590:k
4567:1
4564:+
4561:k
4556:n
4553:k
4530:n
4484:3
4480:n
4477:2
4454:n
4410:)
4407:T
4404:(
4399:z
4395:F
4389:S
4383:z
4372:)
4369:T
4366:(
4361:i
4357:V
4350:A
4329:|
4325:S
4321:|
4300:)
4297:T
4294:(
4289:i
4285:V
4281:=
4278:)
4275:T
4272:(
4267:z
4263:F
4257:S
4251:z
4225:|
4221:S
4217:|
4195:|
4191:S
4187:|
4165:|
4161:S
4157:|
4149:|
4145:)
4142:T
4139:(
4134:z
4130:F
4124:S
4118:z
4109:|
4086:i
4082:X
4075:S
4055:r
4049:i
4043:1
4015:)
4012:x
4009:(
4004:H
4000:N
3979:v
3959:)
3956:v
3953:(
3948:G
3944:N
3937:)
3934:)
3931:x
3928:(
3923:H
3919:N
3915:(
3890:x
3886:V
3879:v
3859:B
3853:x
3825:t
3793:)
3790:A
3787:,
3784:Y
3781:,
3778:i
3775:(
3755:Y
3733:i
3729:V
3725:=
3722:A
3701:|
3695:i
3691:X
3686:|
3680:Q
3668:|
3664:Y
3660:|
3656:,
3651:i
3647:X
3640:Y
3620:r
3614:i
3608:1
3573:Y
3570:,
3567:A
3563:E
3538:t
3518:A
3498:y
3476:y
3472:t
3451:Y
3445:y
3422:A
3396:Y
3393:,
3390:A
3386:E
3364:|
3360:A
3356:|
3333:i
3329:V
3322:A
3300:i
3296:X
3289:Y
3286:,
3283:r
3277:i
3271:1
3243:z
3223:)
3220:1
3217:+
3214:t
3211:(
3206:z
3202:F
3178:)
3175:t
3172:(
3167:x
3163:F
3138:t
3118:x
3098:t
3062:)
3059:T
3056:(
3051:b
3047:F
3026:B
3020:b
3000:)
2997:T
2994:(
2989:b
2985:F
2979:B
2973:b
2948:B
2919:t
2899:q
2879:L
2855:i
2851:X
2830:q
2808:q
2788:)
2785:t
2782:(
2777:z
2773:F
2749:)
2746:t
2743:(
2738:z
2734:F
2713:x
2693:G
2673:)
2670:x
2667:(
2639:L
2617:q
2597:q
2574:x
2556:.
2542:z
2538:V
2515:z
2511:F
2490:H
2470:z
2450:z
2430:G
2410:z
2390:H
2368:z
2364:F
2340:q
2317:B
2297:L
2277:B
2271:H
2248:4
2228:H
2208:B
2174:T
2154:)
2151:H
2148:(
2145:V
2139:)
2136:G
2133:(
2130:V
2127::
2104:G
2077:|
2071:j
2067:V
2062:|
2057:|
2051:i
2047:V
2042:|
2036:)
2031:j
2027:V
2023:,
2018:i
2014:V
2010:(
2007:e
2001:=
1996:y
1993:x
1989:d
1963:j
1959:X
1952:y
1949:,
1944:i
1940:X
1933:x
1911:i
1907:V
1884:x
1880:V
1857:i
1853:X
1846:x
1826:i
1805:|
1799:i
1795:V
1790:|
1786:=
1782:|
1776:i
1772:X
1767:|
1744:i
1740:X
1734:r
1728:i
1720:=
1717:X
1714:=
1711:)
1708:H
1705:(
1702:V
1681:R
1660:H
1638:i
1634:n
1627:=
1623:|
1619:)
1616:G
1613:(
1610:V
1606:|
1602:=
1599:n
1571:G
1539:H
1516:)
1513:1
1510:(
1507:o
1487:G
1467:H
1431:R
1404:)
1401:H
1398:(
1375:H
1353:j
1349:V
1326:i
1322:V
1301:)
1295:,
1289:(
1269:}
1264:j
1260:v
1256:,
1251:i
1247:v
1243:{
1221:j
1217:V
1194:i
1190:V
1169:R
1149:}
1144:j
1140:v
1136:,
1131:i
1127:v
1123:{
1102:R
1079:i
1075:V
1068:=
1065:V
1043:r
1039:n
1035:,
1029:,
1024:2
1020:n
1016:,
1011:1
1007:n
984:r
980:V
976:,
970:,
965:2
961:V
957:,
952:1
948:V
927:R
905:r
901:v
897:,
891:,
886:2
882:v
878:,
873:1
869:v
846:r
842:n
838:,
832:,
827:2
823:n
819:,
814:1
810:n
789:)
786:r
783:,
777:,
771:(
765:=
739:,
716:r
696:R
668:}
665:y
662:,
659:x
656:{
636:Y
630:y
610:X
604:x
584:)
581:y
578:,
575:x
572:(
552:)
549:Y
546:,
543:X
540:(
537:e
525:.
513:B
507:b
486:|
482:A
478:|
468:)
465:b
462:(
436:A
430:a
409:|
405:B
401:|
391:)
388:a
385:(
352:|
348:Y
344:|
339:|
335:X
331:|
321:)
318:Y
315:,
312:X
309:(
306:e
279:|
275:B
271:|
260:|
256:Y
252:|
230:|
226:A
222:|
211:|
207:X
203:|
179:B
173:Y
153:A
147:X
127:)
121:,
115:(
95:)
92:B
89:,
86:A
83:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.