×

Almost all comparability graphs are UPO. (English) Zbl 0543.05054

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 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.
Reviewer: D.Kleitman

MSC:

05C99 Graph theory
05C75 Structural characterization of families of graphs
06A06 Partial orders, general

Citations:

Zbl 0302.05007
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M.; Prins, G., Uniquely partially orderable graphs, J. London Math. Soc., 3, 2, 260-266 (1971) · Zbl 0214.51601
[2] Arditti, J. C.; Jung, H. A., The dimension of finite and infinite comparability graphs, J. London Math. Soc., 21, 31-38 (1980) · Zbl 0425.05045
[3] Birkhoff, G., Lattice Theory, (Amer. Math. Soc. Publ., Vol. XXV (1973), AMS: AMS Providence, RI) · Zbl 0126.03801
[4] Blass, A.; Harary, F., Properties of almost all graphs and complexes, J. Graph Theory, 3, 225-240 (1979) · Zbl 0418.05050
[5] Buer, H.; Möhring, R. H., A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 8, 170-184 (1983) · Zbl 0517.05057
[6] Fagin, R., Probabilities on finite models, J. Symbolic Logic, 41, 50-58 (1976) · Zbl 0341.02044
[7] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[8] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[9] Kleitman, D. J.; Rothschild, B. L., Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205, 205-220 (1975) · Zbl 0302.05007
[10] Möhring, R. H., On the distribution of locally undecomposable relations and independence systems, Methods Oper. Res., 42, 33-48 (1981) · Zbl 0459.90051
[11] Möhring, R. H.; Radermacher, F. J., Dimension, reversibility and chain-equivalence of posets, and connections with homomorphisms, (Beckmann, M.; Eichhorn, W.; Krelle, W., Mathematische Systeme in der Ökomonie (1983), Athenäum: Athenäum Königstein/Ts), 415-432
[12] R.H. Möhring and F.J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, Ann. Discrete Math., to appear.; R.H. Möhring and F.J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, Ann. Discrete Math., to appear. · Zbl 0567.90073
[13] Oberschelp, W., Properties of almost all parametric relations, (paper presented at the Oberwolfach workshop ‘Kombinatorik geordneter Mengen’. paper presented at the Oberwolfach workshop ‘Kombinatorik geordneter Mengen’, Oberwolfach (1980)) · Zbl 0576.94025
[14] Sabidussi, G., Graph derivations, Math. Z., 76, 385-401 (1961) · Zbl 0109.16404
[15] Shevrin, L. N.; Filippov, N. D., Partially ordered sets and their comparability graphs, Siberian Math. J., 11, 497-509 (1970) · Zbl 0214.23303
[16] Trotter, W. T.; Moore, J. I.; Summer, D. F., The dimension of a comparability graph, (Proc. Amer. Math. Soc., 60 (1976)), 35-38 · Zbl 0356.06006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.