Universal limit theorems in graph coloring problems with connections to extremal combinatorics
From MaRDI portal
(Redirected from Publication:525299)
Abstract: This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs. These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?). It is shown that if the number of colors grows to infinity, the asymptotic distribution is either a Poisson mixture or a Normal depending solely on the limiting behavior of the ratio of the number of edges in the graph and the number of colors. This result holds for any graph sequence, deterministic or random. On the other hand, when the number of colors is fixed, a necessary and sufficient condition for asymptotic normality is determined. Finally, using some results from the emerging theory of dense graph limits, the asymptotic (non-normal) distribution is characterized for any converging sequence of dense graphs. The proofs are based on moment calculations which relate to the results of ErdH os and Alon on extremal subgraph counts. As a consequence, a simpler proof of a result of Alon, estimating the number of isomorphic copies of a cycle of given length in graphs with a fixed number of edges, is presented.
Recommendations
- Extremal problems for k-colour graphs and exact inequalities for pairs of random elements
- scientific article; zbMATH DE number 4183438
- Bounds on threshold probabilities for coloring properties of random hypergraphs
- Extremal problems for colourings of uniform hypergraphs
- On the universality and extremality of graphs with a distance constrained colouring
- scientific article; zbMATH DE number 3911368
- Inequalities in probability theory and turán-type problems for graphs with colored vertices
- On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
- Approximating Independent Set and Coloring in Random Uniform Hypergraphs
- Extremal graphs in some coloring problems
Cited in
(18)- scientific article; zbMATH DE number 17683 (Why is no real title available?)
- Normal approximation and fourth moment theorems for monochromatic triangles
- Fluctuations of subgraph counts in graphon based random graphs
- A Poisson approximation for coloured graphs under exchangeability
- scientific article; zbMATH DE number 4183438 (Why is no real title available?)
- Multidimensional limit theorems for homogeneous sums: a survey and a general transfer principle
- Monochromatic subgraphs in randomly colored graphons
- A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs
- Asymptotic distribution of Bernoulli quadratic forms
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- Card guessing and the birthday problem for sampling without replacement
- A limit theorem for small cliques in inhomogeneous random graphs
- Fluctuations of quadratic chaos
- Inequalities in probability theory and turán-type problems for graphs with colored vertices
- The Second-Moment Phenomenon for Monochromatic Subgraphs
- Limit theorems for monochromatic stars
- A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
- Strong limit theorems in the multi-color generalized allocation scheme
This page was built for publication: Universal limit theorems in graph coloring problems with connections to extremal combinatorics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q525299)
