Sunday, August 25, 2013

Forbidding posets with less then four elements

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