Forbidden induced partial orders (Q1301728): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:51, 5 March 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