On an Extremal Problem for Poset Dimension

摘要

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 ( n (d/d+1)) , 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.