×

Forbidden induced partial orders. (English) Zbl 0940.06003

If \(P\) is a finite partial order, then \(\text{Forb}^n_{\text{ind}}(P)\) denotes the set of partial orders on \(n\) labelled points containing no induced copy of \(P\). The authors deal with the problem of estimating the size of \(|\text{Forb}^n_{\text{ind}}|\) for each fixed \(P\). They specify four classes of partial orders according to the rate of growth of \(|\text{Forb}^n_{\text{ind}}(P)|\). Since all partial orders of height 3 or more are in one of these classes, especially partial orders of height at most 2 are thoroughly studied here. The results are also specified for some known classes of partial orders (interval orders, series-parallel orders, etc.).

MSC:

06A07 Combinatorics of partially ordered sets
06A06 Partial orders, general
Full Text: DOI

References:

[1] Alekseev, V. E., On the entropy values of hereditary classes of graphs, Discrete Math. Appl., 3, 191-199 (1993) · Zbl 0797.05077
[2] Benson, C. T., Minimal regular graphs of girth eight and twelve, Canad. J. Math., 26, 1091-1094 (1966) · Zbl 0146.45701
[3] Bollobás, B.; Thomason, A., Hereditary and monotone properties of graphs, (Graham, R. L.; Nešetřil, J., The Mathematics of Paul Erdős II (1997), Springer: Springer Berlin), 70-78 · Zbl 0866.05030
[4] Brightwell, G.; Goodall, S., The number of partial orders of fixed width, Order, 13, 315-337 (1996) · Zbl 0878.06002
[5] Brightwell, G.; Prömel, H. J.; Steger, A., The average number of linear extensions of a partial order, J. Combin. Theory (A), 73, 193-206 (1996) · Zbl 0842.05004
[6] Brightwell, G.; Trotter, W. T., Incidence posets of trees in posets of large dimension, Order, 11, 159-167 (1994) · Zbl 0823.06005
[7] Cameron, P., On the probability of connectedness, Discrete Math., 167/168, 175-187 (1997) · Zbl 0874.60012
[8] El-Zahar, M. H., Enumeration of ordered sets, (Rival, I., Algorithms and Order (1989), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 327-352 · Zbl 1261.06006
[9] Fishburn, P. C., Interval Orders and Interval Graphs (1985), Wiley Interscience: Wiley Interscience New York · Zbl 0216.30401
[10] Gallai, T., Transitiv orientierbare Graphen, Acta. Math. Hungar., 18, 25-66 (1967) · Zbl 0153.26002
[11] 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
[12] Lazebnik, F.; Ustimenko, V. A., New examples of graphs without small cycles and of large size, Eur. J. Combin., 14, 445-460 (1993) · Zbl 0794.05050
[13] Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J., Properties of certain families of \(2k\)-cycle-free graphs, J. Combin. Theory (B), 60, 293-298 (1994) · Zbl 0803.05028
[14] Prömel, H. J.; Steger, A., Excluding induced subgraphs III: a general asymptotic, Random Structures and Algorithms, 3, 19-31 (1992) · Zbl 0751.05041
[15] Stanley, R. P., Enumeration of posets generated by disjoint unions and ordinal sums, (Proc. Amer. Math. Soc., 45 (1974)), 295-299 · Zbl 0297.05009
[16] Tits, J., Géométries polyédriques et groupes simples, \((2^e\) Reunion Math. d’expression latine. \(2^e\) Reunion Math. d’expression latine, Firenze/Bologna, 1961 (1962), Cremonese: Cremonese Roma), 66-68 · Zbl 0199.24102
[17] Trotter, W. T., Combinatorics and Partially Ordered Sets: Dimension Theory (1992), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0764.05001
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.