### Some inequalities for orderings of acyclic digraphs

#### Abstract

We prove that for every acyclic ordering $g$ of $D$ the following inequality holds:

\[\sum_{x\in V} e_{_{D}}(x)\cdot g(x) ~\geq~ \frac{1}{2} \sum_{x\in V}[e_{_{D}}(x)]^2~.\]

The class of acyclic digraphs for which equality holds is determined as the class of comparability digraphs of posets of order dimension two.

#### Keywords

#### Full Text:

PDF#### References

K. A. Baker, P. C. Fishburn, and F. S. Roberts, Partial orders of dimension 2, Networks 2 (1972), 11-28.

J. Bang-Jensen and G. Gutin, Digraphs, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2001, Theory, algorithms and applications.

T. Bier, Some inequalities for linear extensions of posets and ideals, Algebras and combinatorics (Hong Kong, 1997), Springer, Singapore, 1999, pp. 25-36.

G. Brightwell and V. Patel, Average relational distance in linear extensions of posets, Discrete Math. 310 (2010), no. 5, 1016-1021.

B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600-610.

D. Howard, R. Shull, N. Streib, and A. N. Trenk, The total linear discrepancy of an ordered set, Discrete Math. 310 (2010), no. 5, 1022-1025.

D. Kelly, The 3-irreducible partially ordered sets, Canad. J. Math. 29 (1977), no. 2, 367-383.

N. Streib, Dimension preserving contractions and a nite list of 3-irreducible posets, Order 29 (2012), no. 1, 165-176.

E. Szpilrajn, Sur l'extension de l'ordre partiel, Fundamenta Mathematicae 16 (1930), no. 1, 386-389.

W. T. Trotter Jr. and J. I. Moore Jr., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math. 16 (1976), no. 4, 361-381.