Some inequalities for orderings of acyclic digraphs

Abstract

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\to [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 comparbility digraphs of posets of order dimension two.

10 pages, 1 figure