ABSTRACT
Probabilities to Show Pr(X ≥ b) > 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 951 33.4 Applications to Graph Theory and Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 951
33.4.1 Lower Bound on Maximum Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 951 33.4.2 Lower Bounds on Independence Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 953 33.4.3 Small Dominating Sets in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954 33.4.4 Number of Minimum Cuts in Multigraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955
33.4.4.1 Near-Minimum Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956 33.4.5 List Coloring of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957 33.4.6 High Girth and High Chromatic Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 960 33.4.7 Global Coloring and Local Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961 33.4.8 Tournaments of Specified Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962 33.4.9 Bounds on Oriented Chromatic Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964 33.4.10 Bounds on Constrained Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 965
33.4.10.1 Frugal Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 965 33.4.10.2 Acyclic Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 966 33.4.10.3 Other Constrained Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967
33.4.11 Waring Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968 33.4.12 Sum-Free Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 970
33.5 Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971 33.5.1 Existence of Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972 33.5.2 Being Connected . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973 33.5.3 Emergence of a Giant Component in the Vicinity of 1/n . . . . . . . . . . . . . 974 33.5.4 Diameter of Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 977 33.5.5 Concentration of Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 979
33.5.5.1 Concentration of diam(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 979 33.5.5.2 Concentration of ω(G) and α(G) . . . . . . . . . . . . . . . . . . . . . . . . . 979
33.5.5.3 Concentration of χ(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 981 33.5.5.4 Concentration of Induced Paths and Induced Trees . . . . . . 982
33.6 Random Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 984 33.6.1 Induced Acyclic Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 984 33.6.2 Induced Acyclic Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985 33.6.3 Induced Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986 33.6.4 Being Strongly Connected . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987 33.6.5 Emergence of a Giant Strongly Connected Component Around 1/n . 988
33.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 989
U sing probabilistic arguments to prove statements in combinatorics is gaining pop-ularity. A number of examples illustrate how this approach can be a powerful tool in proving mathematical statements in combinatorics in general, and graph theory in particular. This approach is based on applying (often simple) ideas, tools, and techniques from probability theory to obtain and prove a mathematical statement. On the other hand, several specific applications of this approach have also motivated and led to the development of powerful results in probability theory, in particular, with respect to discrete probability spaces.
