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

DOI10.1002/RSA.21123zbMATH Open1525.05172arXiv2007.02216OpenAlexW4309583437MaRDI QIDQ6076216FDOQ6076216

Authors: Pu Gao 

Publication date: 23 October 2023

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

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.

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

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

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)

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Title not available (Why is that?)
• On the independence and chromatic numbers of random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• On the strength of connectedness of a random graph
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Random regular graphs of high degree
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• Title not available (Why is that?)
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Title not available (Why is that?)
• Small subgraphs of random regular graphs
• The number of graphs and a random graph with a given degree sequence
• The asymptotic connectivity of labelled regular graphs
• How to determine if a random graph with a fixed degree sequence has a giant component
• Critical Window for Connectivity in the Configuration Model
• Complex martingales and asymptotic enumeration
• Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing
• Sandwiching random regular graphs between binomial random graphs
• Random graphs with given vertex degrees and switchings
• On the Chromatic Number of Random Graphs with a Fixed 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
• Title not available (Why is that?)
• 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)