Universal limit theorems in graph coloring problems with connections to extremal combinatorics
From MaRDI portal
Publication:525299
DOI10.1214/16-AAP1205zbMATH Open1360.05051arXiv1310.2336MaRDI QIDQ525299FDOQ525299
Authors: Bhaswar B. Bhattacharya, Persi Diaconis, Sumit Mukherjee 
Publication date: 3 May 2017
Published in: The Annals of Applied Probability (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1310.2336
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
Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Extremal combinatorics (05D99)
Cited In (18)
- Multidimensional limit theorems for homogeneous sums: a survey and a general transfer principle
- A Poisson approximation for coloured graphs under exchangeability
- A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
- Strong limit theorems in the multi-color generalized allocation scheme
- Asymptotic distribution of Bernoulli quadratic forms
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs
- Fluctuations of subgraph counts in graphon based random graphs
- Monochromatic subgraphs in randomly colored graphons
- Normal approximation and fourth moment theorems for monochromatic triangles
- 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
- Title not available (Why is that?)
- The Second-Moment Phenomenon for Monochromatic Subgraphs
- Card guessing and the birthday problem for sampling without replacement
- Title not available (Why is that?)
- Limit theorems for monochromatic stars
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)
