Forbidden induced partial orders (Q1301728): Difference between revisions

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.).