2023/10/02 by Dudek, Andrzej, Grytczuk, Jarosław, Ruciński, Andrzej
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.01394
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ős-Szekeres-type results for ordered matchings, we show that t(r)(n)=Ω(n^\frac35⋅(2r-1-1)) for every fixed r\geqslant 2. On the other hand, t(r)(n)=O(n(2)/(r+1)), 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.