Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity

DOI10.1002/RSA.21123MaRDI QIDQ6076216zbMATH OpenOpenAlexFDO

Authors Pu Gao

Publication date 23 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.02216

zbMATH Keywords

subgraph probabilityrandom graphs with given degree sequencethreshold of connectivity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Given a graphical degree sequence $$, let $$ denote a uniformly random graph on vertex set $[n]$ where vertex $i$ has degree $d_i$ for every $1leilen$. We give upper and lower bounds on the joint probability of an arbitrary set of edges in $$. These upper and lower bounds are approximately what one would get in the configuration model, and thus the analysis in the configuration model can be translated directly to $$, without conditioning on that the configuration model produces a simple graph. Many existing results of $$ in the literature can be significantly improved with simpler proofs, by applying this new probabilistic tool. One example we give is about the chromatic number of $$. In another application, we use these joint probabilities to study the connectivity of $$. When $Delt{a}^2=o(M)$ where $Delta$ is the maximum component of $$, we fully characterise the connectivity phase transition of $$. We also give sufficient conditions for $$ being connected when $Delta$ is unrestricted.

Recommendations

• Subgraphs of random graphs with specified degrees
• scientific article; zbMATH DE number 3943865
• Subgraphs of dense random graphs with specified degrees
• Random graphs and their subgraphs
• Subgraphs of Random Graphs
• On Subgraph Sizes in Random Graphs
• scientific article; zbMATH DE number 6327467
• On the chromatic number of random subgraphs of a certain distance graph
• Subgraph counts for dense random graphs with specified degrees
• On random subgraphs of Kneser and Schrijver graphs

Cites work

• scientific article; zbMATH DE number 3878944 (Why is no real title available?)
• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 747040 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Complex martingales and asymptotic enumeration
• Critical window for connectivity in the configuration model
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• How to determine if a random graph with a fixed degree sequence has a giant component
• On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
• On the independence and chromatic numbers of random regular graphs
• On the strength of connectedness of a random graph
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• Random graphs with given vertex degrees and switchings
• Random regular graphs of high degree
• Sandwiching random regular graphs between binomial random graphs
• Small subgraphs of random regular graphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The asymptotic connectivity of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• The number of graphs and a random graph with a given degree sequence

Cited in

(5)

• Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
• The Threshold of Symmetry in Random Graphs with Specified Degree Sequences
• On subgraphs with degrees of prescribed residues in the random graph
• scientific article; zbMATH DE number 4164910 (Why is no real title available?)
• Triangles and subgraph probabilities in random regular graphs

This page was built for publication: Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076216)