fence (mathematics)
{{short description|Partially ordered set with alternatingly-related elements}}
File:Zigzag poset.svg of a six-element fence.]]
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:
:
or
:
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.{{harvtxt|André|1881}}. The solutions to this counting problem, the so-called Euler zigzag numbers or up/down numbers, are:
:
:{{OEIS|A001250}}.
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.{{harvtxt|Gansner|1982}} calls the fact that this lattice has a Fibonacci number of elements a “well known fact,” while {{harvtxt|Stanley|1986}} asks for a description of it in an exercise. See also {{harvtxt|Höft|Höft|1985}}, {{harvtxt|Beck|1990}}, and {{harvtxt|Salvi|Salvi|2008}}.
A partially ordered set is series-parallel if and only if it does not have four elements forming a fence.{{harvtxt|Valdes|Tarjan|Lawler|1982}}.
Several authors have also investigated the number of order-preserving maps from fences to themselves, or to fences of other sizes.{{harvtxt|Currie|Visentin|1991}}; {{harvtxt|Duffus|Rödl|Sands|Woodrow|1992}}; {{harvtxt|Rutkowski|1992a}}; {{harvtxt|Rutkowski|1992b}}; {{harvtxt|Farley|1995}}.
An up-down poset {{math|Q(a,b)}} is a generalization of a zigzag poset in which there are {{mvar|a}} downward orientations for every upward one and {{mvar|b}} total elements.{{harvtxt|Gansner|1982}}. For instance, {{math|Q(2,9)}} has the elements and relations
:
In this notation, a fence is a partially ordered set of the form {{math|Q(1,n)}}.
References
{{reflist}}
{{refbegin|2}}
- {{citation
| last = André | first = Désiré
| journal = J. Math. Pures Appl.
| series = (Ser. 3)
| pages = 167–184
| title = Sur les permutations alternées
| volume = 7
| year = 1881}}.
- {{citation
| last = Beck | first = István
| mr = 1051291
| issue = 2
| journal = Fibonacci Quarterly
| pages = 172–174
| title = Partial orders and the Fibonacci numbers
| volume = 28
| year = 1990| doi = 10.1080/00150517.1990.12429508
}}.
- {{citation
| last1 = Currie | first1 = J. D.
| last2 = Visentin | first2 = T. I.
| doi = 10.1007/BF00383399
| mr = 1137906
| issue = 2
| journal = Order
| pages = 133–142
| title = The number of order-preserving maps of fences and crowns
| volume = 8
| year = 1991| hdl = 10680/1724
| s2cid = 122356472
| hdl-access = free
}}.
- {{citation
| last1 = Duffus | first1 = Dwight | author1-link = Dwight Duffus
| last2 = Rödl | first2 = Vojtěch
| last3 = Sands | first3 = Bill
| last4 = Woodrow | first4 = Robert
| doi = 10.1007/BF00419036
| mr = 1194849
| issue = 1
| journal = Order
| pages = 15–29
| title = Enumeration of order preserving maps
| volume = 9
| year = 1992| s2cid = 84180809 }}.
- {{citation
| last = Farley | first = Jonathan David
| doi = 10.1007/BF01108588
| mr = 1336535
| issue = 1
| journal = Order
| pages = 5–44
| title = The number of order-preserving maps between fences and crowns
| volume = 12
| year = 1995| s2cid = 120372679
}}.
- {{citation
| last = Gansner | first = Emden R.
| doi = 10.1016/0012-365X(82)90134-0
| mr = 675856
| issue = 2
| journal = Discrete Mathematics
| pages = 113–122
| title = On the lattice of order ideals of an up-down poset
| volume = 39
| year = 1982| doi-access = free
}}.
- {{citation
| last1 = Höft | first1 = Hartmut
| last2 = Höft | first2 = Margret
| mr = 806293
| issue = 3
| journal = Fibonacci Quarterly
| pages = 232–237
| title = A Fibonacci sequence of distributive lattices
| volume = 23
| year = 1985| doi = 10.1080/00150517.1985.12429817
}}.
- {{citation
| last1 = Kelly | first1 = David
| last2 = Rival | first2 = Ivan | author2-link = Ivan Rival
| mr = 0417003
| journal = Canadian Journal of Mathematics
| pages = 1257–1271
| title = Crowns, fences, and dismantlable lattices
| volume = 26
| year = 1974 | issue = 5
| doi=10.4153/cjm-1974-120-2| doi-access = free
}}.
- {{citation
| last = Rutkowski | first = Aleksander
| doi = 10.1007/BF00419037
| mr = 1194850
| issue = 1
| journal = Order
| pages = 31–42
| title = The number of strictly increasing mappings of fences
| volume = 9
| year = 1992a| s2cid = 120965362
}}.
- {{citation
| last = Rutkowski | first = Aleksander
| doi = 10.1007/BF00814405
| mr = 1199291
| issue = 2
| journal = Order
| pages = 127–137
| title = The formula for the number of order-preserving self-mappings of a fence
| volume = 9
| year = 1992b| s2cid = 121879635
}}.
- {{citation
| last1 = Salvi | first1 = Rodolfo
| last2 = Salvi | first2 = Norma Zagaglia
| mr = 2414008
| journal = Ars Combinatoria
| pages = 105–117
| title = Alternating unimodal sequences of Whitney numbers
| volume = 87
| year = 2008}}.
- {{citation
| last = Stanley | first = Richard P. | authorlink = Richard P. Stanley
| title = Enumerative Combinatorics
| year = 1986
| publisher = Wadsworth, Inc.}} Exercise 3.23a, page 157.
- {{citation
| last1 = Valdes | first1 = Jacobo
| last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
| last3 = Lawler | first3 = Eugene L. | author3-link = Eugene Lawler
| doi = 10.1137/0211023
| issue = 2
| journal = SIAM Journal on Computing
| pages = 298–313
| title = The Recognition of Series Parallel Digraphs
| volume = 11
| year = 1982}}.
{{refend}}
External links
- {{mathworld|title=Fence Poset|urlname=FencePoset}}