Some inequalities for orderings of acyclic digraphs

摘要

Let $D=(V,A)$ be an acyclic digraph. For $xin 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 ightarrow [1,|V|] $ that has the property that for all $x,yin 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_{xin V} e_{_{D}}(x)cdot g(x) ~geq~ frac{1}{2} sum_{xin 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.