Hasheminezhad–McKay conjecture on regular partitions of the complete graph

Let d0,d1,,dk1d_0,d_1,\ldots,d_k\geq1 satisfy

i=0kdi=n1,\sum_{i=0}^k d_i=n-1,

and let R(n;d0,,dk)R(n;d_0,\ldots,d_k) be the number of partitions of the edges of KnK_n into spanning regular subgraphs of degrees d0,,dkd_0,\ldots,d_k. Define λi:=di/(n1)\lambda_i:=d_i/(n-1). Hasheminezhad–McKay conjecture. If k=o(n)k=o(n), then

R(n;d0,,dk)=(1+o(1))ek/42k/2\originalleft(i=0kλiλi\aftergroup\originalright)(n2)(n1d0,,dk)n.R(n;d_0,\ldots,d_k)=(1+o(1))e^{k/4}2^{k/2}\mathopen{}\mathclose\bgroup\originalleft(\prod_{i=0}^k\lambda_i^{\lambda_i}\aftergroup\egroup\originalright)^{\binom{n}{2}}\binom{n-1}{d_0,\ldots,d_k}^{n}.

The expected regular-subgraph count conjecture above is a special case. The general partition-enumeration assertion is not resolved in the source.

Sources & referencesView supporting material

Primary source

Mikhail Isaev, Brendan D. McKay, Angus Southwell and Maksim Zhukovskii, “Sprinkling with random regular graphs”, arXiv:2309.00190 (2024).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2206.12792.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.