zbMATH — the first resource for mathematics

Large subposets with small dimension. (English) Zbl 1336.06003
Summary: Dorais asked for the maximum guaranteed size of a subposet with dimension at most \(d\) of an \(n\)-element poset. A lower bound of order \(\sqrt n\) was found by Goodwillie. We provide a sublinear upper bound for each \(d\). For \(d=2\), our bound is \(n^{0.8295}\).

06A07 Combinatorics of partially ordered sets
Full Text: DOI arXiv
[1] Dorais, F.G.: Subposets of small dimension http://dorais.org/archives/656 (updated Feb. 18, 2012, retrieved Feb. 17, 2014) (2014)
[2] Dorais, F.G.: Subposets of small Dushnik-Miller dimension http://mathoverflow.net/questions/29169 (updated Sept. 12, 2010, retrieved Feb. 17, 2014) (2014)
[3] Erdős, P.: Some new applications of probability methods to combinatorial analysis and graph theory. In: Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, pp 39-51 (1974)
[4] Goodwillie, T.: http://mathoverflow.net/questions/29570 (updated June 28, 2013, retrieved Feb. 17, 2014) (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.