Erd\H{o}s-Szekeres type Theorems for ordered uniform matchings

arXiv2301.02936MaRDI QIDQ6422835FDOQ6422835

Authors: Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński 

Publication date: 7 January 2023

Abstract: For $r,nge2$, an ordered $r$-uniform matching $M_n^{(r)}$ of size $n$ is an $r$-uniform hypergraph on a linearly ordered vertex set $V$, with $|V|=rn$, consisting of $n$ pairwise disjoint edges. There are $$ different $M_2^{(r)}$'s, that is, different ways two edges may intertwine, called here patterns. Among them we identify $3^{r-1}$ collectable patterns $P$, which have the potential of appearing in arbitrarily large quantities called $P$-cliques. We prove an ErdH{o}s-Szekeres type result guaranteeing in every $M_n^{(r)}$ the presence of a $P$-clique of a prescribed size, for some collectable pattern $P$. In particular, in the diagonal case, one of the $P$-cliques must be of size $Omegaleft(n^{3^{1-r}}ight)$. In addition, for each collectable pattern $P$ we show that the largest size of a $P$-clique in a emph{random} $M_n^{(r)}$ is, with high probability, $Thetaleft(n^{1/r}ight)$.

This page was built for publication: Erd\H{o}s-Szekeres type Theorems for ordered uniform matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6422835)