The graph of critical pairs of a crown

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Hypergraphs (05C65) Combinatorics of partially ordered sets (06A07)

Abstract: There is a natural way to associate with a poset

P

a hypergraph

H

, called the hypergraph of critical pairs, so that the dimension of

P

is exactly equal to the chromatic number of

H

. The edges of

H

have variable sizes, but it is of interest to consider the graph

G

formed by the edges of

H

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 g e 3, k g e 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

l c e i l 2 (n + k) / (k + 2) c e i l

. 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.

Review text

To any poset \(P\) one can associate a hypergraph \(\mathcal{H}\) of critical pairs such that the chromatic number of \(\mathcal{H}\) is equal to the dimension of \(P\). The chromatic number of the subgraph \(G\), on the same vertex set, comprising the hyperedges with two elements thus gives a lower bound on the dimension of \(P\). While the gap between this lower bound and the truth can be arbitrarily large, quite often the lower bound is the true dimension. The main aim of the article under review was originally to show this equivalence for a class of posets called crowns (the crown \(S_{n}^{k}\) is a height 2 poset with minimal elements \(A=\{a_{1},a_{2},\ldots a_{n+k}\}\) and maximal elements \(B=\{b_{1},b_{2},\ldots b_{n+k}\}\) and with \(a_{i}\) and \(b_{j}\) comparable precisely when \(j\not\in \{i,i+1,\ldots i+k\}\) where of course all indices are read modulo \(n+k\). Crowns have long been known to be important in the study of dimension, for example the crowns with \(k=0\) are the posets on \(2n\) vertices with the largest possible dinension \(n\) (for \(n\geq 4\)). More generally, \(S_{n}^{k}\) has dimension \(2(n+k)/(k+2)\). In the end, the authors prove the desired result by showing that the independence number of the graph \(G_{n}^{k}\) associated with \(S_{n}^{k}\) is \((k+1)(k+2)/2\), as part of a more detailed study of independent sets in \(G_{n}^{k}\). This gives the result, using the standard fact that the chromatic number is the least number of vertices divided by the independence number, as one can check that \(G_{n}^{k}\) has \((n+k)(k+1)\) vertices. The proofs involve, inter alia, splitting the class of independent sets into so-aclled reversible ones and non-reversible ones, with the analysis for non-reversible ones requiring distinction of two cases \(n\leq k\) and \(k < n \leq 2k\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: The graph of critical pairs of a crown

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279688)