Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs

2024/07/23 by Diskin, Sahar, Erde, Joshua, Kang, Mihyun +1
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2407.16458

Abstract

Given a graph G and p∈ [0,1], the random subgraph G_p is obtained by retaining each edge of G independently with probability p. We show that for every ε>0, there exists a constant C>0 such that the following holds. Let d≥ C be an integer, let G be a d-regular graph and let p≥ (C)/(d). Then, with probability tending to one as |V(G)| tends to infinity, there exists a matching in G_p covering at least (1-ε)|V(G)| vertices. We further show that for a wide family of d-regular graphs G, which includes the d-dimensional hypercube, for any p≥ (log⁵d)/(d) with probability tending to one as d tends to infinity, G_p contains an induced subgraph on at least (1-o(1))|V(G)| vertices, whose degrees are tightly concentrated around the expected average degree dp.

Related

• Large induced matchings in random graphs
• On random irregular subgraphs
• The number of perfect matchings, and the nesting properties, of random regular graphs
• Large subgraphs in pseudo-random graphs
• Sandwiching random regular graphs between binomial random graphs