On an extremal problem for poset dimension (Q1789056)

Every partially ordered set (poset) with \(n\) elements has either a chain or an antichain of size \(\sqrt{n}\) by Dilworth's theorem, so has a subposet of dimension 2 of that size (recalling that the dimension of a poset is the smallest number of total orders on the ground set whose intersection is the poset in question). In the paper under review, the authors study \(f(n)\), the largest number such that every poset on \(n\) elements has a subposet on \(f(n)\) vertices with dimension 2 and concentrate on upper bounds on \(f(n)\). The main result of the paper is that \(f(n)\leq 4n^{2/3}+o(n^{2/3})\). The analogous question can also be asked for the largest \(d\)-dimensional subposet, call this \(f_{d}(n)\) (so that \(f(n)\) above is \(f_{2}(n)\)). The main result here is that \(f_{d}(n)=O(n^{d/(d+1)})\). The proof for \(d=2\) with the precise constant is short: the multiplicative 4 can be improved to 3, it seems unknown whether the exponent \(2/3\) can be improved. The proof for general \(d\) uses a multivariate generalisation of a result by \textit{A. Marcus} and \textit{G. Tardos} [J. Comb. Theory, Ser. A 107, No. 1, 153--160 (2004; Zbl 1051.05004)] which controls the number of 1 entries in a \(\{0,1\}\)-matrix that avoids a given permutation matrix.