On the integral dicycle packings and covers and the linear ordering polytope (Q1894372): Difference between revisions

The authors give a number of results about the linear ordering polynomial \(P^n_{\text{LO}}\) defined as the convex hull of the incidence vectors of acyclic tournaments on \(n\) nodes. For example, they give a necessary condition for a digraph \(D\) to induce a facet-defining inequality for \(P^n_{\text{LO}}\) that is not equivalent to a trivial or to a 3-dicycle inequality. Let \(\tau\) and \(\nu\) denote the values of a minimum integral dicycle cover and of a maximum integral dicycle packing of a digraph \(D\). The authors also give a necessary condition for the relation \(\tau= \nu\) to hold that yields another proof of the known result that \(\tau= \nu\) in \(K_{3,3}\)-free digraphs.