The Graph of Critical Pairs of a Crown

Fidel Barrera-Cruz, Rebecca Garcia, Pamela Harris, Bethany Kubik, Heather Smith, Shannon Talbott, Libby Taylor, William T. Trotter

Research output: Contribution to journalArticlepeer-review

Abstract

There is a natural way to associate with a poset P a hypergraph , called the hypergraph of critical pairs, so that the dimension of P is exactly equal to the chromatic number of. The edges of have variable sizes, but it is of interest to consider the graph G formed by the edges of that have size 2. The chromatic number of G is less than or equal to the dimension of P and the difference between the two values can be arbitrarily large. Nevertheless, there are important instances where the two parameters are the same, and we study one of these in this paper. Our focus is on a family {Snk:n≥3,k≥0} of height two posets called crowns. We show that the chromatic number of the graph Gnk of critical pairs of the crown Snk is the same as the dimension of Snk, which is known to be ⌈2(n + k)/(k + 2)⌉. In fact, this theorem follows as an immediate corollary to the stronger result: The independence number of Gnk is (k + 1)(k + 2)/2. We obtain this theorem as part of a comprehensive analysis of independent sets in Gnk including the determination of the second largest size among the maximal independent sets, both the reversible and non-reversible types.

Original languageEnglish (US)
Pages (from-to)621-652
Number of pages32
JournalOrder
Volume36
Issue number3
DOIs
StatePublished - Nov 1 2019

Bibliographical note

Funding Information:
The research reported here was initiated in two informal workshops hosted by the United States Military Academy (West Point) in 2015 and 2016, and we thank them for providing a stimulating and encouraging atmosphere. Smith acknowledges support from NSF-DMS grant #1344199. Harris acknowledges support from NSF-DMS grant #1620202.

Publisher Copyright:
© 2019, Springer Nature B.V.

Keywords

  • Chromatic number
  • Critical pairs
  • Dimension

Fingerprint Dive into the research topics of 'The Graph of Critical Pairs of a Crown'. Together they form a unique fingerprint.

Cite this