**Finite classes:**

Every set of more then three forbidden suborders with three elements or less is finite as is every class of partial orders with limited height or width.

Empty class: #{}

Height 1 Width 1: #{[1]}

Height 2 Chains: #{[1],[1 1]}

Width 2 Chains: #{[1], [2]}

Height 2 Width 2: #{[1],[1 1], [1 2], {[1] 1, [1 1] 2}, [2], [2 1], [2 2]}

Height 2 Width 2 Weak Orders: #{[1], [1 1], [1 2], [2], [2 1], [2], [2 2]}

Height 2 Width 2 Upper Forests: #{[1],[1 1], {[1] 1, [1 1] 2}, [2], [2 1], [2 2]}

Height 2 Width 2 Lower Forests: #{[1],[1 1], {[1], [1 1] 2}, [2], [1 2], [2 2]}

Weak sets of lists: #{[1], [1 1], [2]}

Restricting the set of weak sets of lists to height two or width two has no effect on its set of values.

**Classes with a single forbidden element:**

Once we consider classes of partial orders with infinite elements things get to be much more interesting. To begin with lets consider classes defined by a single forbidden element:

Antichains: [n]

Total orders: T_n

Weak orders: e.g [1 2 1], [1 2 2 1], [1 3 3 1]

Upper/Lower Forests: e.g [{[1] 1, [1 1] 1} 1]

Height 2: e.g [1 2], {[1] 2, [1 1] 1}

Width 2: e.g [1 1 1], [2 2]

**Classes with two forbidden elements:**

Here are the sets defined by two forbidden elements rather then a single one:

Sets of lists: e.g {[1] 2, [1 1] 1}, {[1 1] 1, [1 1 1] 2, [1 1 1 1] 4}

Height 2 Weak Orders: [n k]

Width 2 Weak Orders: e.g [1 1 2 2 1 2 1 2 1 1 1 2 1 2 1 1 1 ... ]

Reductions/Antireductions: e.g {[1] 2, [2 1] 1, [3 1] 2, [4 1] 1}

Weak upper/lower forests: [n 1 1 1 1 ...] or [... 1 1 1 1 1 n]

Width 2 Upper/lower forests: [{T_a, T_b} T_c]

**Classes with three forbidden elements:**

All infinite classes with three elements are forests of some sort because the width 2 height 2 class is finite:

Width 2 sets of lists: {T_n, T_k}

Height 2 sets of lists: {[1] n, [1 1] k} Width 2 weak upper/lower forests: [2 T_n] or [T_n 2]

Height 2 weak upper/lower forests: [n] and [n 1] or [1 n]

## No comments:

## Post a Comment