Kamčev–Liebenau–Wormald conjecture on typical degree sequences of uniform hypergraphs

Let 2rn22\le r\le n-2 and let d\boldsymbol{d} denote a degree sequence of an rr-uniform hypergraph with mm edges. Write Dr(n,m)\mathcal{D}_r(n,m) for the degree-sequence distribution of a uniformly random rr-uniform hypergraph with mm edges, and Tr(n,m)\mathcal{T}_r(n,m) for the corresponding comparison distribution. Assume

min\originalleft{m,(nr)m\aftergroup\originalright}=ω(logn).\min\mathopen{}\mathclose\bgroup\originalleft\{m,\binom{n}{r}-m\aftergroup\egroup\originalright\}=\omega(\log n).

Kamčev–Liebenau–Wormald conjecture. There exists a set W\mathfrak{W} having probability 1O(nω(1))1-O(n^{-\omega(1)}) in both Dr(n,m)\mathcal{D}_r(n,m) and Tr(n,m)\mathcal{T}_r(n,m) such that, uniformly for all dW\boldsymbol{d}\in\mathfrak{W},

PDr(n,m)(d)=PTr(n,m)(d)(1+o(1)).\mathbb{P}_{\mathcal{D}_r(n,m)}(\boldsymbol{d})=\mathbb{P}_{\mathcal{T}_r(n,m)}(\boldsymbol{d})\,(1+o(1)).

The conjecture asserts that the two degree-sequence distributions agree asymptotically for almost every degree sequence throughout the stated range. The paper proves this comparison under substantially stronger density and regularity hypotheses, leaving the full range of the conjecture as the unresolved motivation.

Sources & referencesView supporting material

Primary source

Catherine Greenhill, Mikhail Isaev, Tamás Makai and Brendan D. McKay, “Degree sequences of sufficiently dense random uniform hypergraphs”, arXiv:2106.08100 (2022).

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.