In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory of free probability.
Contents |
Definition
A partition of a set S is a pairwise disjoint set of non-empty subsets, called "parts" or "blocks", whose union is all of S. Consider a finite set that is linearly ordered, or (equivalently, for purposes of this definition) arranged in a cyclic order like the vertices of a regular n-gon. No generality is lost by taking this set to be S = { 1, ..., n }. A noncrossing partition of S is a partition in which no two blocks "cross" each other, i.e., if a and b belong to one block and x and y to another, they are not arranged in the order a x b y. If one draws an arch based at a and b, and another arch based at x and y, then the two arches cross each other if the order is a x b y but not if it is a x y b or a b x y. In the latter two orders the partition { { a, b }, { x, y } } is noncrossing.
| Crossing: | a x b y |
| Noncrossing: | a x y b |
| Noncrossing: | a b x y |
Equivalently, if we label the vertices of a regular n-gon with the numbers 1 through n, the convex hulls of different blocks of the partition are disjoint from each other, i.e., they also do not "cross" each other.
Lattice structure
Like the set of all partitions of the set { 1, ..., n }, the set of all noncrossing partitions is a lattice when partially ordered by saying that a finer partition is "less than" a coarser partition. However, although it is a subset of the lattice of all partitions, it is not a sublattice of the lattice of all partitions, because the join operations do not agree. In other words, the finest partition that is coarser than both of two noncrossing partitions is not always the finest noncrossing partition that is coarser than both of them.
Unlike the lattice of all partitions of the set, the lattice of all noncrossing partitions of a set is self-dual, i.e., it is order-isomorphic to the lattice that results from inverting the partial order ("turning it upside-down"). This can be seen by observing that each noncrossing partition has a complement. Indeed, every interval within this lattice is self-dual.
How many noncrossing partitions does a finite set have?
The set of all noncrossing partitions is one of many sets enumerated by the Catalan numbers, i.e., the number of noncrossing partitions of a set of size n is
Role in free probability theory
The lattice of noncrossing partitions plays the same role in defining "free cumulants" in free probability theory that is played by the lattice of all partitions in defining joint cumulants in classical probability theory. See also Wigner semicircle distribution.
References
- Germain Kreweras, "Sur les partitions non croisées d'un cycle", Discrete Mathematics, volume 1, number 4, pages 333–350, 1972.
- Rodica Simion, "Noncrossing partitions", Discrete Mathematics, volume 217, numbers 1–3, pages 367–409, April 2000.
- Roland Speicher, "Free probability and noncrossing partitions", Séminaire Lotharingien de Combinatoire, B39c (1997), 38 pages, 1997
Open source encyclopedia content modification information:
This page was last modified on 7 March 2010 at 19:53.
Authorship and Review
Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.
Usage Guidelines
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Noncrossing partition", which is available in its original form here:
http://en.wikipedia.org/w/index.php?title=Noncrossing_partition
All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.