论文标题
在比赛和随机匹配中有序不可避免的子结构
Ordered unavoidable sub-structures in matchings and random matchings
论文作者
论文摘要
大小$ n $的有序匹配是线性订购的顶点套装$ v $，$ | v | = 2n $的图形，由$ n $成对的分离边缘组成。 $ V = \ {1,2,3,4 \} $有三个不同的有序匹配：一个对齐$ \ {1,2 \}，\ {3,4 \} $，一个嵌套$ \ {1,4 \}，\ {1,4 \}，\ {2,3 \} $ $ \ {1,3 \}，\ {2,4 \} $。因此，我们分别称之为三种基本均匀类型的有序匹配项（所有边缘以相同方式排列）分别称为行，堆栈和波浪。 我们证明了Erdős-Szekeres类型的结果，以确保每个大小$ n $的有序匹配都存在给定尺寸的三个基本子结构之一。特别是，其中一个必须至少为$ n^{1/3} $。我们还以随机有序匹配的方式研究了三个子结构中的每一个的大小。此外，前者的结果被推广到$ 3 $统一的订购比赛。 我们研究的另一种不可避免的模式是双胞胎，即成对的阶数形式，不相交的子匹配。通过与排列的类似问题有关，我们证明，在每个大小$ n $的有序匹配中发生的双胞胎的最大大小为$ o \ left（n^{2/3} \ right）$和$ω\ left（n^{3/5} \ right）$。我们猜想上限是正确的数量级，并为几乎所有匹配而确认它。实际上，我们对双胞胎的结果更普遍地证明了$ r $ r $ - 万月双胞胎，$ r \ ge2 $。
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 $Ω\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$.
