Forbidden induced partial orders
type: Item
instance of: scholarly article
title: Forbidden induced partial orders
zbMATH Open document ID: 0940.06003
DOI: 10.1016/S0012-365X(98)00312-4
author: David A. Grable
author: Hans Jürgen Prömel
author: Graham Brightwell
published in: Discrete Mathematics
publication date: 1999-12-12T00:00:00Z
review text: 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.).
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 1334538
zbMATH Keywords: forbidden induced partial order
zbMATH Keywords: asymptotic formula
reviewed by: Jiří Rachůnek
MaRDI profile type: Publication
cites work: On the entropy values of hereditary classes of graphs
cites work: Minimal Regular Graphs of Girths Eight and Twelve
cites work: Q5688999
cites work: The number of partial orders of fixed width
cites work: The average number of linear extensions of a partial order
cites work: Incidence posets of trees in posets of large dimension
cites work: On the probability of connectedness
cites work: Q4918392
cites work: Betweenness, orders and interval graphs
cites work: Transitiv orientierbare Graphen
cites work: Asymptotic Enumeration of Partial Orders on a Finite Set
cites work: New examples of graphs without small cycles and of large size
cites work: Properties of certain families of \(2k\)-cycle-free graphs
cites work: Excluding Induced Subgraphs III: A General Asymptotic
cites work: Enumeration of Posets Generated by Disjoint Unions and Ordinal Sums
cites work: Q5597374
cites work: Q4004146
Recommended article: Q3971999
Recommended article: On induction principles for partial orders
Recommended article: Forbidden configurations for distributive and modular ordered sets
Recommended article: A New Class of Partial Orders
Recommended article: Partial orders induced by quasilinear clones
Recommended article: Q4013051
Recommended article: Partial orders based on outer inverses
Recommended article: Forbidden induced subgraphs
Recommended article: Two forbidden induced subgraphs and well-quasi-ordering
Recommended article: Q4732498
description: scientific article; zbMATH DE number 1334538