2872:
2344:
2081:
122:
Alternatively, the probabilistic method can also be used to guarantee the existence of a desired element in a sample space with a value that is greater than or equal to the calculated expected value, since the non-existence of such element would imply every element in the sample space is less than
2661:
1837:
2859:
This result gives a hint as to why the computation of the chromatic number of a graph is so difficult: even when there are no local reasons (such as small cycles) for a graph to require many colors the chromatic number can still be arbitrarily large.
2339:{\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}
2432:
2056:
1004:
2735:, the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1).
2840:
2717:
1642:
1650:
1303:
1146:
119:. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value.
2409:
666:
2995:
158:), many of the most well known proofs using this method are due to Erdős. The first example below describes one such result from 1947 that gives a proof of a lower bound for the
3071:
Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex
Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296;
2796:
1540:
101:
If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero.
1496:
1450:
505:
852:
572:
460:
398:
314:
770:
711:
540:
428:
258:
1035:
820:
731:
362:
338:
278:
3060:
Elishakoff I., Probabilistic
Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore,
2905:
2656:{\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}
58:
that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for
54:
the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the
1980:
860:
17:
1545:
Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).
1832:{\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1}
2672:
1551:
3048:
2805:
3065:
1197:
3044:
104:
Similarly, showing that the probability is (strictly) less than 1 can be used to prove the existence of an object that does
3076:
2900:
1043:
2922:
2944:
2374:
3106:
580:
2368:
1390:-subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been
3101:
204:
1501:
151:
3012:
2895:
2885:
1462:
1416:
1014:
469:
208:
2762:
3096:
3007:
2072:
825:
545:
433:
127:
1548:
Hence, the total number of colorings that are bad for some (at least one) subgraph is at most
367:
283:
1379:
192:
39:
740:
681:
510:
135:
3029:
2978:
1870:
406:
236:
1382:. Even though it proves (for example) that almost every coloring of the complete graph on
8:
2890:
200:
159:
86:
3033:
2982:
2877:
1368:
1020:
775:
716:
347:
323:
263:
90:
51:
218:
To do so, we color the graph randomly. Color each edge independently with probability
3072:
3061:
2986:
2940:
2871:
1853:
A 1959 paper of Erdős (see reference cited below) addressed the following problem in
155:
3037:
1163:, there exists a coloring satisfying the condition that the number of monochromatic
3017:
2964:
1878:
1406:
The same fact can be proved without probability, using a simple counting argument:
82:
3055:
3025:
2974:
116:
150:
via the probabilistic method (for example, Szele's 1943 result that there exist
463:
185:
131:
112:
74:
226:
of being blue. We calculate the expected number of monochromatic subgraphs on
3090:
1330:
78:
70:
43:
47:
3021:
2969:
2952:
2910:
1854:
1391:
1017:), so the expectation of the sum (the expected number of all monochromatic
1839:, there must be at least one coloring which is not 'bad' for any subgraph.
2051:{\displaystyle {\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}}
66:
55:
31:
999:{\displaystyle \sum _{i=1}^{C(n,r)}E={n \choose r}2^{1-{r \choose 2}}.}
215:
vertices which is monochromatic (every edge colored the same color).
1322:), there must exist a coloring in which there are no monochromatic
111:
Another way to use the probabilistic method is by calculating the
1176:
147:
2802:. We can see that this new graph has no independent set of size
401:
207:
in two colors (say red and blue) so that there is no complete
2712:{\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}
1637:{\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}
2852:
independent sets, and, hence, has chromatic number at least
2835:{\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }
1298:{\displaystyle E={n \choose r}2^{1-{r \choose 2}}<1}
1009:
The sum of expectations is the expectation of the sum (
2798:
vertices that contains only cycles of length at least
2382:
2100:
126:
Common tools used in the probabilistic method include
2808:
2765:
2675:
2435:
2377:
2084:
1983:
1653:
1554:
1504:
1465:
1419:
1200:
1175:-subgraphs in this random coloring is a non-negative
1046:
1023:
863:
828:
778:
743:
719:
684:
583:
548:
513:
472:
436:
409:
370:
350:
326:
286:
266:
239:
2867:
2723:, property 2 holds with a probability of more than
2352:, property 1 holds with a probability of more than
1378:A weakness of this argument is that it is entirely
1141:{\displaystyle E={n \choose r}2^{1-{r \choose 2}}.}
65:This method has now been applied to other areas of
2906:Probabilistic proofs of non-probabilistic theorems
2834:
2790:
2711:
2655:
2403:
2338:
2050:
1831:
1636:
1534:
1490:
1444:
1297:
1140:
1029:
998:
846:
814:
764:
725:
705:
660:
566:
534:
499:
454:
422:
392:
356:
332:
308:
272:
252:
2705:
2473:
2460:
1892:It can be shown that such a graph exists for any
1782:
1769:
1673:
1660:
1574:
1561:
1482:
1469:
1436:
1423:
1248:
1235:
1151:Consider what happens if this value is less than
1094:
1081:
952:
939:
344:otherwise. Note that the number of monochromatic
3088:
2742:has these two properties, we can remove at most
2436:
2085:
2422:be the size of the largest independent set in
2404:{\displaystyle \lceil {\tfrac {n}{2k}}\rceil }
675:comes because there are two possible colors).
195:. We wish to show (for small enough values of
27:Nonconstructive method for mathematical proofs
1815:
1802:
1756:
1743:
1725:
1712:
1700:
1687:
1626:
1613:
1601:
1588:
1525:
1512:
1281:
1268:
1155:. Since the expected number of monochromatic
1127:
1114:
985:
972:
650:
637:
280:vertices from our graph, define the variable
2398:
2378:
713:possible subsets we could have chosen, i.e.
141:
1926:. We show that with positive probability,
1900:, and the proof is reasonably simple. Let
1187:is the only non-negative integer less than
661:{\displaystyle E=2\cdot 2^{-{r \choose 2}}}
1904:be very large and consider a random graph
507:is simply the probability that all of the
3011:
2993:
2968:
2950:
1962:be the number cycles of length less than
3056:Extremal and Probabilistic Combinatorics
1930:satisfies the following two properties:
2939:(2ed). New York: Wiley-Interscience.
2916:
14:
3089:
2935:Alon, Noga; Spencer, Joel H. (2000).
2923:Probabilistic Methods in Combinatorics
2848:can only be partitioned into at least
123:the expected value, a contradiction.
3054:Alon, N and Krivelevich, M (2006).
2901:Method of conditional probabilities
1386:vertices contains no monochromatic
199:) that it is possible to color the
108:satisfy the prescribed properties.
24:
2996:"Graph theory and probability, II"
2464:
1806:
1773:
1747:
1716:
1691:
1664:
1617:
1592:
1565:
1516:
1473:
1427:
1272:
1239:
1118:
1085:
976:
943:
641:
146:Although others before him proved
25:
3118:
1966:. The number of cycles of length
1848:
1498:edges and thus can be colored in
1167:-subgraphs is strictly less than
1159:-subgraphs is strictly less than
2870:
340:vertices is the same color, and
179:
2061:and each of them is present in
1535:{\displaystyle 2^{r \choose 2}}
1308:(which holds, for example, for
678:This holds true for any of the
96:
2953:"Graph theory and probability"
2647:
2641:
2630:
2600:
2565:
2553:
2513:
2501:
2492:
2479:
2451:
2439:
2330:
2324:
2138:
2132:
2019:
2007:
1912:vertices, where every edge in
1763:
1400:
1226:
1223:
1210:
1204:
1171:. The number of monochromatic
1072:
1069:
1056:
1050:
930:
927:
909:
903:
895:
883:
809:
806:
788:
782:
759:
747:
700:
688:
614:
611:
593:
587:
529:
517:
494:
476:
387:
374:
303:
290:
62:, without any possible error.
13:
1:
2929:
2719:Thus, for sufficiently large
1491:{\displaystyle {r \choose 2}}
1445:{\displaystyle {n \choose r}}
1013:of whether the variables are
772:. So we have that the sum of
154:containing a large number of
3082:
2738:Here comes the trick: since
2348:Thus for sufficiently large
500:{\displaystyle X(S_{r}^{i})}
7:
2863:
1947:cycles of length less than
1865:, does there exist a graph
18:Probabilistic combinatorics
10:
3123:
2791:{\displaystyle n'\geq n/2}
1857:: given positive integers
320:if every edge amongst the
42:method, primarily used in
1970:in the complete graph on
847:{\displaystyle S_{r}^{i}}
567:{\displaystyle S_{r}^{i}}
455:{\displaystyle S_{r}^{i}}
430:. For any individual set
364:-subgraphs is the sum of
142:Two examples due to Erdős
3049:The Probabilistic Method
2937:The probabilistic method
2896:Incompressibility method
2886:Interactive proof system
1916:exists with probability
1394:for more than 50 years.
393:{\displaystyle X(S_{r})}
309:{\displaystyle X(S_{r})}
3107:Probabilistic arguments
2731:For sufficiently large
3022:10.4153/CJM-1961-029-9
2970:10.4153/CJM-1959-003-9
2836:
2792:
2753:to obtain a new graph
2713:
2657:
2405:
2340:
2240:
2180:
2052:
1833:
1638:
1536:
1492:
1446:
1299:
1191:). It follows that if
1142:
1031:
1000:
899:
848:
816:
766:
765:{\displaystyle C(n,r)}
727:
707:
706:{\displaystyle C(n,r)}
662:
568:
536:
535:{\displaystyle C(r,2)}
501:
456:
424:
394:
358:
334:
310:
274:
254:
2837:
2793:
2714:
2658:
2406:
2341:
2214:
2154:
2053:
1834:
1639:
1537:
1493:
1447:
1329:By definition of the
1300:
1143:
1032:
1001:
864:
849:
817:
767:
728:
708:
663:
569:
537:
502:
457:
425:
423:{\displaystyle S_{r}}
395:
359:
335:
311:
275:
255:
253:{\displaystyle S_{r}}
230:vertices as follows:
2925:, MIT OpenCourseWare
2917:Additional resources
2806:
2763:
2673:
2433:
2375:
2082:
1981:
1651:
1552:
1502:
1463:
1417:
1409:The total number of
1348:must be bigger than
1333:, this implies that
1198:
1044:
1021:
861:
826:
776:
741:
717:
682:
581:
574:are the same color:
546:
511:
470:
434:
407:
368:
348:
324:
284:
264:
237:
36:probabilistic method
3102:Mathematical proofs
2891:Las Vegas algorithm
2426:. Clearly, we have
2073:Markov's inequality
1873:of length at least
1367:must grow at least
1179:, hence it must be
926:
843:
805:
610:
563:
493:
451:
128:Markov's inequality
87:randomized rounding
2994:Erdős, P. (1961).
2951:Erdős, P. (1959).
2878:Mathematics portal
2832:
2788:
2709:
2653:
2401:
2396:
2336:
2109:
2048:
1829:
1634:
1532:
1488:
1442:
1295:
1138:
1027:
996:
912:
844:
829:
812:
791:
762:
723:
703:
658:
596:
564:
549:
532:
497:
479:
452:
437:
420:
400:over all possible
390:
354:
330:
306:
270:
250:
184:Suppose we have a
156:Hamiltonian cycles
136:Lovász local lemma
91:information theory
3066:978-981-3149-84-7
2826:
2699:
2595:
2572:
2520:
2471:
2395:
2314:
2289:
2267:
2253:
2212:
2152:
2127:
2108:
2065:with probability
2046:
2026:
1940:contains at most
1869:containing only
1813:
1780:
1754:
1723:
1698:
1671:
1624:
1599:
1572:
1523:
1480:
1434:
1352:. In particular,
1279:
1246:
1125:
1092:
1030:{\displaystyle r}
983:
950:
815:{\displaystyle E}
726:{\displaystyle i}
648:
357:{\displaystyle r}
333:{\displaystyle r}
273:{\displaystyle r}
222:of being red and
46:and pioneered by
16:(Redirected from
3114:
3051:. Lecture notes.
3041:
3015:
2990:
2972:
2880:
2875:
2874:
2855:
2851:
2847:
2841:
2839:
2838:
2833:
2831:
2827:
2822:
2814:
2801:
2797:
2795:
2794:
2789:
2784:
2773:
2758:
2752:
2748:
2741:
2734:
2726:
2722:
2718:
2716:
2715:
2710:
2704:
2700:
2698:
2687:
2662:
2660:
2659:
2654:
2634:
2633:
2596:
2588:
2575:
2574:
2573:
2568:
2545:
2535:
2534:
2522:
2521:
2516:
2496:
2478:
2477:
2476:
2463:
2425:
2421:
2410:
2408:
2407:
2402:
2397:
2394:
2383:
2366:
2355:
2351:
2345:
2343:
2342:
2337:
2317:
2316:
2315:
2307:
2291:
2290:
2285:
2274:
2268:
2260:
2255:
2254:
2246:
2239:
2228:
2213:
2205:
2200:
2199:
2190:
2189:
2179:
2168:
2153:
2145:
2128:
2120:
2115:
2111:
2110:
2101:
2070:
2064:
2057:
2055:
2054:
2049:
2047:
2042:
2041:
2032:
2027:
2025:
1993:
1985:
1973:
1969:
1965:
1961:
1950:
1946:
1939:
1929:
1925:
1915:
1911:
1907:
1903:
1899:
1895:
1888:
1884:
1879:chromatic number
1877:, such that the
1876:
1868:
1864:
1860:
1842:
1838:
1836:
1835:
1830:
1822:
1821:
1820:
1819:
1818:
1805:
1787:
1786:
1785:
1772:
1762:
1761:
1760:
1759:
1746:
1732:
1731:
1730:
1729:
1728:
1715:
1705:
1704:
1703:
1690:
1678:
1677:
1676:
1663:
1643:
1641:
1640:
1635:
1633:
1632:
1631:
1630:
1629:
1616:
1606:
1605:
1604:
1591:
1579:
1578:
1577:
1564:
1541:
1539:
1538:
1533:
1531:
1530:
1529:
1528:
1515:
1497:
1495:
1494:
1489:
1487:
1486:
1485:
1472:
1451:
1449:
1448:
1443:
1441:
1440:
1439:
1426:
1404:
1389:
1385:
1374:
1366:
1351:
1347:
1325:
1321:
1314:
1304:
1302:
1301:
1296:
1288:
1287:
1286:
1285:
1284:
1271:
1253:
1252:
1251:
1238:
1222:
1221:
1190:
1186:
1182:
1174:
1170:
1166:
1162:
1158:
1154:
1147:
1145:
1144:
1139:
1134:
1133:
1132:
1131:
1130:
1117:
1099:
1098:
1097:
1084:
1068:
1067:
1036:
1034:
1033:
1028:
1005:
1003:
1002:
997:
992:
991:
990:
989:
988:
975:
957:
956:
955:
942:
925:
920:
898:
878:
853:
851:
850:
845:
842:
837:
821:
819:
818:
813:
804:
799:
771:
769:
768:
763:
736:
732:
730:
729:
724:
712:
710:
709:
704:
674:
667:
665:
664:
659:
657:
656:
655:
654:
653:
640:
609:
604:
573:
571:
570:
565:
562:
557:
541:
539:
538:
533:
506:
504:
503:
498:
492:
487:
461:
459:
458:
453:
450:
445:
429:
427:
426:
421:
419:
418:
399:
397:
396:
391:
386:
385:
363:
361:
360:
355:
343:
339:
337:
336:
331:
319:
315:
313:
312:
307:
302:
301:
279:
277:
276:
271:
259:
257:
256:
251:
249:
248:
229:
225:
221:
214:
198:
191:
175:
83:computer science
81:, as well as in
21:
3122:
3121:
3117:
3116:
3115:
3113:
3112:
3111:
3087:
3086:
3085:
3013:10.1.1.210.6669
2932:
2919:
2876:
2869:
2866:
2853:
2849:
2843:
2815:
2813:
2809:
2807:
2804:
2803:
2799:
2780:
2766:
2764:
2761:
2760:
2754:
2750:
2743:
2739:
2732:
2724:
2720:
2691:
2686:
2682:
2674:
2671:
2670:
2587:
2583:
2579:
2546:
2544:
2540:
2536:
2530:
2526:
2497:
2495:
2491:
2472:
2459:
2458:
2457:
2434:
2431:
2430:
2423:
2419:
2387:
2381:
2376:
2373:
2372:
2369:independent set
2364:
2353:
2349:
2306:
2302:
2298:
2275:
2273:
2269:
2259:
2245:
2241:
2229:
2218:
2204:
2195:
2191:
2185:
2181:
2169:
2158:
2144:
2119:
2099:
2092:
2088:
2083:
2080:
2079:
2066:
2062:
2037:
2033:
2031:
1994:
1986:
1984:
1982:
1979:
1978:
1971:
1967:
1963:
1959:
1948:
1941:
1937:
1927:
1917:
1913:
1909:
1905:
1901:
1897:
1893:
1886:
1882:
1874:
1866:
1862:
1858:
1851:
1846:
1845:
1814:
1801:
1800:
1799:
1792:
1788:
1781:
1768:
1767:
1766:
1755:
1742:
1741:
1740:
1736:
1724:
1711:
1710:
1709:
1699:
1686:
1685:
1684:
1683:
1679:
1672:
1659:
1658:
1657:
1652:
1649:
1648:
1625:
1612:
1611:
1610:
1600:
1587:
1586:
1585:
1584:
1580:
1573:
1560:
1559:
1558:
1553:
1550:
1549:
1542:different ways.
1524:
1511:
1510:
1509:
1505:
1503:
1500:
1499:
1481:
1468:
1467:
1466:
1464:
1461:
1460:
1459:-subgraphs has
1435:
1422:
1421:
1420:
1418:
1415:
1414:
1405:
1401:
1396:
1387:
1383:
1380:nonconstructive
1372:
1353:
1349:
1334:
1323:
1316:
1309:
1280:
1267:
1266:
1265:
1258:
1254:
1247:
1234:
1233:
1232:
1217:
1213:
1199:
1196:
1195:
1188:
1184:
1180:
1172:
1168:
1164:
1160:
1156:
1152:
1126:
1113:
1112:
1111:
1104:
1100:
1093:
1080:
1079:
1078:
1063:
1059:
1045:
1042:
1041:
1037:-subgraphs) is
1022:
1019:
1018:
984:
971:
970:
969:
962:
958:
951:
938:
937:
936:
921:
916:
879:
868:
862:
859:
858:
838:
833:
827:
824:
823:
800:
795:
777:
774:
773:
742:
739:
738:
734:
718:
715:
714:
683:
680:
679:
672:
671:(the factor of
649:
636:
635:
634:
630:
626:
605:
600:
582:
579:
578:
558:
553:
547:
544:
543:
512:
509:
508:
488:
483:
471:
468:
467:
446:
441:
435:
432:
431:
414:
410:
408:
405:
404:
381:
377:
369:
366:
365:
349:
346:
345:
341:
325:
322:
321:
317:
297:
293:
285:
282:
281:
265:
262:
261:
244:
240:
238:
235:
234:
227:
223:
219:
212:
196:
189:
182:
162:
144:
117:random variable
99:
40:nonconstructive
28:
23:
22:
15:
12:
11:
5:
3120:
3110:
3109:
3104:
3099:
3084:
3081:
3080:
3079:
3069:
3058:
3052:
3047:, J. Vondrak.
3042:
2991:
2948:
2931:
2928:
2927:
2926:
2918:
2915:
2914:
2913:
2908:
2903:
2898:
2893:
2888:
2882:
2881:
2865:
2862:
2830:
2825:
2821:
2818:
2812:
2787:
2783:
2779:
2776:
2772:
2769:
2749:vertices from
2729:
2728:
2708:
2703:
2697:
2694:
2690:
2685:
2681:
2678:
2664:
2663:
2652:
2649:
2646:
2643:
2640:
2637:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2594:
2591:
2586:
2582:
2578:
2571:
2567:
2564:
2561:
2558:
2555:
2552:
2549:
2543:
2539:
2533:
2529:
2525:
2519:
2515:
2512:
2509:
2506:
2503:
2500:
2494:
2490:
2487:
2484:
2481:
2475:
2470:
2467:
2462:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2413:
2412:
2400:
2393:
2390:
2386:
2380:
2358:
2357:
2346:
2335:
2332:
2329:
2326:
2323:
2320:
2313:
2310:
2305:
2301:
2297:
2294:
2288:
2284:
2281:
2278:
2272:
2266:
2263:
2258:
2252:
2249:
2244:
2238:
2235:
2232:
2227:
2224:
2221:
2217:
2211:
2208:
2203:
2198:
2194:
2188:
2184:
2178:
2175:
2172:
2167:
2164:
2161:
2157:
2151:
2148:
2143:
2140:
2137:
2134:
2131:
2126:
2123:
2118:
2114:
2107:
2104:
2098:
2095:
2091:
2087:
2059:
2058:
2045:
2040:
2036:
2030:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1992:
1989:
1953:
1952:
1850:
1849:Second example
1847:
1844:
1843:
1841:
1840:
1828:
1825:
1817:
1812:
1809:
1804:
1798:
1795:
1791:
1784:
1779:
1776:
1771:
1765:
1758:
1753:
1750:
1745:
1739:
1735:
1727:
1722:
1719:
1714:
1708:
1702:
1697:
1694:
1689:
1682:
1675:
1670:
1667:
1662:
1656:
1645:
1628:
1623:
1620:
1615:
1609:
1603:
1598:
1595:
1590:
1583:
1576:
1571:
1568:
1563:
1557:
1546:
1543:
1527:
1522:
1519:
1514:
1508:
1484:
1479:
1476:
1471:
1453:
1438:
1433:
1430:
1425:
1413:-subgraphs is
1398:
1397:
1306:
1305:
1294:
1291:
1283:
1278:
1275:
1270:
1264:
1261:
1257:
1250:
1245:
1242:
1237:
1231:
1228:
1225:
1220:
1216:
1212:
1209:
1206:
1203:
1149:
1148:
1137:
1129:
1124:
1121:
1116:
1110:
1107:
1103:
1096:
1091:
1088:
1083:
1077:
1074:
1071:
1066:
1062:
1058:
1055:
1052:
1049:
1026:
1007:
1006:
995:
987:
982:
979:
974:
968:
965:
961:
954:
949:
946:
941:
935:
932:
929:
924:
919:
915:
911:
908:
905:
902:
897:
894:
891:
888:
885:
882:
877:
874:
871:
867:
841:
836:
832:
811:
808:
803:
798:
794:
790:
787:
784:
781:
761:
758:
755:
752:
749:
746:
722:
702:
699:
696:
693:
690:
687:
669:
668:
652:
647:
644:
639:
633:
629:
625:
622:
619:
616:
613:
608:
603:
599:
595:
592:
589:
586:
561:
556:
552:
531:
528:
525:
522:
519:
516:
496:
491:
486:
482:
478:
475:
464:expected value
449:
444:
440:
417:
413:
389:
384:
380:
376:
373:
353:
329:
305:
300:
296:
292:
289:
269:
247:
243:
186:complete graph
181:
178:
143:
140:
132:Chernoff bound
113:expected value
98:
95:
75:linear algebra
26:
9:
6:
4:
3:
2:
3119:
3108:
3105:
3103:
3100:
3098:
3097:Combinatorics
3095:
3094:
3092:
3078:
3077:0 444 81624 0
3074:
3070:
3067:
3063:
3059:
3057:
3053:
3050:
3046:
3043:
3039:
3035:
3031:
3027:
3023:
3019:
3014:
3009:
3005:
3001:
2997:
2992:
2988:
2984:
2980:
2976:
2971:
2966:
2962:
2958:
2954:
2949:
2946:
2945:0-471-37046-0
2942:
2938:
2934:
2933:
2924:
2921:
2920:
2912:
2909:
2907:
2904:
2902:
2899:
2897:
2894:
2892:
2889:
2887:
2884:
2883:
2879:
2873:
2868:
2861:
2857:
2846:
2828:
2823:
2819:
2816:
2810:
2785:
2781:
2777:
2774:
2770:
2767:
2757:
2746:
2736:
2706:
2701:
2695:
2692:
2688:
2683:
2679:
2676:
2669:
2668:
2667:
2650:
2644:
2638:
2635:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2606:
2603:
2597:
2592:
2589:
2584:
2580:
2576:
2569:
2562:
2559:
2556:
2550:
2547:
2541:
2537:
2531:
2527:
2523:
2517:
2510:
2507:
2504:
2498:
2488:
2485:
2482:
2468:
2465:
2454:
2448:
2445:
2442:
2429:
2428:
2427:
2417:
2391:
2388:
2384:
2370:
2363:
2360:
2359:
2347:
2333:
2327:
2321:
2318:
2311:
2308:
2303:
2299:
2295:
2292:
2286:
2282:
2279:
2276:
2270:
2264:
2261:
2256:
2250:
2247:
2242:
2236:
2233:
2230:
2225:
2222:
2219:
2215:
2209:
2206:
2201:
2196:
2192:
2186:
2182:
2176:
2173:
2170:
2165:
2162:
2159:
2155:
2149:
2146:
2141:
2135:
2129:
2124:
2121:
2116:
2112:
2105:
2102:
2096:
2093:
2089:
2078:
2077:
2076:
2074:
2069:
2043:
2038:
2034:
2028:
2022:
2016:
2013:
2010:
2004:
2001:
1998:
1995:
1990:
1987:
1977:
1976:
1975:
1957:
1944:
1936:
1933:
1932:
1931:
1924:
1920:
1890:
1880:
1872:
1856:
1826:
1823:
1810:
1807:
1796:
1793:
1789:
1777:
1774:
1751:
1748:
1737:
1733:
1720:
1717:
1706:
1695:
1692:
1680:
1668:
1665:
1654:
1646:
1621:
1618:
1607:
1596:
1593:
1581:
1569:
1566:
1555:
1547:
1544:
1520:
1517:
1506:
1477:
1474:
1458:
1454:
1431:
1428:
1412:
1408:
1407:
1403:
1399:
1395:
1393:
1381:
1376:
1370:
1369:exponentially
1364:
1360:
1356:
1345:
1341:
1337:
1332:
1331:Ramsey number
1327:
1319:
1312:
1292:
1289:
1276:
1273:
1262:
1259:
1255:
1243:
1240:
1229:
1218:
1214:
1207:
1201:
1194:
1193:
1192:
1178:
1135:
1122:
1119:
1108:
1105:
1101:
1089:
1086:
1075:
1064:
1060:
1053:
1047:
1040:
1039:
1038:
1024:
1016:
1012:
993:
980:
977:
966:
963:
959:
947:
944:
933:
922:
917:
913:
906:
900:
892:
889:
886:
880:
875:
872:
869:
865:
857:
856:
855:
839:
834:
830:
801:
796:
792:
785:
779:
756:
753:
750:
744:
720:
697:
694:
691:
685:
676:
645:
642:
631:
627:
623:
620:
617:
606:
601:
597:
590:
584:
577:
576:
575:
559:
554:
550:
526:
523:
520:
514:
489:
484:
480:
473:
465:
447:
442:
438:
415:
411:
403:
382:
378:
371:
351:
327:
298:
294:
287:
267:
245:
241:
231:
216:
210:
206:
202:
194:
187:
180:First example
177:
173:
169:
165:
161:
160:Ramsey number
157:
153:
149:
139:
137:
133:
129:
124:
120:
118:
114:
109:
107:
102:
94:
92:
88:
84:
80:
79:real analysis
76:
72:
71:number theory
68:
63:
61:
57:
53:
49:
45:
44:combinatorics
41:
37:
33:
19:
3003:
3000:Can. J. Math
2999:
2960:
2957:Can. J. Math
2956:
2936:
2911:Random graph
2858:
2844:
2755:
2744:
2737:
2730:
2665:
2415:
2414:
2367:contains no
2361:
2067:
2060:
1974:vertices is
1955:
1954:
1942:
1934:
1922:
1918:
1891:
1885:is at least
1855:graph theory
1852:
1456:
1410:
1402:
1377:
1362:
1358:
1354:
1343:
1339:
1335:
1328:
1326:-subgraphs.
1317:
1310:
1307:
1150:
1010:
1008:
733:ranges from
677:
670:
233:For any set
232:
217:
183:
171:
167:
163:
145:
125:
121:
110:
105:
103:
100:
97:Introduction
64:
59:
35:
29:
3045:J. Matoušek
3006:: 346–352.
2362:Property 2.
2071:. Hence by
1935:Property 1.
1015:independent
152:tournaments
67:mathematics
56:probability
32:mathematics
3091:Categories
2930:References
1647:Hence, if
1011:regardless
134:, and the
48:Paul Erdős
3083:Footnotes
3008:CiteSeerX
2987:122784453
2963:: 34–38.
2775:≥
2625:−
2619:
2610:−
2598:⋅
2585:−
2560:−
2542:−
2524:≤
2508:−
2486:−
2455:≤
2446:≥
2399:⌉
2379:⌈
2304:−
2280:−
2257:≤
2234:−
2216:∑
2174:−
2156:∑
2142:≤
2117:≤
2029:≤
2014:−
2005:⋅
1999:⋅
1797:−
1764:⇔
1707:−
1608:−
1263:−
1109:−
967:−
866:∑
822:over all
632:−
624:⋅
542:edges in
3038:15134755
2864:See also
2829:⌉
2820:′
2811:⌈
2771:′
2702:⌉
2684:⌈
2371:of size
2075:we have
209:subgraph
193:vertices
148:theorems
115:of some
69:such as
3030:0120168
2979:0102081
1177:integer
402:subsets
203:of the
89:), and
60:certain
52:proving
3075:
3068:, 2017
3064:
3036:
3028:
3010:
2985:
2977:
2943:
2416:Proof.
1956:Proof.
1871:cycles
462:, the
316:to be
130:, the
85:(e.g.
77:, and
50:, for
34:, the
3034:S2CID
2983:S2CID
2666:when
1455:Each
1384:(1.1)
1371:with
205:graph
201:edges
38:is a
3073:ISBN
3062:ISBN
2941:ISBN
2418:Let
2097:>
1958:Let
1896:and
1861:and
1824:<
1734:<
1392:open
1315:and
1290:<
3018:doi
2965:doi
2759:on
2725:1/2
2354:1/2
1908:on
1881:of
1320:= 4
1313:= 5
854:is
737:to
466:of
260:of
224:1/2
220:1/2
211:on
188:on
106:not
30:In
3093::
3032:.
3026:MR
3024:.
3016:.
3004:13
3002:.
2998:.
2981:.
2975:MR
2973:.
2961:11
2959:.
2955:.
2856:.
2845:G′
2842:.
2756:G′
2747:/2
2616:ln
2437:Pr
2086:Pr
1945:/2
1921:=
1889:?
1375:.
1361:,
1342:,
176:.
170:,
138:.
93:.
73:,
3040:.
3020::
2989:.
2967::
2947:.
2854:k
2850:k
2824:k
2817:n
2800:g
2786:2
2782:/
2778:n
2768:n
2751:G
2745:n
2740:G
2733:n
2727:.
2721:n
2707:.
2696:k
2693:2
2689:n
2680:=
2677:y
2651:,
2648:)
2645:1
2642:(
2639:o
2636:=
2631:)
2628:p
2622:n
2613:2
2607:y
2604:p
2601:(
2593:2
2590:y
2581:e
2577:=
2570:2
2566:)
2563:1
2557:y
2554:(
2551:y
2548:p
2538:e
2532:y
2528:n
2518:2
2514:)
2511:1
2505:y
2502:(
2499:y
2493:)
2489:p
2483:1
2480:(
2474:)
2469:y
2466:n
2461:(
2452:)
2449:y
2443:Y
2440:(
2424:G
2420:Y
2411:.
2392:k
2389:2
2385:n
2365:G
2356:.
2350:n
2334:.
2331:)
2328:1
2325:(
2322:o
2319:=
2312:g
2309:1
2300:n
2296:g
2293:=
2287:g
2283:1
2277:g
2271:n
2265:n
2262:g
2251:g
2248:i
2243:n
2237:1
2231:g
2226:3
2223:=
2220:i
2210:n
2207:1
2202:=
2197:i
2193:n
2187:i
2183:p
2177:1
2171:g
2166:3
2163:=
2160:i
2150:n
2147:1
2139:]
2136:X
2133:[
2130:E
2125:n
2122:2
2113:)
2106:2
2103:n
2094:X
2090:(
2068:p
2063:G
2044:2
2039:i
2035:n
2023:!
2020:)
2017:i
2011:n
2008:(
2002:i
1996:2
1991:!
1988:n
1972:n
1968:i
1964:g
1960:X
1951:.
1949:g
1943:n
1938:G
1928:G
1923:n
1919:p
1914:G
1910:n
1906:G
1902:n
1898:k
1894:g
1887:k
1883:G
1875:g
1867:G
1863:k
1859:g
1827:1
1816:)
1811:2
1808:r
1803:(
1794:1
1790:2
1783:)
1778:r
1775:n
1770:(
1757:)
1752:2
1749:n
1744:(
1738:2
1726:)
1721:2
1718:r
1713:(
1701:)
1696:2
1693:n
1688:(
1681:2
1674:)
1669:r
1666:n
1661:(
1655:2
1644:.
1627:)
1622:2
1619:r
1614:(
1602:)
1597:2
1594:n
1589:(
1582:2
1575:)
1570:r
1567:n
1562:(
1556:2
1526:)
1521:2
1518:r
1513:(
1507:2
1483:)
1478:2
1475:r
1470:(
1457:r
1452:.
1437:)
1432:r
1429:n
1424:(
1411:r
1388:r
1373:r
1365:)
1363:r
1359:r
1357:(
1355:R
1350:n
1346:)
1344:r
1340:r
1338:(
1336:R
1324:r
1318:r
1311:n
1293:1
1282:)
1277:2
1274:r
1269:(
1260:1
1256:2
1249:)
1244:r
1241:n
1236:(
1230:=
1227:]
1224:)
1219:r
1215:S
1211:(
1208:X
1205:[
1202:E
1189:1
1185:0
1183:(
1181:0
1173:r
1169:1
1165:r
1161:1
1157:r
1153:1
1136:.
1128:)
1123:2
1120:r
1115:(
1106:1
1102:2
1095:)
1090:r
1087:n
1082:(
1076:=
1073:]
1070:)
1065:r
1061:S
1057:(
1054:X
1051:[
1048:E
1025:r
994:.
986:)
981:2
978:r
973:(
964:1
960:2
953:)
948:r
945:n
940:(
934:=
931:]
928:)
923:i
918:r
914:S
910:(
907:X
904:[
901:E
896:)
893:r
890:,
887:n
884:(
881:C
876:1
873:=
870:i
840:i
835:r
831:S
810:]
807:)
802:i
797:r
793:S
789:(
786:X
783:[
780:E
760:)
757:r
754:,
751:n
748:(
745:C
735:1
721:i
701:)
698:r
695:,
692:n
689:(
686:C
673:2
651:)
646:2
643:r
638:(
628:2
621:2
618:=
615:]
612:)
607:i
602:r
598:S
594:(
591:X
588:[
585:E
560:i
555:r
551:S
530:)
527:2
524:,
521:r
518:(
515:C
495:)
490:i
485:r
481:S
477:(
474:X
448:i
443:r
439:S
416:r
412:S
388:)
383:r
379:S
375:(
372:X
352:r
342:0
328:r
318:1
304:)
299:r
295:S
291:(
288:X
268:r
246:r
242:S
228:r
213:r
197:n
190:n
174:)
172:r
168:r
166:(
164:R
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.