Some inequalities for orderings of acyclic digraphs

Thomas Bier, Imed Zaguia


Let $D=(V,A)$ be an acyclic digraph. For $x\in V$ define $e_{_{D}}(x)$ to be the difference of the indegree and the outdegree of $x$. An acyclic ordering of the vertices of $D$ is a one-to-one map $g: V \rightarrow [1,|V|] $ that has the property that for all $x,y\in V$ if $(x,y)\in A$, then $g(x) < g(y)$.

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.


(partially) ordered set; digraph, acyclic ordering; linear extension; order dimension two

Full Text:



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.


Contributions to Discrete Mathematics. ISSN: 1715-0868