Erdős-Szekeres type Theorems for ordered uniform matchings
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912048594550784 |
|---|---|
| author | Dudek, Andrzej Grytczuk, Jarosław Ruciński, Andrzej |
| author_facet | Dudek, Andrzej Grytczuk, Jarosław Ruciński, Andrzej |
| contents | For $r,n\ge2$, an ordered $r$-uniform matching 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 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 ordered $r$-uniform matching 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 $Ω\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 ordered $r$-uniform matching of size $n$ is, with high probability, $Θ\left(n^{1/r}\right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_02936 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Erdős-Szekeres type Theorems for ordered uniform matchings Dudek, Andrzej Grytczuk, Jarosław Ruciński, Andrzej Combinatorics For $r,n\ge2$, an ordered $r$-uniform matching 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 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 ordered $r$-uniform matching 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 $Ω\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 ordered $r$-uniform matching of size $n$ is, with high probability, $Θ\left(n^{1/r}\right)$. |
| title | Erdős-Szekeres type Theorems for ordered uniform matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2301.02936 |