2025/10/28 by Larkin, John, McKay, Brendan D., Tian, Fang
#05C30 #05C80 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.24276
Let G be a uniformly chosen simple (labelled) random graph with given degree sequence \boldsymbold and let X,Y,L be edge-disjoint graphs on the same vertex set as G. We investigate the probability that X ⊆ G and that G ∩ Y = ∅ both conditioned on the event G ∩ L = ∅. We improve upon known bounds of these probabilities and extend them to a wider range of degree sequences through a more precise edge switching argument. Notably, a few vertices of linear degree are permitted provided that the subgraph X does not have an edge incident with them. Further, the graph L is permitted to contain many edges (we provide an example where L is a spanning r-regular subgraph with r = o(n)). We provide the same analysis when G is a simple (labelled) bipartite random graph with a given degree sequence (\boldsymbols,\boldsymbolt). Our work extends the results of Gao and Ohapkin (2023) and McKay (1981, 2010).