Asymptotic order conjecture for twins in ordered rr-matchings

An ordered rr-matching is an ordered matching in which every vertex belongs to one of rr edge labels, and let t(r)(n)t^{(r)}(n) be the minimum, over ordered rr-matchings of size nn, of the maximum size of a pair of twins. Asymptotic order conjecture for twins in ordered rr-matchings. For every r2r\geqslant 2,

t(r)(n)=Θ(n2r+1).t^{(r)}(n)=\Theta\left(n^{\frac{2}{r+1}}\right).

This conjecture proposes the true asymptotic order of the extremal function, building on the paper's probabilistic upper bound and earlier results on twins in permutations. The source presents it as a problem for future consideration and gives no resolution.

Sources & referencesView supporting material

Primary source

Andrzej Dudek, Jarosław Grytczuk and Andrzej Ruciński, “Twins in ordered hyper-matchings”, arXiv:2310.01394 (2023).

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.