
A linear extension \(L\) of a poset \(P\) reverses an incomparable pair \((x,y)\) of \(P\) if \(x>y\) in \(L\). A set \(S\) of incomparable pairs forms a strict alternating cycle of \(P\) if no linear extension of \(P\) reverses all pairs in \(S\) but for all \(T \subset S\) there is a linear extension of \(P\) which reverses all pairs in \(T\). For a poset \(P = (X,\leq)\) let \(H_P = (V,E)\) be the hypergraph of incomparable pairs defined by \(V = \{(x,y) : x,y \in X\) and \(x \|y\}\) and \(E = \{S : S \subseteq V\) is a strict alternating cycle of \(P\}\). The graph of incomparable pairs is \(G_P = (V,E')\) with \(E' = \{S : S \in E\) and \(|S|=2\}\). Then dim\((P) = \chi(H_P) \geq \chi(G_P)\). The paper provides a new proof of the following theorem by Cogis: dim\((P)=2\) if and only if \(\chi(G_P)=2\) for every poset \(P\) that is not a total order. For all \(t \geq 2\) a poset \(P_t\) of dimension dim\((P_t) \geq (3/2)^{t-1}\) is constructed such that the chromatic number fulfills \(\chi(G_{P_t}) \leq 3t-4\).
Combinatorics of partially ordered sets, Extremal problems in graph theory, Coloring of graphs and hypergraphs, dimension, chromatic number, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik, Hypergraphs, 004
Combinatorics of partially ordered sets, Extremal problems in graph theory, Coloring of graphs and hypergraphs, dimension, chromatic number, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik, Hypergraphs, 004
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 21 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
