On an Extremal Problem for Poset Dimension |
| |
Authors: | Grzegorz Guśpiel " target="_blank">Piotr Micek " target="_blank">Adam Polak |
| |
Institution: | 1.Theoretical Computer Science Department, Faculty of Mathematics and Computer Science,Jagiellonian University,Kraków,Poland |
| |
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) = n 1/2. We improve the best known upper bound and show f(n) = O (n 2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f d (n) elements. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|