Two-Point Concentration of the Domination Number of Random Graphs

2024/01/19 by Tom Bohman, Bohman, Tom, Lutz Warnke +3 · 1 citation
Computer Science · Mathematics · #05C69 #05C80 #60C05 #60F10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2401.10486

openalex publication_date 2024/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the domination number of the binomial random graph G_n,p with edge-probability p is concentrated on two values for p ≥ n^-2/3+\eps, and not concentrated on two values for general p ≤ n^-2/3. This refutes a conjecture of Glebov, Liebenau and Szabo, who showed two-point concentration for p ≥ n^-1/2+\eps, and conjectured that two-point concentration fails for p ≪ n^-1/2. The proof of our main result requires a Poisson type approximation for the probability that a random bipartite graph has no isolated vertices, in a regime where standard tools are unavailable (as the expected number of isolated vertices is relatively large). We achieve this approximation by adapting the proof of Janson's inequality to this situation, and this adaptation may be of broader interest.

Cited by

• Concentration of the maximum size of an induced subtree in moderately sparse random graphs

Related

• On the Concentration of the Domination Number of the Random Graph
• Two-Point Concentration of the Independence Number of the Random Graph
• Concentration of the maximum size of an induced subtree in moderately sparse random graphs
• A concentration result with application to subgraph count
• Maximum sparse induced subgraphs of the binomial random graph with given\n number of edges