2014/07/14 by Nicolas Broutin, Ross J. Kang, Broutin, Nicolas +1
Mathematics · #05A16 #05C15 #05C80 #Bounded function #Chromatic scale #Combinatorics #Combinatorics (math.CO) #Component (thermodynamics) #Computer science #Connected component #Discrete mathematics #FOS: Mathematics #Graph #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Monochromatic color #Optics #Order (exchange) #Partition (number theory) #Physics #Probability (math.PR) #Random graph #Stochastic processes and statistical mechanics #Vertex (graph theory) #math.CO #math.PR #msc:05A16 #msc:05C15 #msc:05C80
paper · pdf · open access · doi:10.48550/arxiv.1407.3555
published in arXiv (Cornell University) (Cornell University) · 23 pages, 1 figure; v2 accepted to Journal of Combinatorics
openalex publication_date 2014/07/14 · arxiv created 2017/07/18 · arxiv updated 2017/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider vertex partitions of the binomial random graph Gn,p. For np→∞, we observe the following phenomenon: in any partition into asymptotically fewer than χ(Gn,p) parts, i.e. o(np/log np) parts, one part must induce a connected component of order at least roughly the average part size. Stated another way, we consider the t-component chromatic number, the smallest number of colours needed in a colouring of the vertices for which no monochromatic component has more than t vertices. As long as np → ∞, there is a threshold for t around Θ(p-1log np): if t is smaller then the t-component chromatic number is nearly as large as the chromatic number, while if t is greater then it is around n/t. For 0 < p <1 fixed, we obtain more precise information. We find something more subtle happens at the threshold t = Θ(log n), and we determine that the asymptotic first-order behaviour is characterised by a non-smooth function. Moreover, we consider the t-component stability number, the maximum order of a vertex subset that induces a subgraph with maximum component order at most t, and show that it is concentrated in a constant length interval about an explicitly given formula, so long as t = O(log log n). We also consider a related Ramsey-type parameter and use bounds on the component stability number of Gn,1/2 to describe its basic asymptotic growth.