Article in press
Authors:
Title:
Twins in ordered hyper-matchings
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-10-02 , Revised: 2024-01-04 , Accepted: 2024-01-09 , Available online: 2024-01-26 , https://doi.org/10.7151/dmgt.2535
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ő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.
Keywords:
hypergraphs, ordered matchings, twins
References:
- M. Anastos, Z. Jin, M. Kwan and B. Sudakov, Extremal, enumerative and probabilistic results on ordered hypergraph matchings (2023).
arXiv: 2308.12268 - M. Axenovich, Y. Person and S. Puzynina, A regularity lemma and twins in words, J. Combin. Theory Ser. A 120 (2013) 733–743.
https://doi.org/10.1016/j.jcta.2013.01.001 - B. Bukh and O. Rudenko, Order-isomorphic twins in permutations, SIAM J. Discrete Math. 34 (2020) 1620–1622.
https://doi.org/10.1137/20M1323357 - A. Dudek, J. Grytczuk and A. Ruciński, Variations on twins in permutations, Electron. J. Combin. 28(3) (2021) #P3.19.
https://doi.org/10.37236/9734 - A. Dudek and J. Grytczuk and A. Ruciński, Patterns in ordered $($random$)$ matchings, in: LATIN 2022: Theoretical Informatics, Lecture Notes in Comput. Sci. 13568, A. Castañeda and F. Rodrdríguez-Henrríquez (Ed(s)), (Springer Cham 2022) 544–556.
https://doi.org/10.1007/978-3-031-20624-5_33 - A. Dudek, J. Grytczuk and A. Ruciński, Ordered unavoidable sub-structures in matchings and random matchings (2022).
arXiv: 2210.14042 - A. Dudek, J. Grytczuk and A. Ruciński, Erdős-Szekeres type theorems for ordered uniform matchings (2023).
arXiv: 2301.02936 - P. Erd\H {o}s and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935) 463–470.
- M. Gawron, Isomorphic Substructures in Words and Permutations, Master Thesis, Jagiellonian University (2014) in Polish.
- C. Lee, P.-S. Loh and B. Sudakov, Self-similarity of graphs, SIAM J. Discrete Math. 27 (2013) 959–972.
https://doi.org/10.1137/120861436 - M.J. Luczak and C. McDiarmid, Concentration for locally acting permutations, Discrete Math. 265 (2003) 159–171.
https://doi.org/10.1016/S0012-365X(02)00628-3 - C. McDiarmid, Concentration for independent permutations, Combin. Probab. Comput. 11 (2002) 163–178.
https://doi.org/10.1017/S0963548301005089 - L. Sauermann and D. Zakharov, A sharp Ramsey theorem for ordered hypergraph matchings (2023).
arXiv: 2309.04813 - M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. Inst. Hautes Études Sci. 81 (1995) 73–205.
Close