The conjectured order of twins in ordered r-matchings

About 4 years old · traced to

For each integer r⩾2r\geqslant2, let trmatch⁡(n)t_r^{\operatorname{match}}(n) denote the largest size of twins that are unavoidable in every ordered rr-matching of size nn. Here twins are pairs of disjoint, order-isomorphic sub-matchings. Twins conjecture for ordered r-matchings. For every fixed r⩾2r\geqslant 2, one has

trmatch⁡(n)=Θ(nr2r−1).t_r^{\operatorname{match}}(n)=\Theta\left(n^{\frac{r}{2r-1}}\right).

This extends the paper's results and proposed asymptotic order for twins beyond ordinary ordered matchings. Its status is open in the supplied text.

References

Primary source

Andrzej Dudek, Jarosław Grytczuk and Andrzej Ruciński, “Ordered unavoidable sub-structures in matchings and random matchings”, arXiv:2210.14042 (2024).

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.