On quantitative aspects of a canonisation theorem for edge‐orderings
| Autor: | Reiher, Christian, Rödl, Vojtěch, Sales, Marcelo, Sames, Kevin, Schacht, Mathias |
|---|---|
| Jazyk: | angličtina |
| Předmět: | |
| Zdroj: | Journal of the London Mathematical Society. 106(3):2773-2803 |
| ISSN: | 1469-7750 0024-6107 |
| DOI: | 10.1112/jlms.12648 |
| Popis: | For integers $k\ge 2$ and $N\ge 2k+1$ there are $k!2^k$ canonical orderings of the edges of the complete $k$-uniform hypergraph with vertex set $[N] = \{1,2,\dots, N\}$. These are exactly the orderings with the property that any two subsets $A, B\subseteq [N]$ of the same size induce isomorphic suborderings. We study the associated canonisation problem to estimate, given $k$ and $n$, the least integer $N$ such that no matter how the $k$-subsets of $[N]$ are ordered there always exists an $n$-element set $X\subseteq [N]$ whose $k$-subsets are ordered canonically. For fixed $k$ we prove lower and upper bounds on these numbers that are $k$ times iterated exponential in a polynomial of $n$. Comment: revised according to referee report |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|