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

DOI10.1002/rsa.21123zbMath1525.05172arXiv2007.02216OpenAlexW4309583437MaRDI QIDQ6076216

Unnamed Author, 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)

Related Items

The Threshold of Symmetry in Random Graphs with Specified Degree Sequences ⋮ Triangles and subgraph probabilities in random regular graphs ⋮ Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs

Cites Work

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