# Ordered Unavoidable Sub-Structures in Matchings and Random Matchings

### Abstract

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\}$, 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 in the same way) which we call, respectively,

*lines*,

*stacks*, and

*waves*. We prove an Erdős-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*ordered matching. Additionally, the former result is generalized to $3$-uniform ordered matchings. Another type of unavoidable patterns we study are

*twins*, that is, pairs 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 and confirm it for almost all matchings. In fact, our results for twins are proved more generally for $r$-multiple twins, $r\ge2$.