Joint-growth height conjecture for wreath and Kronecker products

Let SnS_n and SmS_m be symmetric groups, let π\pi be distributed uniformly from either the wreath product SnSmS_n \wr S_m or the Kronecker product SmSnS_m \otimes S_n, and let hn,mh_{n,m} denote the height of the associated block binary search tree. Write p\to_p for convergence in probability.

Joint-growth height conjecture. As min(n,m)\min(n,m)\to\infty,

hn,mlogn,logmpc.\frac{h_{n,m}}{\log n\\,\log m}\to_p c^*.

Here c4.311c^*\approx 4.311 is the constant from Devroye's theorem. This is motivated by the fixed-nn conjecture and the asymptotic relation Hn(1)/logn1H_n^{(1)}/\log n\to 1; proving the matching result when both parameters grow remains open and would require stronger control of tree-height extremes.

Sources & referencesView supporting material

Primary source

John Peca-Medlin and Chenyang Zhong, “Heights of butterfly trees”, arXiv:2507.04505 (2026).

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.