Fence (mathematics)

In mathematics, a fence, also called a zigzag poset, is a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binar ...

(poset) in which the order

relations Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...

form a path with alternating orientations: :

a

ceh or : $a>b d f i \cdots$ A fence may be
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb Traditionally, a finite verb (from la, fīnītus, past partici ...
, or it may be formed by an infinite alternating sequence extending in both directions. The
incidence poset In mathematics, an incidence poset or incidence order is a type of partially ordered set that represents the incidence relation between vertices and edges of an undirected graph. The incidence poset of a graph ''G'' has an element for each vertex or ...
s of
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
s form examples of fences. A
linear extension In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear ext ...
of a fence is called an alternating permutation;
André's problem In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry. For example, the five alte ...
of counting the number of different linear extensions has been studied since the 19th century. 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
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its w ...
s in a fence is a
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
; the
distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set ...
with this many elements, generated from a fence via
Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive latti ...
, has as its graph the Fibonacci cube. A partially ordered set is series-parallel if and only if it does not have four elements forming a fence. Several authors have also investigated the number of order-preserving maps from fences to themselves, or to fences of other sizes. An up-down poset is a generalization of a zigzag poset in which there are downward orientations for every upward one and total elements.. For instance, has the elements and relations : $a>b>c e>f h>i.$ In this notation, a fence is a partially ordered set of the form .

Equivalent conditions
The following conditions are equivalent for a poset : # is a
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...
of zigzag posets. #If in , either or . # $< \circ < \; = \emptyset$ , i.e. it is never the case that and , so that is vacuously transitive. # has dimension at most one (defined analogously to the
Krull dimension In commutative algebra, the Krull dimension of a commutative ring ''R'', named after Wolfgang Krull, is the supremum of the lengths of all chains of prime ideals. The Krull dimension need not be finite even for a Noetherian ring. More generall ...
of a commutative ring). #Every element of is either maximal or minimal. #The
slice category In mathematics, specifically category theory, an overcategory (and undercategory) is a distinguished class of categories used in multiple contexts, such as with covering spaces (espace etale). They were introduced as a mechanism for keeping trac ...
is
cartesian closed In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in math ...
. The prime ideals of a commutative ring , ordered by inclusion, satisfy the equivalent conditions above if and only if has Krull dimension at most one.

Notes

References
* . * . * . * . * . * . * . * . * . * . * . * Exercise 3.23a, page 157. * .

External links
* {{mathworld, title=Fence Poset, urlname=FencePoset Order theory Enumerative combinatorics