Combinatorial Problems and Extreme Values

The interplay between combinatorics and probability started in the early history of probability theory, when combinatorics was used to calculate the probabilities of events in discrete models. Probabilistic methods were applied in combinatorics starting with several papers by Erds and his coauthors, and a paper by Goncharov 1944. These methods are still used extensively in combinatorics today. In Chapter 4 we gathered results mainly related to the asymptotic behavior of the extremal characteristics of different combinatorial configurations. These results are related to the following main topics: the extremal characteristics of random permutations, the coupon collector’s problem, the polynomial scheme, random trees and random forests, random partitions of finite sets, and the geometric properties of samples of random vectors. The topics and results presented in this chapter provide insight into the natural connections between probability theory and algebra, combinatorics, graph theory and combinatorial geometry. Extreme value distributions, generalized Pareto distributions and many other distributions as well appear in theorems that describe the asymptotic behavior of the extremal characteristics of the combinatorial configurations considered. Original results are also included.