The dimension of interior levels of the Boolean lattice

G. H. Hurlbert, A. V. Kostochka, L. A. Talysheva

Research output: Contribution to journalArticlepeer-review

Abstract

Let P(k, r;n) denote the containment order generated by the k-element and r-element subsets of an n-element set, and let d(k, r;n) be its dimension. Previous research in this area has focused on the case k=1. P(1, n-1;n) is the standard example of an n-dimensional poset, and Dushnik determined the value of d(1, r;n) exactly, when r≥2 {Mathematical expression}. Spencer used the Erdös-Szekeres theorem to show that d(1, 2;n) ∼ lg lg n, and he used the concept of scrambling families of sets to show that d(1, r;n)=Θ(lg lg n) for fixed r. Füredi, Hajnal, Rödl and Trotter proved that d(1, 2;n)=lg lg n+(1/2+o(1))lg lg lg n. In this paper, we concentrate on the case k≥2. We show that P(2, n-2;n) is (n-1)-irreducible, and we investigate d(2, r;n) when r≥2 {Mathematical expression}, obtaining the exact value for almost all r.

Original languageEnglish (US)
Pages (from-to)29-40
Number of pages12
JournalOrder
Volume11
Issue number1
DOIs
StatePublished - Mar 1 1994
Externally publishedYes

Keywords

  • Containment order
  • Mathematics Subject Classifications (1991): 06A07, 05C35
  • dimension

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The dimension of interior levels of the Boolean lattice'. Together they form a unique fingerprint.

Cite this