Andrzej Ruciński
Abstract
For $r,n\ge2$, an ordered $r$-uniform matching $M^{(r)}_n$ 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 $\tfrac12\binom{2r}r$ 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 Erdős-Szekeres type result guaranteeing in every $M^{(r)}_n$ 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 $\Omega\left( n^{3^{1-r}}\right)$. In addition, for each collectable pattern $P$ we show that the largest size of a $P$-clique in a random $M^{(r)}_n$ is, with high probability, $\Theta\left(n^{1/r}\right)$.
This is joint work with Andrzej Dudek and Jarek Grytczuk.
Combinatorics
Adam Mickiewicz University, Poznań and Emory University, Atlanta
Thursday 16 February 2023, 10am
RC-3085