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.

Speaker

Andrzej Ruciński

Research Area

Combinatorics

Affiliation

Adam Mickiewicz University, Poznań and Emory University, Atlanta

Date

Thursday 16 February 2023, 10am

Venue

RC-3085