Non-crossing partition

from Wikipedia, the free encyclopedia
There are 42 non-crossing (top) and 10 crossing (bottom) partitions of a 5-element set
The partial order on the 14 non-crossing partitions of a 4-element set is shown here by a Hasse diagram . The Kreweras complement is obtained by reflection on the horizontal central axis

Non-crossing partitions were introduced by Germain Kreweras in combinatorics and have since played an important role in various mathematical fields. In particular, they are of great importance in free probability theory .

definition

A partition of a set is a division of non-empty subsets (which are called blocks of the partition) into pairwise disjoint , the union of which results. If the finite set is linearly ordered , then one can consider non-crossing partitions. Without reservation, we can assume that is true. A non-crossing partition of is a partition whose blocks do not cross; d. i.e., there are none such that and are in the same block, and are in the same block, and these two blocks are different. Instead of arranging the points linearly, they can also be viewed cyclically arranged on a circle as the corner points of a regular corner . Then one can identify a block of a partition with the convex hull of its points, and the condition not crossing means that the blocks do not intersect in this graph.

The set of all non-crossing partitions of is denoted by. There is an obvious isomorphism between and for two finite linearly ordered sets of the same size. That means, it essentially only depends on the number of elements in . and we denote by the non-crossing partitions of a set with elements. The number of elements in is counted by the Catalan numbers .

Association structure

Just like the set of all partitions of , the set of all non-crossing partitions is a lattice with respect to the partial order , which is given by the refinement of the blocks. However, the lattice of non-crossing partitions is not a subset of all partitions. The partial order is the same for both lattices, but the maximum of two non-crossing partitions can be different in both lattices. (The minimum, however, is the same in both associations.)

In contrast to the association of all partitions, the association of the non-crossing partitions is self-dual, i.e. H. there is a bijective mapping (the so-called Kreweras complement ) of on itself, which reverses the partial order.

Significance in free probability theory

The association of the non-crossing partitions plays the same role in the definition of the free cumulants in the free probability theory as the association of all partitions in the definition of the usual cumulants in the classical probability theory . Let be a non-commutative probability space and a non-commutative random variable with free cumulants . Then the free moment cumulative formula applies

,

where denotes the number of elements of the block .

This is the free counterpart to the classic moment-cumulative formula .

Individual evidence

  1. Germain Kreweras: Sur les partitions non croisées d'un cycle. Discrete Mathematics, volume 1, number 4, pp. 333-350, 1972.
  2. Rodica Simion: noncrossing partitions. Discrete Mathematics, volume 217, numbers 1-3, pp. 367-409, April 2000.
  3. Roland Speicher: Free probability and noncrossing partitions. Séminaire Lotharingien de Combinatoire, B39c (1997).