On random irregular subgraphs

2022/07/27 by Fox, Jacob, Luo, Sammy, Pham, Huy Tuan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2207.13651

Abstract

Let G be a d-regular graph on n vertices. Frieze, Gould, Karoński and Pfender began the study of the following random spanning subgraph model H=H(G). Assign independently to each vertex v of G a uniform random number x(v) ∈ [0,1], and an edge (u,v) of G is an edge of H if and only if x(u)+x(v) ≥ 1. Addressing a problem of Alon and Wei, we prove that if d = o(n/(log n)¹²), then with high probability, for each nonnegative integer k ≤ d, there are (1+o(1))n/(d+1) vertices of degree k in H.

Cited by

• Every graph is uniform-span (2,2)-choosable: Beyond the 1-2 conjecture

Related

• Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
• Irregular Subgraphs
• Sandwiching random regular graphs between binomial random graphs
• Sprinkling with random regular graphs
• Monotonicity and decompositions of random regular graphs