Asymptotic conjecture that the normalized constants αr\alpha_r vanish

For fixed r1r\geq 1, let αr\alpha_r be the smallest real number such that

fr(n)αr(1+o(1))(nr/2).f_r(n)\leq \alpha_r(1+o(1))\binom{n}{\lfloor r/2\rfloor}.

Here fr(n)f_r(n) is the minimum number of complete rr-partite rr-graphs needed to decompose the complete rr-graph on nn vertices.

Vanishing-αr\alpha_r conjecture. We have

αr0as r.\alpha_r\rightarrow 0\quad\text{as }r\rightarrow\infty.

The initial construction gives αr1\alpha_r\leq 1 for all rr, while the paper establishes αr1415\alpha_r\leq \frac{14}{15} for even rr. The conjecture predicts a substantially stronger improvement as the uniformity grows.

Sources & referencesView supporting material

Primary source

Imre Leader, Luka Milićević and Ta Sheng Tan, “Decomposing the Complete r-Graph”, arXiv:1701.08335 (2017).

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.