Ordered Unavoidable Sub-Structures in Matchings and Random Matchings
Ordered Unavoidable Sub-Structures in Matchings and Random Matchings
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 …