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

(poset) in which the order relations 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 particip ...
, 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 extensi ...
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. 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 wid ...
s in a fence is a
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a 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 sequence from ...
; 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 lattice ...
, has as its graph the
Fibonacci cube In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs ...
. 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 map In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
s 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 In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "sh ...
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 generally ...
of a
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
). #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 track ...
is cartesian closed. The
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
s 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