Alon–Wei asymptotic nearly-uniform degree-distribution conjecture

From papers

Let GG be a dd-regular graph on nn vertices, let HH be a spanning subgraph of GG, and suppose that d=o(n)d=o(n). For each k{0,1,,d}k\in\{0,1,\dots,d\}, write #{vV(H):dH(v)=k}\#\{v\in V(H):d_H(v)=k\} for the number of vertices of degree kk in HH. Alon–Wei asymptotic conjecture. Every dd-regular graph on nn vertices contains a spanning subgraph HH such that

#{vV(H):dH(v)=k}=(1+o(1))nd+1\#\{v\in V(H):d_H(v)=k\}=(1+o(1))\frac{n}{d+1}

for all 0kd0\leq k\leq d. This is the asymptotic version proposed by Alon and Wei; the supplied abstract says that the paper proves it, so the conjecture is solved by the result described in the source.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Richard Montgomery, Alexey Pokrovskiy and Benny Sudakov, “Nearly-uniform degree distributions in spanning subgraphs”, arXiv:2606.30612 (2026).

Additional references

4 papers in this index state this conjecture (2022–2026). The statement above is taken from the most recent of them; the others are arXiv:2408.16121, arXiv:2406.05675, arXiv:2207.13651.

Solutions 0

No solutions have been posted yet.