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 \(\{{S_{n}^{k}}:n\ge 3, k\ge 0\}\) of height two posets called crowns. We show that the chromatic number of the graph \({G_{n}^{k}}\) of critical pairs of the crown \({S_{n}^{k}}\) is the same as the dimension of \({S_{n}^{k}}\), 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 \({G_{n}^{k}}\) is (k + 1)(k + 2)/2. We obtain this theorem as part of a comprehensive analysis of independent sets in \({G_{n}^{k}}\) including the determination of the second largest size among the maximal independent sets, both the reversible and non-reversible types.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baker, K., Fishburn, P.C., Roberts, F.: Partial orders of dimension 2, interval orders and interval graphs. Networks 2, 11–28 (1971)
Cogis, O.: La dimension Ferrers des graphes orientés. Thèse. Université Pierre et Marie Curie, Paris (1980)
Dushnik, B., Miller, E.W.: Partially ordered sets. Amer. J. Math. 63, 600–610 (1941)
Erdös, P., Kierstead, H., Trotter, W.T.: The dimension of random ordered sets. Random Struct. Algorithm. 2, 253–275 (1991)
Felsner, S., Trotter, W.T.: Dimension, graph and hypergraph coloring. Order 17, 167–177 (2000)
Felsner, S., Krawczyk, T., Trotter, W.T.: Online dimension for posets excluding two long incomparable chains. Order 30, 1–12 (2013)
Fishburn, P.C.: Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, Wiley-Interscience Series in Discrete Mathematics. Wiley, New York (1985)
Füredi, Z., Kahn, J.: On the dimension of ordered sets of bounded degree. Order 3, 15–20 (1988)
Garcia, R., Harris, P., Kubik, B., Talbott, S.: personal communication
Joret, G., Micek, P., Milans, K., Trotter, W.T., Walczak, B., Wang, R.: Tree-width and dimension. Combinatorica 36, 431–450 (2016)
Kelly, D., Trotter, W.T.: Dimension theory for ordered sets. In: Rival, I., et al. (eds.) Proceedings of the Symposium on Ordered Sets, pp 171–212. Reidel Publishing (1982)
Kierstead, H., McNulty, G., Trotter, W.T.: A theory of dimension for recursive ordered sets. Order 1, 67–82 (1984)
Scott, A., Wood, D.R.: Better bounds for poset dimension and boxicity, arXiv:1804.03271v2 (2018)
Trotter, W.T.: Dimension of the crown \(\mathbf {S}_{n}^{k}\). Discrete Math. 8, 85–103 (1974)
Trotter, W.T.: Combinatorics and Partially Ordered Sets: Dimension Theory. The Johns Hopkins University Press, Baltimore (1992)
New perspectives on interval orders and interval graphs, Surveys in Combinatorics. In: Bailey, R. A. (ed.) London Mathematical Society Lecture Note Series, vol. 241, pp. 237–286 (1997)
Trotter, W.T.: Partially ordered sets. In: Graham, R. L., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, pp 433–480. Elsevier, Amsterdam (1995)
Trotter, W.T., Moore, J.I.: The dimension of planar posets. J. Comb. Theory (B) 21, 51–67 (1977)
Trotter, W.T., Wang, R.: Planar posets, dimension, breadth and the number of minimal elements. Order 33, 333–346 (2016)
Acknowledgments
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.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Much of the research done by Barrera-Cruz, Smith, and Taylor was completed while they were affiliated with the Georgia Institute of Technology.
Rights and permissions
About this article
Cite this article
Barrera-Cruz, F., Garcia, R., Harris, P. et al. The Graph of Critical Pairs of a Crown. Order 36, 621–652 (2019). https://doi.org/10.1007/s11083-019-09485-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-019-09485-4