{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:19Z","timestamp":1753893799883,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>An ordered matching of size $n$ is a graph on a linearly ordered vertex set $V$, $|V|=2n$, consisting of $n$ pairwise disjoint edges. There are three different ordered matchings of size two on $V=\\{1,2,3,4\\}$: an alignment $\\{1,2\\},\\{3,4\\}$,\u00a0 a nesting $\\{1,4\\},\\{2,3\\}$, and a crossing $\\{1,3\\},\\{2,4\\}$. Accordingly, there are three basic homogeneous types of ordered matchings (with all pairs of edges arranged \u00a0in the same way) which we call, respectively, lines, stacks, and waves.\r\n\u00a0\r\nWe prove an Erd\u0151s-Szekeres type result guaranteeing in every ordered matching of size $n$ the presence of one of the three basic sub-structures of a given size. In particular, one of them must be of size at least $n^{1\/3}$. We also investigate the size of each of the three sub-structures in a random\u00a0ordered matching. Additionally, the former result is generalized to $3$-uniform ordered matchings.\r\n\u00a0\r\nAnother type of unavoidable patterns we study are twins, that is, \u00a0pairs of order-isomorphic, disjoint sub-matchings. By relating to a similar problem for permutations, we prove that the maximum size of twins that occur in every ordered matching of size $n$ is $O\\left(n^{2\/3}\\right)$ and $\\Omega\\left(n^{3\/5}\\right)$. We conjecture that the upper bound is the correct order of magnitude \u00a0and \u00a0confirm it for almost all matchings. In fact, our results for twins are proved more generally for $r$-multiple twins, $r\\ge2$.\u00a0<\/jats:p>","DOI":"10.37236\/11932","type":"journal-article","created":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T08:50:01Z","timestamp":1713430201000},"source":"Crossref","is-referenced-by-count":1,"title":["Ordered Unavoidable Sub-Structures in Matchings and Random Matchings"],"prefix":"10.37236","volume":"31","author":[{"given":"Andrzej","family":"Dudek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaros\u0142aw","family":"Grytczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Ruci\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2024,4,19]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v31i2p15\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v31i2p15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T08:50:01Z","timestamp":1713430201000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v31i2p15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,19]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,4,5]]}},"URL":"https:\/\/doi.org\/10.37236\/11932","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2024,4,19]]},"article-number":"P2.15"}}