The multipartite semiregular factorisation conjecture for complete bipartite graphs

From papers

Let Km,nK_{m,n} be the complete bipartite graph with parts of sizes mm and nn, and let R(m,n;λ0,,λk)R(m,n;\lambda_0,\ldots,\lambda_k) count partitions of its edges into spanning semiregular subgraphs with densities λ0,,λk\lambda_0,\ldots,\lambda_k. For positive numbers λ0,,λk\lambda_0,\ldots,\lambda_k satisfying

i=0kλi=1,\sum_{i=0}^k\lambda_i=1,

write (aa0,,ak)\binom{a}{a_0,\ldots,a_k} for a multinomial coefficient and define

R(m,n;λ0,,λk)=(nλ0n,,λkn) ⁣m(mλ0m,,λkm) ⁣n(mnλ0mn,,λkmn)(11/m)k(m1)/2.R'(m,n;\lambda_0,\ldots,\lambda_k)=\frac{\displaystyle\binom{n}{\lambda_0 n,\ldots,\lambda_k n}^{\!m}\binom{m}{\lambda_0 m,\ldots,\lambda_k m}^{\!n}}{\displaystyle\binom{mn}{\lambda_0 mn,\ldots,\lambda_k mn}}(1-1/m)^{k(m-1)/2}.

The multipartite semiregular factorisation conjecture. If nn\to\infty with 2mn2\le m\le n and 1k=o(m)1\le k=o(m), then

R(m,n;λ0,,λk)R(m,n;λ0,,λk).R(m,n;\lambda_0,\ldots,\lambda_k)\sim R'(m,n;\lambda_0,\ldots,\lambda_k).

This generalises the known asymptotic formula for decompositions into two spanning semiregular subgraphs. The paper proves the conjecture in several regimes, including fixed mm, sparse cases, nearly equal densities, and the Latin-rectangle case, but leaves the full range 1k=o(m)1\le k=o(m) open.

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

Mahdieh Hasheminezhad and Brendan D. McKay, “Factorisation of the complete bipartite graph into spanning semiregular factors”, arXiv:2206.12793 (2022).

Solutions 0

No solutions have been posted yet.