Home

noncrossing

Noncrossing describes a property of a configuration in which the elements can be drawn in the plane so that no two elements cross each other. In common visualizations, points lie on a circle or a line, and connections are drawn as curves or straight segments inside the region. A configuration is noncrossing if no pair of connections intersect in their interior.

In combinatorics, a central instance is the noncrossing partition. A partition of a finite ordered set is

Related structures include noncrossing matchings and noncrossing graphs. A noncrossing matching on 2n points on a

Applications of noncrossing concepts appear in several areas. In free probability, moment and cumulant relations are

noncrossing
if
there
do
not
exist
elements
a
<
b
<
c
<
d
with
a
and
c
in
one
block
and
b
and
d
in
another.
When
the
elements
are
placed
on
a
circle
and
blocks
are
connected
by
convex
hulls,
the
hulls
do
not
cross.
Noncrossing
partitions
form
a
lattice
under
refinement,
and
they
have
rich
algebraic
and
geometric
structures.
The
number
of
noncrossing
partitions
of
an
n-element
set
equals
the
Catalan
number
C_n,
where
C_n
=
(1/(n+1))
*
binomial(2n,
n).
circle
is
a
set
of
n
disjoint
chords
that
do
not
cross;
the
count
of
such
matchings
is
also
C_n.
A
noncrossing
set
of
diagonals
in
a
convex
polygon
yields
triangulations,
which
are
counted
by
Catalan
numbers
as
well.
organized
using
noncrossing
partitions.
In
geometry
and
computer
science,
noncrossing
graphs
underpin
polygon
triangulations
and
outerplanar
graphs.
The
concept
serves
as
a
unifying
theme
for
various
counting,
geometric,
and
algebraic
problems.