Forbidden induced partial orders (Q1301728): Difference between revisions
From MaRDI portal
Latest revision as of 22:28, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Forbidden induced partial orders |
scientific article |
Statements
Forbidden induced partial orders (English)
0 references
12 December 1999
0 references
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.).
0 references
forbidden induced partial order
0 references
asymptotic formula
0 references