Sparse incomparability implies sparse covering

Thinking about this question on the CStheory exchange led me to a curious observation about graph representations of partial orders.

The covering graph, or transitive reduction, of a partially ordered set \( (S,\le) \) is a graph that has an edge \(x\rightarrow y\) for every pair of distinct elements \( x \) and \( y \) in \( S \) for which \( x \le y \) and for which there does not exist \( z \) with \( x \le z \le y. \) It's a directed acyclic graph in which none of the edges is redundant: if an edge \( x\rightarrow y\) is removed, then there is no other path leading from \( x \) to \( y. \) Conversely every irredundant DAG is the covering graph for the partial order on its vertices in which \( x\le  y \) whenever there is a path from \( x \) to \( y. \)

A partially ordered set also has an incomparability graph, an undirected graph with an edge \( x \)–\( y \) for every pair of distinct elements that are incomparable.

If \( C=(V,A) \) is the covering graph of a partial order, and \( I=(V,E) \) is the incomparability graph, then it turns out that \( |A| = O(n + |E|). \) For instance, the DAG shown below in blue (with incomparability graph in pink) has \( |A| = 4|E| - 4 \):

Somehow this seems counterintuitive to me: if you have few incomparability edges, then you have a lot of comparability edges, so why should only a small number of them be covering edges? But it's true.

To prove that \( |A| = O(n + |E|), \) assign a charge of one unit to each edge \( x\rightarrow y \) in the covering graph. Compare whether the number of outgoing neighbors of \( x \) is larger or the number of incoming neighbors of \( y \) is larger. If \( x \) has the larger number of neighbors, \( k \) of them, then spread \( 1/2k \) units of charge to vertex \( x, \) \( 1/2k \) units to vertex \( y, \) and \( 1/k \) units to each of the \( k-1 \) incomparability graph edges \( yz \) where \( z \) ranges over the outgoing neighbors of \( x \) that are different from \( y. \)

Each vertex gets at most one unit of charge: its \( k \) downstairs neighbors in the covering graph can each charge it at most \( 1/2k \) unit and its \( j \) upstairs neighbors can each charge it at most \( 1/2j \) units.

Each incomparability edge also gets at most four units of charge. For, if \( yz \) is an incomparability edge that belongs to \( t \) different triangles \( xyz \) where \( x\rightarrow y \) and \( x\rightarrow z \) are covering graph edges, then \( yz \) will be charged by at most \( 2t \) of the covering edges in these triangles. But for it to be charged by these edges, \( x \) must have at least \( t \) outgoing neighbors, because otherwise \( y \) or \( z \) (which both have at least \( t \) incoming neighbors) would have been charged instead. Therefore, each of these \( 2t \) covering edges will give edge \( yz \) at most \( 1/t \) units of charge, for a total of \( 2 \) units. Symmetrically, \( yz \) can get at most \( 2 \) units charged to it from covering edges that go out of \( y \) or \( z. \)

So: \(|A| ={}\)total charge\({}={}\)(charge assigned to vertices)\({}+{}\)(charge assigned to incomparability edges)\({} \le n + 4|E|. \)

The connection to the CStheory exchange question (this won't make sense unless you've read that question and my answer to it): in my answer, I suggested a data structure in which one stores (in each cell of a certain geometric partition) a total order that is \( O(n) \) inversions away from the correct sorted order, and using a somewhat complicated distribution-sensitive sorting algorithm that runs in linear time when it is given such an input. Instead, with a little more preprocessing effort, one can store a different data structure that makes for simpler queries: use the same geometric partition, find within each cell a partial order representing the order relations that are constant throughout the cell, and store within the cell both the covering graph and the incomparability graph. Then, to handle a query, compare each pair of endpoints of each edge in the incomparability graph, orient these edges according to the result of the comparison, take the union of the resulting directed graph with the stored covering graph, and find its (unique) topological ordering. The analysis in my answer shows that the number of incomparability edges is linear, and the relation shown here then implies that the number of covering edges is also linear, so the data structure takes cubic space and has linear query time.

What I don't know is whether this relation between the sparsity of covering graphs are and the sparsity of the corresponding incomparability graphs appears in the literature already — I tried some searches but didn't find anything. It seems like the sort of basic thing that should have already been known, though.

---

Comments: