References & Citations
Mathematics > Combinatorics
Title: Twins in ordered hyper-matchings
(Submitted on 2 Oct 2023 (v1), last revised 5 Dec 2023 (this version, v2))
Abstract: An ordered $r$-matching of size $n$ is an $r$-uniform hypergraph on a linearly ordered set of vertices, consisting of $n$ pairwise disjoint edges. Two ordered $r$-matchings are isomorphic if there is an order-preserving isomorphism between them. A pair of twins in an ordered $r$-matching is formed by two vertex disjoint isomorphic sub-matchings. Let $t^{(r)}(n)$ denote the maximum size of twins one may find in every ordered $r$-matching of size $n$.
By relating the problem to that of largest twins in permutations and applying some recent Erd\H{o}s-Szekeres-type results for ordered matchings, we show that $t^{(r)}(n)=\Omega\left(n^{\frac{3}{5\cdot(2^{r-1}-1)}}\right)$ for every fixed $r\geqslant 2$. On the other hand, $t^{(r)}(n)=O\left(n^{\frac{2}{r+1}}\right)$, by a simple probabilistic argument. As our main result, we prove that, for almost all ordered $r$-matchings of size $n$, the size of the largest twins achieves this bound.
Submission history
From: Andrzej Dudek [view email][v1] Mon, 2 Oct 2023 17:53:13 GMT (17kb,D)
[v2] Tue, 5 Dec 2023 20:07:46 GMT (17kb,D)
Link back to: arXiv, form interface, contact.