fbpx
Wikipedia

Noncrossing partition

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. The number of noncrossing partitions of a set of n elements is the nth Catalan number. The number of noncrossing partitions of an n-element set with k blocks is found in the Narayana number triangle.

There are 42 noncrossing and 10 crossing partitions of a 5-element set
The 14 noncrossing partitions of a 4-element set ordered by refinement in a Hasse diagram

Definition edit

A partition of a set S is a set of non-empty, pairwise disjoint subsets of S, 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. The set of all non-crossing partitions of S is denoted  . There is an obvious order isomorphism between   and   for two finite sets   with the same size. That is,   depends essentially only on the size of   and we denote by   the non-crossing partitions on any set of size n.

Lattice structure edit

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 set partitions, it is not a sublattice, because the subset is not closed under the join operation in the larger lattice. 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 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 non-crossing complement. Indeed, every interval within this lattice is self-dual.

Role in free probability theory edit

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. To be more precise, let   be a non-commutative probability space (See free probability for terminology.),   a non-commutative random variable with free cumulants  . Then

 

where   denotes the number of blocks of length   in the non-crossing partition  . That is, the moments of a non-commutative random variable can be expressed as a sum of free cumulants over the sum non-crossing partitions. This is the free analogue of the moment-cumulant formula in classical probability. See also Wigner semicircle distribution.

References edit

  • 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

noncrossing, partition, combinatorial, mathematics, topic, noncrossing, partitions, assumed, some, importance, because, among, other, things, application, theory, free, probability, number, noncrossing, partitions, elements, catalan, number, number, noncrossin. 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 The number of noncrossing partitions of a set of n elements is the nth Catalan number The number of noncrossing partitions of an n element set with k blocks is found in the Narayana number triangle There are 42 noncrossing and 10 crossing partitions of a 5 element set The 14 noncrossing partitions of a 4 element set ordered by refinement in a Hasse diagram Contents 1 Definition 2 Lattice structure 3 Role in free probability theory 4 ReferencesDefinition editA partition of a set S is a set of non empty pairwise disjoint subsets of S 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 The set of all non crossing partitions of S is denoted NC S displaystyle text NC S nbsp There is an obvious order isomorphism between NC S 1 displaystyle text NC S 1 nbsp and NC S 2 displaystyle text NC S 2 nbsp for two finite sets S 1 S 2 displaystyle S 1 S 2 nbsp with the same size That is NC S displaystyle text NC S nbsp depends essentially only on the size of S displaystyle S nbsp and we denote by NC n displaystyle text NC n nbsp the non crossing partitions on any set of size n Lattice structure editLike 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 set partitions it is not a sublattice because the subset is not closed under the join operation in the larger lattice 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 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 non crossing complement Indeed every interval within this lattice is self dual Role in free probability theory editThe 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 To be more precise let A ϕ displaystyle mathcal A phi nbsp be a non commutative probability space See free probability for terminology a A displaystyle a in mathcal A nbsp a non commutative random variable with free cumulants k n n N displaystyle k n n in mathbb N nbsp Then ϕ a n p NC n j k j N j p displaystyle phi a n sum pi in text NC n prod j k j N j pi nbsp where N j p displaystyle N j pi nbsp denotes the number of blocks of length j displaystyle j nbsp in the non crossing partition p displaystyle pi nbsp That is the moments of a non commutative random variable can be expressed as a sum of free cumulants over the sum non crossing partitions This is the free analogue of the moment cumulant formula in classical probability See also Wigner semicircle distribution References editGermain Kreweras Sur les partitions non croisees 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 Seminaire Lotharingien de Combinatoire B39c 1997 38 pages 1997 Retrieved from https en wikipedia org w index php title Noncrossing partition amp oldid 1172683885, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.