Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n1/2. We improve the best known upper bound and show f(n) = O (n2/3). For higher dimensions, we show fd(n)=O(ndd+1), where fd(n) is the largest integer such that every poset on n elements has a d-dimensional subposet on fd(n) elements.
On an extremal problem for poset dimension
Polak, Adam
2018
Abstract
Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n1/2. We improve the best known upper bound and show f(n) = O (n2/3). For higher dimensions, we show fd(n)=O(ndd+1), where fd(n) is the largest integer such that every poset on n elements has a d-dimensional subposet on fd(n) elements.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
s11083-017-9444-1.pdf
accesso aperto
Descrizione: article
Tipologia:
Pdf editoriale (Publisher's layout)
Licenza:
Creative commons
Dimensione
508.59 kB
Formato
Adobe PDF
|
508.59 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
