Fence (mathematics)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The Hasse diagram of a six-element fence.

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:

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. 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 (sequence A001250 in OEIS).

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 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.[5] 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).

Notes[edit]

  1. ^ André (1881).
  2. ^ Gansner (1982) calls the fact that this lattice has a Fibonacci number of elements a “well known fact,” while Stanley (1986) asks for a description of it in an exercise. See also Höft & Höft (1985), Beck (1990), and Salvi & Salvi (2008).
  3. ^ Valdes, Tarjan & Lawler (1982).
  4. ^ Currie & Visentin (1991); Duffus et al. (1992); Rutkowski (1992a); Rutkowski (1992b); Farley (1995).
  5. ^ Gansner (1982).

References[edit]

External links[edit]