Fence (mathematics)
Encyclopedia
In mathematics
, a fence, also called a zigzag poset, is a partially ordered set
in which the order relations form a path
with alternating orientations:
or
A fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.
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. The solutions to this counting problem, the so-called Euler zigzag numbers or up/down numbers, are
The number of antichain
s 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
.
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 Q(a,b) is a generalization of a zigzag poset in which there are a downward orientations for every upward one and b total elements. For instance, Q(2,9) has the elements and relations
In this notation, a fence is a partially ordered set of the form Q(1,n).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a fence, also called a zigzag poset, is a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...
in which the order relations form a path
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
with alternating orientations:
- a < b > c < d > e < f > h < i ...
or
- a > 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.
A linear extension
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...
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
Antichain
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
s in a fence is a Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
; the distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for 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 union and intersection...
with this many elements, generated from a fence via Birkhoff's representation theorem
Birkhoff's representation theorem
In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...
, has as its graph the Fibonacci cube
Fibonacci cube
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, but with a Fibonacci number of vertices, studied in graph-theoretic mathematics...
.
A partially ordered set is series-parallel
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations....
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 Q(a,b) is a generalization of a zigzag poset in which there are a downward orientations for every upward one and b total elements. For instance, Q(2,9) 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 Q(1,n).