Almost all comparability graphs are UPO (Q795847): Difference between revisions

A comparability graph is an undirected graph that becomes a partial order if appropriate directions are given to its arcs. It is shown here that asymptotically all comparability graphs are bi-uniquely so that there are exactly two different orders corresponding to most such graphs. The reviewer and \textit{B. L. Rothschild} [Trans. Am. Math. Soc. 205, 205-220 (1975; Zbl 0302.05007)] have characterized what asymptotically all partial orders look like. (Their comparability graphs are tripartite with a complete bipartite graph between two of the parts.) As asymptotically all reverse pairs of these have distinct comparability graphs, the present result seems to follow from this characterization.