Lecture
PROBABILISTIC COMBINATORICS, a branch of discrete mathematics in which the methods of probability theory are applied to the study of combinatorial objects. Probabilistic combinatorics also considers enumerative problems of combinatorics and questions of the existence of combinatorial objects with given characteristics.
This branch answers questions of the form: what is the probability of the presence of a certain property for a random discrete object, such as a random graph? For example, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain given properties (for which explicit examples may be hard to find), simply by observing that the probability of randomly choosing an object with these properties is greater than 0. This approach (often called the probabilistic method) has proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.
Often associated with Paul Erdős, who did pioneering work on this subject, probabilistic combinatorics was traditionally regarded as a set of tools for studying problems in other parts of combinatorics. However, with the growth of applications to the analysis of algorithms in computer science, as well as classical probability theory, additive number theory and probabilistic number theory, this area has recently grown and become an independent field of combinatorics.
When probabilistic methods are used to solve enumerative problems of combinatorics, a probability distribution is defined on a finite set of combinatorial objects, and the distributions of the characteristics of a random combinatorial object from this set are studied. If the given distribution is uniform, then the probability that some characteristic of a random object has taken some value is the ratio of the number of objects possessing this value of the characteristic to the total number of objects in the set, so that, if the total number of objects is known, the problem of finding the probability and the enumerative problem of finding the number of objects with a given value of the characteristic are equivalent.
The first steps of probabilistic combinatorics are connected with the development, in the mid-17th century, of the elementary theory of probability, when combinatorial methods were used to count various probabilities in games of chance. The first research results in probabilistic combinatorics using modern methods of probability theory appeared in the works of V. L. Goncharov 1942–44, in which the main results were obtained on the limiting behavior of random variables connected with the cycle structure random permutations as their degrees increase. A random permutation in combinatorics of degree n – is a permutation chosen with equal probabilities from the set of all permutations of degree n. Using the methods of proving limit theorems that are well developed in probability theory (the method of generating functions, the method of characteristic functions, and also the method of moments), Goncharov proved that the number of cycles of length r in a random permutation of degree n has, in the limit as n→∞ a Poisson distribution with parameter 1/r, the distribution of the total number of cycles approaches the normal distribution with parameters (lnn,lnn ), and the limiting distribution of the maximum cycle length of a random permutation was found. Subsequently these results largely served as a model for the study of various classes of random combinatorial objects, including random allocations, random partitions of integers into integer summands, various classes of random graphs (random mappings, forests, trees), random matrices, systems of random equations, random automata, random algorithms.
In the study of random graphs, the Hungarian mathematicians P. Erdős and A. Rényi discovered (1960) an unexpected effect which, by analogy with a similar effect in the behavior of systems of particles in statistical physics, is interpreted as a phase transition. Let 𝒢n,T – a random graph with n vertices, which is obtained as a result of placing T edges, each of which, independently of the placement of the other edges, occupies any of n(n−1)/2 possible positions with equal probabilities. Let 2T/n→λ as n,T→∞ . If λ<1, more precisely, if ( 1–2T/n)3n→∞, then the graph 𝒢n,T with probability tending to one, consists of connected components that are either trees or components containing exactly one cycle. As the parameter 2T/n passes through the value 1, more precisely, in the region where, as n,T→∞ the parameter (1–2T/n)3 tends to some constant c, the so-called giant component appears, the number of vertices in which is asymptotically normal with expectation α(c)n, and as the parameter decreases c the parameter α(c) increases. When (1–2T/n)3n→–∞ the graph 𝒢n,T with probability tending to one, consists of the giant component, trees and components with one cycle. Such behavior of the random graph as the parameter 2T/n passes through the value 1 can be interpreted as a phase transition or, in other words, as the presence of a threshold effect in the behavior of the random graph. Later the threshold effect was discovered in the behavior of even simpler random combinatorial objects such as random forests of rooted and unrooted trees.
The probabilistic approach is also used to prove the existence of combinatorial objects without resorting to constructive constructions. The simplest variant of this approach is based on the fact that if the expectation of an integer-valued non-negative random variable is positive, then this random variable is not identically zero. One of the examples of applying the probabilistic approach is as follows.
Let 𝒢n(p) – a random graph with n vertices in which each pair of vertices, independently of the others, is joined by an edge with probability p (with probability q there is no such edge, p+q=1). In the graph
, complementary to the graph 𝒢n(p), a pair of vertices is joined by an edge if and only if there is no such edge in 𝒢n(p) . Let vn(p,k) and 
– are the numbers of complete subgraphs with k vertices in 
respectively.
For the expectations the following equalities hold
If the number 
, where
– are the binomial coefficients,
[a] – is the integer part of the number a, then also as n→∞.
A consequence of these relations is that for every fixed p,0 n there exists a graph Gn(p) c n vertices, not containing a complete subgraph with more than 2lnn/ln(1/p) vertices, the complementary graph G¯n(p) of which does not contain a complete subgraph with more than lnn/ln(1/q) vertices.
Considerable attention in probabilistic combinatorics is paid to the generation of sequences of random numbers, the generation of random combinatorial objects such as random permutations, as well as the probabilistic analysis of algorithms and the construction of probabilistic algorithms that include random number generators.
Comments