Fence (mathematics) explained

In mathematics, a fence, also called a zigzag poset, is a partially ordered set (poset) in which the order relations form a path with alternating orientations:

a<b>c<d>e<f>h<i … ora>b<c>d<e>f<h>i … A fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions. The incidence posets of path graphs form examples of fences.

A linear extension of a fence is called an alternating permutation; André's problem of counting the number of different linear extensions has been studied since the 19th century.^[1] The solutions to this counting problem, the so-called Euler zigzag numbers or up/down numbers, are:

1 , 1 , 2 , 4 , 10 , 32 , 122 , 544 , 2770 , 15872 , 101042 .

.

The number of antichains in a fence is a Fibonacci number; the distributive lattice with this many elements, generated from a fence via Birkhoff's representation theorem, has as its graph the Fibonacci cube.^[2]

A partially ordered set is series-parallel if and only if it does not have four elements forming a fence.^[3]

Several authors have also investigated the number of order-preserving maps from fences to themselves, or to fences of other sizes.^[4]

An up-down poset is a generalization of a zigzag poset in which there are downward orientations for every upward one and total elements.^[5] For instance, has the elements and relations

a>b>c<d>e>f<g>h>i. In this notation, a fence is a partially ordered set of the form .

References

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• Exercise 3.23a, page 157.
• .

Notes and References

1. .
2. calls the fact that this lattice has a Fibonacci number of elements a “well known fact,” while asks for a description of it in an exercise. See also,, and .
3. .

4. ; ; ; .

5. .