Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
Pu Gao, Yuval Ohapkin · Random Structures and Algorithms · 2022
Abstract Given a graphical degree sequence , let denote a uniformly random graph on vertex set where vertex has degree for every . We give upper and lower bounds on the joint probability of an arbitrary set of edges in , and we link these probability estimates to the corresponding probabilities in the configuration model. Then we show that many existing results of in the literature can be significantly improved with simpler proofs, by applying this new probabilistic tool. One example we give concerns the chromatic number of . In another application, we use these joint probabilities to study the connectivity of . Under some rather mild condition on —in particular, if where is the maximum component of —we fully characterize the connectivity phase transition of . We also give sufficient conditions for being connected when is unrestricted.