2592:
3251:
2192:
2919:
2587:{\displaystyle {\begin{aligned}&{\text{Denominator}}\\={}&\Pr \left({\overline {B}}_{j1}\mid \bigwedge _{t=2}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdot \Pr \left({\overline {B}}_{j2}\mid \bigwedge _{t=3}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdots \Pr \left({\overline {B}}_{jl}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)\geq \prod _{B\in S_{1}}(1-x(B))\qquad (2)\end{aligned}}}
1872:
3246:{\displaystyle {\begin{aligned}&\Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\\={}&\Pr \left({\overline {A_{1}}}\mid {\overline {A_{2}}}\wedge \cdots {\overline {A_{n}}}\right)\cdot \Pr \left({\overline {A_{2}}}\mid {\overline {A_{3}}}\wedge \cdots {\overline {A_{n}}}\right)\cdots \Pr \left({\overline {A_{n}}}\right)\\\geq {}&\prod _{A\in {\mathcal {A}}}(1-x(A)),\end{aligned}}}
1631:
2181:
965:
1867:{\displaystyle \Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)={\frac {\Pr \left(A\wedge \bigwedge _{B\in S_{1}}{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}{\Pr \left(\bigwedge _{B\in S_{1}}{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}}.}
2782:
28:
allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the
401:
1195:
and gives no method of determining an explicit element of the probability space in which no event occurs. However, algorithmic versions of the local lemma with stronger preconditions are also known (Beck 1991; Czumaj and
Scheideler 2000). More recently, a
2911:
785:
2017:
1403:
820:
1181:
1041:
3418:
By the local lemma, there is a positive probability that none of the bad events occur, meaning that our set contains no pair of adjacent points. This implies that a set satisfying our conditions must exist.
3287:
pairs of adjacent points on the circle. For each pair our chance of picking both points in that pair is at most 1/121 (exactly 1/121 if the two points are of different colors, otherwise 0), so we will take
1620:
1101:
2633:
1962:
523:
3448:
2924:
2197:
1509:
280:
3413:
670:
137:
553:
1533:
1306:
1262:
812:
252:
1449:
582:
2826:
443:
187:
40:
There are several different versions of the lemma. The simplest and most frequently used is the symmetric version given below. A weaker version was proved in 1975 by
2821:
2009:
2625:
678:
1982:
1423:
1326:
1282:
1238:
622:
602:
2176:{\displaystyle {\text{Numerator}}\leq \Pr \left(A\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)=\Pr(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B)).\qquad (1)}
2597:
The inductive assumption can be applied here since each event is conditioned on lesser number of other events, i.e. on a subset of cardinality less than
1331:
960:{\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod _{i\in \{1,\cdot \cdot \cdot ,n\}}(1-x(A_{i})).}
24:
of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The
3279:
To see this, imagine picking a point of each color randomly, with all points equally likely (i.e., having probability 1/11) to be chosen. The 11
3610:
Czumaj, Artur; Scheideler, Christian (2000). "Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma".
1112:
1217:
977:
3623:
3576:
1545:
1197:
2777:{\displaystyle \Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)\prod _{B\in \Gamma (A)-S_{1}}(1-x(B))\leq x(A)}
1052:
2913:. To get the desired probability, we write it in terms of conditional probabilities applying Bayes' theorem repeatedly. Hence,
3272:
different colors in such a way that each color is applied to exactly 11 points. In any such coloring, there must be a set of
1880:
466:
3678:
1454:
396:{\displaystyle {\begin{cases}p<{\frac {(d-1)^{d-1}}{d^{d}}}&d>1\\p<{\tfrac {1}{2}}&d=1\end{cases}}}
456:
A statement of the asymmetric version (which allows for events with different probability bounds) is as follows:
263:= 2.718... is the base of natural logarithms, then there is a nonzero probability that none of the events occurs.
258:
3368:
627:
21:
83:
3428:
1216:
We prove the asymmetric version of the lemma, from which the symmetric version can be derived. By using the
3683:
3635:
528:
41:
1192:
34:
3323:
are both chosen" is dependent only on those pairs of adjacent points which share a color either with
69:
30:
1514:
1287:
1243:
793:
289:
210:
65:
2906:{\displaystyle \Pr \left({\overline {A}}\mid \bigwedge _{B\in S}{\overline {B}}\right)\geq 1-x(A)}
2186:
Expanding the denominator by using Bayes' theorem and then using the inductive assumption, we get
1428:
624:
is not adjacent to events which are mutually independent). If there exists an assignment of reals
3655:
1201:
17:
558:
416:
160:
3572:
1623:
3619:
3598:
3538:
3509:
3342:
itself), each of which is involved with 2 pairs. This means there are 21 pairs other than (
2794:
1987:
780:{\displaystyle \forall A\in {\mathcal {A}}:\Pr(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}
3688:
3564:
3276:
points containing one point of each color but not containing any pair of adjacent points.
2600:
1877:
We bound the numerator and denominator of the above expression separately. For this, let
1205:
57:
1967:
1408:
1311:
1267:
1223:
607:
587:
61:
3672:
3631:
3514:
3497:
45:
3639:
201:
143:
and such that each event is independent of all the other events except for at most
1398:{\displaystyle \Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)}
3358:. The worst that can happen is that these two sets are disjoint, so we can take
971:
The symmetric version follows immediately from the asymmetric version by setting
3586:
1536:
1191:
Note that, as is often the case with probabilistic arguments, this theorem is
139:
be a sequence of events such that each event occurs with probability at most
3640:"Problems and results on 3-chromatic hypergraphs and some related questions"
3560:
3472:
3602:
3654:
Moser, Robin A. (2008). "A constructive proof of the Lovasz Local Lemma".
50:
Problems and results on 3-chromatic hypergraphs and some related questions
3311:, and not at all on whether any other collection of points in the other
3624:
10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-Y
3542:
1176:{\displaystyle {\frac {1}{e}}\leq \left(1-{\frac {1}{d+1}}\right)^{d}.}
3449:"Former doctoral student Robin Moser receives prestigious Gödel Prize"
1405:. The induction here is applied on the size (cardinality) of the set
410:
The threshold in Lemma III is optimal and it implies that the bound
3303:) of points is chosen depends only on what happens in the colors of
64:
for their algorithmic version of the Lovász Local Lemma, which uses
406:
then there is a nonzero probability that none of the events occurs.
192:
then there is a nonzero probability that none of the events occurs.
3660:
3589:. (1991). "An algorithmic approach to the Lovász local lemma, I".
1036:{\displaystyle \forall A\in {\mathcal {A}}:x(A)={\frac {1}{d+1}}}
525:
be a finite set of events in the probability space Ω. For
267:
Lemma II today is usually referred to as "Lovász local lemma".
1511:. We need to show that the inequality holds for any subset of
3647:
Infinite and Finite Sets (to Paul Erdős on his 60th birthday)
1615:{\displaystyle S_{1}=S\cap \Gamma (A),S_{2}=S\setminus S_{1}}
3205:
1539:
given that it holds for all subsets of a lower cardinality.
1520:
1293:
1249:
992:
799:
693:
639:
540:
472:
3315: − 2 colors are chosen. This implies the event "
389:
72:
for finding an outcome in which none of the events occurs.
1096:{\displaystyle p\leq {\frac {1}{d+1}}\cdot {\frac {1}{e}}}
604:
in the dependency graph (In the dependency graph, event
3334:
There are 11 points on the circle sharing a color with
3283:
different events we want to avoid correspond to the 11
1957:{\displaystyle S_{1}=\{B_{j1},B_{j2},\ldots ,B_{jl}\}}
518:{\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}
364:
3371:
2922:
2829:
2797:
2636:
2603:
2195:
2020:
1990:
1970:
1883:
1634:
1548:
1517:
1457:
1431:
1411:
1334:
1314:
1290:
1270:
1246:
1226:
1115:
1055:
980:
823:
796:
681:
630:
610:
590:
561:
531:
469:
419:
283:
213:
163:
86:
3268:points are placed around a circle and colored with
3407:
3245:
2905:
2815:
2776:
2619:
2586:
2175:
2003:
1976:
1956:
1866:
1614:
1527:
1504:{\displaystyle \Pr(A_{i})\leq x\left(A_{i}\right)}
1503:
1443:
1417:
1397:
1320:
1300:
1276:
1256:
1232:
1175:
1095:
1035:
959:
806:
779:
664:
616:
596:
576:
547:
517:
437:
395:
246:
181:
131:
3649:. Vol. II. North-Holland. pp. 609–627.
3151:
3075:
2999:
2930:
2830:
2637:
2451:
2335:
2219:
2084:
2029:
1776:
1686:
1635:
1458:
1335:
824:
701:
790:then the probability of avoiding all events in
3571:(2nd ed.). New York: Wiley-Interscience.
3529:Shearer, J (1985). "On a problem of Spencer".
3498:"Asymptotic lower bounds for Ramsey functions"
8:
1951:
1897:
918:
894:
512:
480:
154:(Lovász and Erdős 1973; published 1975) If
3645:. In A. Hajnal; R. Rado; V. T. Sós (eds.).
76:Statements of the lemma (symmetric version)
53:
3408:{\displaystyle ep(d+1)\approx 0.966<1.}
3362: = 42 in the lemma. This gives
3659:
3513:
3370:
3204:
3203:
3196:
3186:
3164:
3158:
3132:
3126:
3109:
3103:
3089:
3083:
3056:
3050:
3033:
3027:
3013:
3007:
2993:
2970:
2964:
2944:
2938:
2923:
2921:
2867:
2855:
2838:
2828:
2796:
2727:
2701:
2667:
2655:
2635:
2612:
2604:
2602:
2538:
2527:
2505:
2497:
2486:
2470:
2460:
2433:
2425:
2414:
2398:
2388:
2381:
2370:
2354:
2344:
2317:
2309:
2298:
2282:
2272:
2265:
2254:
2238:
2228:
2213:
2201:
2196:
2194:
2115:
2066:
2058:
2047:
2021:
2019:
1995:
1989:
1969:
1942:
1920:
1904:
1888:
1882:
1843:
1835:
1824:
1807:
1799:
1788:
1759:
1751:
1740:
1723:
1715:
1704:
1683:
1665:
1653:
1633:
1606:
1587:
1553:
1547:
1519:
1518:
1516:
1491:
1468:
1456:
1430:
1410:
1365:
1353:
1333:
1313:
1292:
1291:
1289:
1269:
1248:
1247:
1245:
1225:
1164:
1141:
1116:
1114:
1083:
1062:
1054:
1015:
991:
990:
979:
942:
887:
864:
858:
838:
832:
822:
798:
797:
795:
732:
692:
691:
680:
665:{\displaystyle x:{\mathcal {A}}\to [0,1)}
638:
637:
629:
609:
589:
560:
539:
538:
530:
506:
487:
471:
470:
468:
418:
363:
334:
317:
298:
284:
282:
212:
162:
123:
104:
91:
85:
3256:which is what we had intended to prove.
132:{\displaystyle A_{1},A_{2},\dots ,A_{k}}
3440:
2823:. Note that we have essentially proved
1599:
1198:constructive version of the local lemma
20:, if a large number of events are all
1208:requiring no stronger preconditions.
7:
1451:the statement obviously holds since
1187:Constructive versus non-constructive
1218:principle of mathematical induction
548:{\displaystyle A\in {\mathcal {A}}}
3612:Random Structures & Algorithms
3350:) which include the same color as
2708:
2122:
1984:does not depend upon any event in
1964:. First, exploiting the fact that
1568:
1438:
981:
739:
682:
562:
14:
3591:Random Structures and Algorithms
1046:to get the sufficient condition
2570:
2163:
3390:
3378:
3354:, and the same holds true for
3233:
3230:
3224:
3212:
2900:
2894:
2810:
2798:
2771:
2765:
2756:
2753:
2747:
2735:
2717:
2711:
2694:
2688:
2613:
2605:
2577:
2571:
2567:
2564:
2558:
2546:
2170:
2164:
2157:
2154:
2148:
2136:
2131:
2125:
2108:
2102:
2093:
2087:
1577:
1571:
1528:{\displaystyle {\mathcal {A}}}
1474:
1461:
1392:
1386:
1301:{\displaystyle {\mathcal {A}}}
1257:{\displaystyle {\mathcal {A}}}
1009:
1003:
951:
948:
935:
923:
807:{\displaystyle {\mathcal {A}}}
774:
771:
765:
753:
748:
742:
725:
719:
710:
704:
659:
647:
644:
571:
565:
314:
301:
247:{\displaystyle ep(d+1)\leq 1,}
232:
220:
1:
452:Asymmetric Lovász local lemma
3515:10.1016/0012-365x(77)90044-9
3170:
3138:
3115:
3095:
3062:
3039:
3019:
2976:
2950:
2872:
2843:
2672:
2510:
2465:
2438:
2393:
2349:
2322:
2277:
2233:
2071:
1848:
1812:
1764:
1728:
1670:
1444:{\displaystyle S=\emptyset }
1370:
870:
844:
56:). In 2020, Robin Moser and
2627:. From (1) and (2), we get
814:is positive, in particular
200:(Lovász 1977; published by
52:. For other versions, see (
3705:
3473:"ACM SIGACT - Gödel Prize"
577:{\displaystyle \Gamma (A)}
461:Lemma (asymmetric version)
584:denote the neighbours of
438:{\displaystyle epd\leq 1}
182:{\displaystyle 4pd\leq 1}
3569:The probabilistic method
672:to the events such that
68:to provide an efficient
33:, in particular to give
54:Alon & Spencer 2000
3603:10.1002/rsa.3240020402
3409:
3295:Whether a given pair (
3247:
2907:
2817:
2778:
2621:
2588:
2386:
2270:
2177:
2005:
1978:
1958:
1868:
1616:
1529:
1505:
1445:
1419:
1399:
1322:
1302:
1278:
1258:
1234:
1220:we prove that for all
1212:Non-constructive proof
1177:
1097:
1037:
969:
961:
808:
781:
666:
618:
598:
578:
549:
519:
439:
408:
397:
265:
248:
194:
183:
133:
3410:
3248:
2908:
2818:
2816:{\displaystyle [0,1)}
2779:
2622:
2589:
2366:
2250:
2178:
2006:
2004:{\displaystyle S_{2}}
1979:
1959:
1869:
1617:
1530:
1506:
1446:
1420:
1400:
1323:
1303:
1279:
1259:
1235:
1178:
1098:
1038:
962:
809:
782:
667:
619:
599:
579:
550:
520:
458:
440:
398:
269:
249:
195:
184:
149:
134:
3679:Probability theorems
3502:Discrete Mathematics
3496:Spencer, J. (1977).
3429:Shearer's inequality
3369:
2920:
2827:
2795:
2634:
2601:
2193:
2018:
1988:
1968:
1881:
1632:
1546:
1515:
1455:
1429:
1409:
1332:
1312:
1308:that do not include
1288:
1268:
1244:
1224:
1113:
1053:
978:
821:
794:
679:
628:
608:
588:
559:
529:
467:
448:is also sufficient.
417:
281:
211:
161:
84:
70:randomized algorithm
31:probabilistic method
2787:Since the value of
2620:{\displaystyle |S|}
274:(Shearer 1985) If
66:entropy compression
3543:10.1007/BF02579368
3405:
3243:
3241:
3211:
2903:
2866:
2813:
2774:
2734:
2666:
2617:
2584:
2582:
2545:
2504:
2432:
2316:
2173:
2135:
2065:
2001:
1974:
1954:
1864:
1842:
1806:
1758:
1722:
1664:
1612:
1525:
1501:
1441:
1415:
1395:
1364:
1318:
1298:
1274:
1254:
1230:
1173:
1093:
1033:
957:
922:
804:
777:
752:
662:
614:
594:
574:
545:
515:
435:
393:
388:
373:
244:
179:
129:
26:Lovász local lemma
18:probability theory
3192:
3173:
3141:
3118:
3098:
3065:
3042:
3022:
2979:
2953:
2875:
2851:
2846:
2697:
2675:
2651:
2523:
2513:
2482:
2468:
2441:
2410:
2396:
2352:
2325:
2294:
2280:
2236:
2204:
2111:
2074:
2043:
2024:
1977:{\displaystyle A}
1859:
1851:
1820:
1815:
1784:
1767:
1736:
1731:
1700:
1673:
1649:
1418:{\displaystyle S}
1373:
1349:
1321:{\displaystyle A}
1277:{\displaystyle S}
1233:{\displaystyle A}
1157:
1124:
1091:
1078:
1031:
883:
873:
847:
728:
617:{\displaystyle A}
597:{\displaystyle A}
372:
340:
3696:
3665:
3663:
3650:
3644:
3627:
3618:(3–4): 213–237.
3606:
3582:
3565:Spencer, Joel H.
3547:
3546:
3526:
3520:
3519:
3517:
3493:
3487:
3486:
3484:
3483:
3469:
3463:
3462:
3460:
3459:
3445:
3414:
3412:
3411:
3406:
3252:
3250:
3249:
3244:
3242:
3210:
3209:
3208:
3187:
3178:
3174:
3169:
3168:
3159:
3147:
3143:
3142:
3137:
3136:
3127:
3119:
3114:
3113:
3104:
3099:
3094:
3093:
3084:
3071:
3067:
3066:
3061:
3060:
3051:
3043:
3038:
3037:
3028:
3023:
3018:
3017:
3008:
2994:
2985:
2981:
2980:
2975:
2974:
2965:
2954:
2949:
2948:
2939:
2926:
2912:
2910:
2909:
2904:
2881:
2877:
2876:
2868:
2865:
2847:
2839:
2822:
2820:
2819:
2814:
2783:
2781:
2780:
2775:
2733:
2732:
2731:
2681:
2677:
2676:
2668:
2665:
2626:
2624:
2623:
2618:
2616:
2608:
2593:
2591:
2590:
2585:
2583:
2544:
2543:
2542:
2519:
2515:
2514:
2506:
2503:
2502:
2501:
2478:
2477:
2469:
2461:
2447:
2443:
2442:
2434:
2431:
2430:
2429:
2406:
2405:
2397:
2389:
2385:
2380:
2362:
2361:
2353:
2345:
2331:
2327:
2326:
2318:
2315:
2314:
2313:
2290:
2289:
2281:
2273:
2269:
2264:
2246:
2245:
2237:
2229:
2214:
2205:
2202:
2199:
2182:
2180:
2179:
2174:
2134:
2080:
2076:
2075:
2067:
2064:
2063:
2062:
2025:
2022:
2010:
2008:
2007:
2002:
2000:
1999:
1983:
1981:
1980:
1975:
1963:
1961:
1960:
1955:
1950:
1949:
1928:
1927:
1912:
1911:
1893:
1892:
1873:
1871:
1870:
1865:
1860:
1858:
1857:
1853:
1852:
1844:
1841:
1840:
1839:
1816:
1808:
1805:
1804:
1803:
1774:
1773:
1769:
1768:
1760:
1757:
1756:
1755:
1732:
1724:
1721:
1720:
1719:
1684:
1679:
1675:
1674:
1666:
1663:
1621:
1619:
1618:
1613:
1611:
1610:
1592:
1591:
1558:
1557:
1534:
1532:
1531:
1526:
1524:
1523:
1510:
1508:
1507:
1502:
1500:
1496:
1495:
1473:
1472:
1450:
1448:
1447:
1442:
1425:. For base case
1424:
1422:
1421:
1416:
1404:
1402:
1401:
1396:
1379:
1375:
1374:
1366:
1363:
1327:
1325:
1324:
1319:
1307:
1305:
1304:
1299:
1297:
1296:
1283:
1281:
1280:
1275:
1264:and all subsets
1263:
1261:
1260:
1255:
1253:
1252:
1239:
1237:
1236:
1231:
1182:
1180:
1179:
1174:
1169:
1168:
1163:
1159:
1158:
1156:
1142:
1125:
1117:
1102:
1100:
1099:
1094:
1092:
1084:
1079:
1077:
1063:
1042:
1040:
1039:
1034:
1032:
1030:
1016:
996:
995:
966:
964:
963:
958:
947:
946:
921:
879:
875:
874:
869:
868:
859:
848:
843:
842:
833:
813:
811:
810:
805:
803:
802:
786:
784:
783:
778:
751:
697:
696:
671:
669:
668:
663:
643:
642:
623:
621:
620:
615:
603:
601:
600:
595:
583:
581:
580:
575:
554:
552:
551:
546:
544:
543:
524:
522:
521:
516:
511:
510:
492:
491:
476:
475:
444:
442:
441:
436:
402:
400:
399:
394:
392:
391:
374:
365:
341:
339:
338:
329:
328:
327:
299:
253:
251:
250:
245:
188:
186:
185:
180:
138:
136:
135:
130:
128:
127:
109:
108:
96:
95:
35:existence proofs
3704:
3703:
3699:
3698:
3697:
3695:
3694:
3693:
3669:
3668:
3653:
3642:
3630:
3609:
3585:
3579:
3559:
3556:
3551:
3550:
3528:
3527:
3523:
3495:
3494:
3490:
3481:
3479:
3471:
3470:
3466:
3457:
3455:
3447:
3446:
3442:
3437:
3425:
3367:
3366:
3262:
3240:
3239:
3188:
3180:
3179:
3160:
3154:
3128:
3105:
3085:
3082:
3078:
3052:
3029:
3009:
3006:
3002:
2995:
2987:
2986:
2966:
2940:
2937:
2933:
2918:
2917:
2837:
2833:
2825:
2824:
2793:
2792:
2723:
2644:
2640:
2632:
2631:
2599:
2598:
2581:
2580:
2534:
2493:
2459:
2458:
2454:
2421:
2387:
2343:
2342:
2338:
2305:
2271:
2227:
2226:
2222:
2215:
2207:
2206:
2191:
2190:
2054:
2036:
2032:
2016:
2015:
1991:
1986:
1985:
1966:
1965:
1938:
1916:
1900:
1884:
1879:
1878:
1831:
1795:
1783:
1779:
1775:
1747:
1711:
1693:
1689:
1685:
1642:
1638:
1630:
1629:
1622:. We have from
1602:
1583:
1549:
1544:
1543:
1513:
1512:
1487:
1483:
1464:
1453:
1452:
1427:
1426:
1407:
1406:
1342:
1338:
1330:
1329:
1310:
1309:
1286:
1285:
1266:
1265:
1242:
1241:
1222:
1221:
1214:
1193:nonconstructive
1189:
1146:
1134:
1130:
1129:
1111:
1110:
1067:
1051:
1050:
1020:
976:
975:
938:
860:
834:
831:
827:
819:
818:
792:
791:
677:
676:
626:
625:
606:
605:
586:
585:
557:
556:
527:
526:
502:
483:
465:
464:
454:
415:
414:
387:
386:
375:
354:
353:
342:
330:
313:
300:
285:
279:
278:
209:
208:
159:
158:
119:
100:
87:
82:
81:
78:
48:in the article
12:
11:
5:
3702:
3700:
3692:
3691:
3686:
3681:
3671:
3670:
3667:
3666:
3651:
3636:Lovász, László
3628:
3607:
3597:(4): 343–365.
3583:
3577:
3555:
3552:
3549:
3548:
3537:(3): 241–245.
3521:
3488:
3464:
3439:
3438:
3436:
3433:
3432:
3431:
3424:
3421:
3416:
3415:
3404:
3401:
3398:
3395:
3392:
3389:
3386:
3383:
3380:
3377:
3374:
3261:
3258:
3254:
3253:
3238:
3235:
3232:
3229:
3226:
3223:
3220:
3217:
3214:
3207:
3202:
3199:
3195:
3191:
3189:
3185:
3182:
3181:
3177:
3172:
3167:
3163:
3157:
3153:
3150:
3146:
3140:
3135:
3131:
3125:
3122:
3117:
3112:
3108:
3102:
3097:
3092:
3088:
3081:
3077:
3074:
3070:
3064:
3059:
3055:
3049:
3046:
3041:
3036:
3032:
3026:
3021:
3016:
3012:
3005:
3001:
2998:
2996:
2992:
2989:
2988:
2984:
2978:
2973:
2969:
2963:
2960:
2957:
2952:
2947:
2943:
2936:
2932:
2929:
2927:
2925:
2902:
2899:
2896:
2893:
2890:
2887:
2884:
2880:
2874:
2871:
2864:
2861:
2858:
2854:
2850:
2845:
2842:
2836:
2832:
2812:
2809:
2806:
2803:
2800:
2785:
2784:
2773:
2770:
2767:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2737:
2730:
2726:
2722:
2719:
2716:
2713:
2710:
2707:
2704:
2700:
2696:
2693:
2690:
2687:
2684:
2680:
2674:
2671:
2664:
2661:
2658:
2654:
2650:
2647:
2643:
2639:
2615:
2611:
2607:
2595:
2594:
2579:
2576:
2573:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2541:
2537:
2533:
2530:
2526:
2522:
2518:
2512:
2509:
2500:
2496:
2492:
2489:
2485:
2481:
2476:
2473:
2467:
2464:
2457:
2453:
2450:
2446:
2440:
2437:
2428:
2424:
2420:
2417:
2413:
2409:
2404:
2401:
2395:
2392:
2384:
2379:
2376:
2373:
2369:
2365:
2360:
2357:
2351:
2348:
2341:
2337:
2334:
2330:
2324:
2321:
2312:
2308:
2304:
2301:
2297:
2293:
2288:
2285:
2279:
2276:
2268:
2263:
2260:
2257:
2253:
2249:
2244:
2241:
2235:
2232:
2225:
2221:
2218:
2216:
2212:
2209:
2208:
2200:
2198:
2184:
2183:
2172:
2169:
2166:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2133:
2130:
2127:
2124:
2121:
2118:
2114:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2079:
2073:
2070:
2061:
2057:
2053:
2050:
2046:
2042:
2039:
2035:
2031:
2028:
1998:
1994:
1973:
1953:
1948:
1945:
1941:
1937:
1934:
1931:
1926:
1923:
1919:
1915:
1910:
1907:
1903:
1899:
1896:
1891:
1887:
1875:
1874:
1863:
1856:
1850:
1847:
1838:
1834:
1830:
1827:
1823:
1819:
1814:
1811:
1802:
1798:
1794:
1791:
1787:
1782:
1778:
1772:
1766:
1763:
1754:
1750:
1746:
1743:
1739:
1735:
1730:
1727:
1718:
1714:
1710:
1707:
1703:
1699:
1696:
1692:
1688:
1682:
1678:
1672:
1669:
1662:
1659:
1656:
1652:
1648:
1645:
1641:
1637:
1624:Bayes' theorem
1609:
1605:
1601:
1598:
1595:
1590:
1586:
1582:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1556:
1552:
1522:
1499:
1494:
1490:
1486:
1482:
1479:
1476:
1471:
1467:
1463:
1460:
1440:
1437:
1434:
1414:
1394:
1391:
1388:
1385:
1382:
1378:
1372:
1369:
1362:
1359:
1356:
1352:
1348:
1345:
1341:
1337:
1317:
1295:
1273:
1251:
1229:
1213:
1210:
1188:
1185:
1184:
1183:
1172:
1167:
1162:
1155:
1152:
1149:
1145:
1140:
1137:
1133:
1128:
1123:
1120:
1104:
1103:
1090:
1087:
1082:
1076:
1073:
1070:
1066:
1061:
1058:
1044:
1043:
1029:
1026:
1023:
1019:
1014:
1011:
1008:
1005:
1002:
999:
994:
989:
986:
983:
968:
967:
956:
953:
950:
945:
941:
937:
934:
931:
928:
925:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
886:
882:
878:
872:
867:
863:
857:
854:
851:
846:
841:
837:
830:
826:
801:
788:
787:
776:
773:
770:
767:
764:
761:
758:
755:
750:
747:
744:
741:
738:
735:
731:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
695:
690:
687:
684:
661:
658:
655:
652:
649:
646:
641:
636:
633:
613:
593:
573:
570:
567:
564:
542:
537:
534:
514:
509:
505:
501:
498:
495:
490:
486:
482:
479:
474:
453:
450:
446:
445:
434:
431:
428:
425:
422:
404:
403:
390:
385:
382:
379:
376:
371:
368:
362:
359:
356:
355:
352:
349:
346:
343:
337:
333:
326:
323:
320:
316:
312:
309:
306:
303:
297:
294:
291:
290:
288:
255:
254:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
190:
189:
178:
175:
172:
169:
166:
126:
122:
118:
115:
112:
107:
103:
99:
94:
90:
77:
74:
13:
10:
9:
6:
4:
3:
2:
3701:
3690:
3687:
3685:
3684:Combinatorics
3682:
3680:
3677:
3676:
3674:
3662:
3657:
3652:
3648:
3641:
3637:
3633:
3629:
3625:
3621:
3617:
3613:
3608:
3604:
3600:
3596:
3592:
3588:
3584:
3580:
3578:0-471-37046-0
3574:
3570:
3566:
3562:
3558:
3557:
3553:
3544:
3540:
3536:
3532:
3531:Combinatorica
3525:
3522:
3516:
3511:
3507:
3503:
3499:
3492:
3489:
3478:
3474:
3468:
3465:
3454:
3450:
3444:
3441:
3434:
3430:
3427:
3426:
3422:
3420:
3402:
3399:
3396:
3393:
3387:
3384:
3381:
3375:
3372:
3365:
3364:
3363:
3361:
3357:
3353:
3349:
3345:
3341:
3337:
3332:
3330:
3326:
3322:
3318:
3314:
3310:
3306:
3302:
3298:
3293:
3291:
3286:
3282:
3277:
3275:
3271:
3267:
3259:
3257:
3236:
3227:
3221:
3218:
3215:
3200:
3197:
3193:
3190:
3183:
3175:
3165:
3161:
3155:
3148:
3144:
3133:
3129:
3123:
3120:
3110:
3106:
3100:
3090:
3086:
3079:
3072:
3068:
3057:
3053:
3047:
3044:
3034:
3030:
3024:
3014:
3010:
3003:
2997:
2990:
2982:
2971:
2967:
2961:
2958:
2955:
2945:
2941:
2934:
2928:
2916:
2915:
2914:
2897:
2891:
2888:
2885:
2882:
2878:
2869:
2862:
2859:
2856:
2852:
2848:
2840:
2834:
2807:
2804:
2801:
2791:is always in
2790:
2768:
2762:
2759:
2750:
2744:
2741:
2738:
2728:
2724:
2720:
2714:
2705:
2702:
2698:
2691:
2685:
2682:
2678:
2669:
2662:
2659:
2656:
2652:
2648:
2645:
2641:
2630:
2629:
2628:
2609:
2574:
2561:
2555:
2552:
2549:
2539:
2535:
2531:
2528:
2524:
2520:
2516:
2507:
2498:
2494:
2490:
2487:
2483:
2479:
2474:
2471:
2462:
2455:
2448:
2444:
2435:
2426:
2422:
2418:
2415:
2411:
2407:
2402:
2399:
2390:
2382:
2377:
2374:
2371:
2367:
2363:
2358:
2355:
2346:
2339:
2332:
2328:
2319:
2310:
2306:
2302:
2299:
2295:
2291:
2286:
2283:
2274:
2266:
2261:
2258:
2255:
2251:
2247:
2242:
2239:
2230:
2223:
2217:
2210:
2189:
2188:
2187:
2167:
2160:
2151:
2145:
2142:
2139:
2128:
2119:
2116:
2112:
2105:
2099:
2096:
2090:
2081:
2077:
2068:
2059:
2055:
2051:
2048:
2044:
2040:
2037:
2033:
2026:
2014:
2013:
2012:
1996:
1992:
1971:
1946:
1943:
1939:
1935:
1932:
1929:
1924:
1921:
1917:
1913:
1908:
1905:
1901:
1894:
1889:
1885:
1861:
1854:
1845:
1836:
1832:
1828:
1825:
1821:
1817:
1809:
1800:
1796:
1792:
1789:
1785:
1780:
1770:
1761:
1752:
1748:
1744:
1741:
1737:
1733:
1725:
1716:
1712:
1708:
1705:
1701:
1697:
1694:
1690:
1680:
1676:
1667:
1660:
1657:
1654:
1650:
1646:
1643:
1639:
1628:
1627:
1626:
1625:
1607:
1603:
1596:
1593:
1588:
1584:
1580:
1574:
1565:
1562:
1559:
1554:
1550:
1540:
1538:
1535:of a certain
1497:
1492:
1488:
1484:
1480:
1477:
1469:
1465:
1435:
1432:
1412:
1389:
1383:
1380:
1376:
1367:
1360:
1357:
1354:
1350:
1346:
1343:
1339:
1315:
1271:
1227:
1219:
1211:
1209:
1207:
1203:
1200:was given by
1199:
1194:
1186:
1170:
1165:
1160:
1153:
1150:
1147:
1143:
1138:
1135:
1131:
1126:
1121:
1118:
1109:
1108:
1107:
1088:
1085:
1080:
1074:
1071:
1068:
1064:
1059:
1056:
1049:
1048:
1047:
1027:
1024:
1021:
1017:
1012:
1006:
1000:
997:
987:
984:
974:
973:
972:
954:
943:
939:
932:
929:
926:
915:
912:
909:
906:
903:
900:
897:
891:
888:
884:
880:
876:
865:
861:
855:
852:
849:
839:
835:
828:
817:
816:
815:
768:
762:
759:
756:
745:
736:
733:
729:
722:
716:
713:
707:
698:
688:
685:
675:
674:
673:
656:
653:
650:
634:
631:
611:
591:
568:
535:
532:
507:
503:
499:
496:
493:
488:
484:
477:
462:
457:
451:
449:
432:
429:
426:
423:
420:
413:
412:
411:
407:
383:
380:
377:
369:
366:
360:
357:
350:
347:
344:
335:
331:
324:
321:
318:
310:
307:
304:
295:
292:
286:
277:
276:
275:
273:
268:
264:
262:
261:
241:
238:
235:
229:
226:
223:
217:
214:
207:
206:
205:
203:
199:
193:
176:
173:
170:
167:
164:
157:
156:
155:
153:
148:
146:
142:
124:
120:
116:
113:
110:
105:
101:
97:
92:
88:
75:
73:
71:
67:
63:
60:received the
59:
55:
51:
47:
43:
42:László Lovász
38:
36:
32:
27:
23:
19:
3646:
3615:
3611:
3594:
3590:
3568:
3534:
3530:
3524:
3505:
3501:
3491:
3480:. Retrieved
3476:
3467:
3456:. Retrieved
3452:
3443:
3417:
3359:
3355:
3351:
3347:
3343:
3339:
3335:
3333:
3328:
3324:
3320:
3316:
3312:
3308:
3304:
3300:
3296:
3294:
3289:
3284:
3280:
3278:
3273:
3269:
3265:
3263:
3255:
2788:
2786:
2596:
2185:
1876:
1541:
1215:
1206:Gábor Tardos
1190:
1105:
1045:
970:
789:
460:
459:
455:
447:
409:
405:
271:
270:
266:
259:
256:
202:Joel Spencer
197:
196:
191:
151:
150:
144:
140:
79:
58:Gábor Tardos
49:
39:
25:
15:
3632:Erdős, Paul
3338:(including
2203:Denominator
1537:cardinality
1202:Robin Moser
62:Gödel Prize
22:independent
3673:Categories
3561:Alon, Noga
3554:References
3482:2020-04-20
3477:sigact.org
3458:2020-04-20
3264:Suppose 11
46:Paul Erdős
3661:0810.4812
3508:: 69–76.
3394:≈
3290:p = 1/121
3219:−
3201:∈
3194:∏
3184:≥
3171:¯
3149:⋯
3139:¯
3124:⋯
3121:∧
3116:¯
3101:∣
3096:¯
3073:⋅
3063:¯
3048:⋯
3045:∧
3040:¯
3025:∣
3020:¯
2977:¯
2962:∧
2959:⋯
2956:∧
2951:¯
2889:−
2883:≥
2873:¯
2860:∈
2853:⋀
2849:∣
2844:¯
2760:≤
2742:−
2721:−
2709:Γ
2706:∈
2699:∏
2683:≤
2673:¯
2660:∈
2653:⋀
2649:∣
2553:−
2532:∈
2525:∏
2521:≥
2511:¯
2491:∈
2484:⋀
2480:∣
2466:¯
2449:⋯
2439:¯
2419:∈
2412:⋀
2408:∧
2394:¯
2368:⋀
2364:∣
2350:¯
2333:⋅
2323:¯
2303:∈
2296:⋀
2292:∧
2278:¯
2252:⋀
2248:∣
2234:¯
2143:−
2123:Γ
2120:∈
2113:∏
2097:≤
2072:¯
2052:∈
2045:⋀
2041:∣
2027:≤
2023:Numerator
1933:…
1849:¯
1829:∈
1822:⋀
1818:∣
1813:¯
1793:∈
1786:⋀
1765:¯
1745:∈
1738:⋀
1734:∣
1729:¯
1709:∈
1702:⋀
1698:∧
1671:¯
1658:∈
1651:⋀
1647:∣
1600:∖
1569:Γ
1566:∩
1478:≤
1439:∅
1381:≤
1371:¯
1358:∈
1351:⋀
1347:∣
1139:−
1127:≤
1081:⋅
1060:≤
988:∈
982:∀
930:−
910:⋅
907:⋅
904:⋅
892:∈
885:∏
881:≥
871:¯
856:∧
853:⋯
850:∧
845:¯
760:−
740:Γ
737:∈
730:∏
714:≤
689:∈
683:∀
645:→
563:Γ
536:∈
497:…
430:≤
322:−
308:−
272:Lemma III
236:≤
174:≤
147:of them.
114:…
3638:(1975).
3567:(2000).
3423:See also
3327:or with
198:Lemma II
3587:Beck, J
3453:ethz.ch
3346:,
3299:,
3260:Example
152:Lemma I
3689:Lemmas
3575:
1106:since
463:. Let
257:where
3656:arXiv
3643:(PDF)
3435:Notes
3397:0.966
204:) If
3573:ISBN
3400:<
3319:and
3307:and
1542:Let
1204:and
555:let
361:<
348:>
296:<
80:Let
44:and
3620:doi
3599:doi
3539:doi
3510:doi
1284:of
1240:in
16:In
3675::
3634:;
3616:17
3614:.
3593:.
3563:;
3533:.
3506:20
3504:.
3500:.
3475:.
3451:.
3403:1.
3331:.
3292:.
3152:Pr
3076:Pr
3000:Pr
2931:Pr
2831:Pr
2638:Pr
2452:Pr
2336:Pr
2220:Pr
2085:Pr
2030:Pr
2011:.
1777:Pr
1687:Pr
1636:Pr
1459:Pr
1336:Pr
1328:,
825:Pr
702:Pr
37:.
3664:.
3658::
3626:.
3622::
3605:.
3601::
3595:2
3581:.
3545:.
3541::
3535:5
3518:.
3512::
3485:.
3461:.
3391:)
3388:1
3385:+
3382:d
3379:(
3376:p
3373:e
3360:d
3356:b
3352:a
3348:b
3344:a
3340:a
3336:a
3329:b
3325:a
3321:b
3317:a
3313:n
3309:b
3305:a
3301:b
3297:a
3285:n
3281:n
3274:n
3270:n
3266:n
3237:,
3234:)
3231:)
3228:A
3225:(
3222:x
3216:1
3213:(
3206:A
3198:A
3176:)
3166:n
3162:A
3156:(
3145:)
3134:n
3130:A
3111:3
3107:A
3091:2
3087:A
3080:(
3069:)
3058:n
3054:A
3035:2
3031:A
3015:1
3011:A
3004:(
2991:=
2983:)
2972:n
2968:A
2946:1
2942:A
2935:(
2901:)
2898:A
2895:(
2892:x
2886:1
2879:)
2870:B
2863:S
2857:B
2841:A
2835:(
2811:)
2808:1
2805:,
2802:0
2799:[
2789:x
2772:)
2769:A
2766:(
2763:x
2757:)
2754:)
2751:B
2748:(
2745:x
2739:1
2736:(
2729:1
2725:S
2718:)
2715:A
2712:(
2703:B
2695:)
2692:A
2689:(
2686:x
2679:)
2670:B
2663:S
2657:B
2646:A
2642:(
2614:|
2610:S
2606:|
2578:)
2575:2
2572:(
2568:)
2565:)
2562:B
2559:(
2556:x
2550:1
2547:(
2540:1
2536:S
2529:B
2517:)
2508:B
2499:2
2495:S
2488:B
2475:l
2472:j
2463:B
2456:(
2445:)
2436:B
2427:2
2423:S
2416:B
2403:t
2400:j
2391:B
2383:l
2378:3
2375:=
2372:t
2359:2
2356:j
2347:B
2340:(
2329:)
2320:B
2311:2
2307:S
2300:B
2287:t
2284:j
2275:B
2267:l
2262:2
2259:=
2256:t
2243:1
2240:j
2231:B
2224:(
2211:=
2171:)
2168:1
2165:(
2161:.
2158:)
2155:)
2152:B
2149:(
2146:x
2140:1
2137:(
2132:)
2129:A
2126:(
2117:B
2109:)
2106:A
2103:(
2100:x
2094:)
2091:A
2088:(
2082:=
2078:)
2069:B
2060:2
2056:S
2049:B
2038:A
2034:(
1997:2
1993:S
1972:A
1952:}
1947:l
1944:j
1940:B
1936:,
1930:,
1925:2
1922:j
1918:B
1914:,
1909:1
1906:j
1902:B
1898:{
1895:=
1890:1
1886:S
1862:.
1855:)
1846:B
1837:2
1833:S
1826:B
1810:B
1801:1
1797:S
1790:B
1781:(
1771:)
1762:B
1753:2
1749:S
1742:B
1726:B
1717:1
1713:S
1706:B
1695:A
1691:(
1681:=
1677:)
1668:B
1661:S
1655:B
1644:A
1640:(
1608:1
1604:S
1597:S
1594:=
1589:2
1585:S
1581:,
1578:)
1575:A
1572:(
1563:S
1560:=
1555:1
1551:S
1521:A
1498:)
1493:i
1489:A
1485:(
1481:x
1475:)
1470:i
1466:A
1462:(
1436:=
1433:S
1413:S
1393:)
1390:A
1387:(
1384:x
1377:)
1368:B
1361:S
1355:B
1344:A
1340:(
1316:A
1294:A
1272:S
1250:A
1228:A
1171:.
1166:d
1161:)
1154:1
1151:+
1148:d
1144:1
1136:1
1132:(
1122:e
1119:1
1089:e
1086:1
1075:1
1072:+
1069:d
1065:1
1057:p
1028:1
1025:+
1022:d
1018:1
1013:=
1010:)
1007:A
1004:(
1001:x
998::
993:A
985:A
955:.
952:)
949:)
944:i
940:A
936:(
933:x
927:1
924:(
919:}
916:n
913:,
901:,
898:1
895:{
889:i
877:)
866:n
862:A
840:1
836:A
829:(
800:A
775:)
772:)
769:B
766:(
763:x
757:1
754:(
749:)
746:A
743:(
734:B
726:)
723:A
720:(
717:x
711:)
708:A
705:(
699::
694:A
686:A
660:)
657:1
654:,
651:0
648:[
640:A
635::
632:x
612:A
592:A
572:)
569:A
566:(
541:A
533:A
513:}
508:n
504:A
500:,
494:,
489:1
485:A
481:{
478:=
473:A
433:1
427:d
424:p
421:e
384:1
381:=
378:d
370:2
367:1
358:p
351:1
345:d
336:d
332:d
325:1
319:d
315:)
311:1
305:d
302:(
293:p
287:{
260:e
242:,
239:1
233:)
230:1
227:+
224:d
221:(
218:p
215:e
177:1
171:d
168:p
165:4
145:d
141:p
125:k
121:A
117:,
111:,
106:2
102:A
98:,
93:1
89:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.