In mathematics, Ky Fan's lemma (KFL) is a combinatorial lemma about labellings of triangulations. It is a generalization of Tucker's lemma. It was proved by Ky Fan in 1952. [1]
Contents
In mathematics, Ky Fan's lemma (KFL) is a combinatorial lemma about labellings of triangulations. It is a generalization of Tucker's lemma. It was proved by Ky Fan in 1952. [1]
KFL uses the following concepts.
Let T be a boundary-antipodally-symmetric triangulation of and L a boundary-odd labeling of T.
If L has no complementary edge, then L has an odd number of n-dimensional alternating simplices.
By definition, an n-dimensional alternating simplex must have labels with n + 1 different sizes.
This means that, if the labeling L uses only n different sizes (i.e. ), it cannot have an n-dimensional alternating simplex.
Hence, by KFL, L must have a complementary edge.
KFL can be proved constructively based on a path-based algorithm. The algorithm it starts at a certain point or edge of the triangulation, then goes from simplex to simplex according to prescribed rules, until it is not possible to proceed any more. It can be proved that the path must end in an alternating simplex.
The proof is by induction on n.
The basis is . In this case, is the interval and its boundary is the set . The labeling L is boundary-odd, so . Without loss of generality, assume that and . Start at −1 and go right. At some edge e, the labeling must change from negative to positive. Since L has no complementary edges, e must have a negative label and a positive label with a different size (e.g. −1 and +2); this means that e is a 1-dimensional alternating simplex. Moreover, if at any point the labeling changes again from positive to negative, then this change makes a second alternating simplex, and by the same reasoning as before there must be a third alternating simplex later. Hence, the number of alternating simplices is odd.
The following description illustrates the induction step for . In this case is a disc and its boundary is a circle. The labeling L is boundary-odd, so in particular for some point v on the boundary. Split the boundary circle to two semi-circles and treat each semi-circle as an interval. By the induction basis, this interval must have an alternating simplex, e.g. an edge with labels (+1,−2). Moreover, the number of such edges on both intervals is odd. Using the boundary criterion, on the boundary we have an odd number of edges where the smaller number is positive and the larger negative, and an odd number of edges where the smaller number is negative and the larger positive. We call the former decreasing, the latter increasing.
There are two kinds of triangles.
By induction, this proof can be extended to any dimension.
In mathematics, the Borsuk–Ulam theorem states that every continuous function from an n-sphere into Euclidean n-space maps some pair of antipodal points to the same point. Here, two points on a sphere are called antipodal if they are in exactly opposite directions from the sphere's center.
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points. This maximizes the size of the smallest angle in any of the triangles, and tends to avoid sliver triangles.
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,
In geometry, a hypercube is an n-dimensional analogue of a square and a cube ; the special case for n = 4 is known as a tesseract. It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length. A unit hypercube's longest diagonal in n dimensions is equal to .
In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.
In mathematics, the term homology, originally introduced in algebraic topology, has three primary, closely-related usages. The most direct usage of the term is to take the homology of a chain complex, resulting in a sequence of abelian groups called homology groups. This operation, in turn, allows one to associate various named homologies or homology theories to various other types of mathematical objects. Lastly, since there are many homology theories for topological spaces that produce the same answer, one also often speaks of the homology of a topological space. There is also a related notion of the cohomology of a cochain complex, giving rise to various cohomology theories, in addition to the notion of the cohomology of a topological space.
In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their n-dimensional counterparts. Simplicial complexes should not be confused with the more abstract notion of a simplicial set appearing in modern simplicial homotopy theory. The purely combinatorial counterpart to a simplicial complex is an abstract simplicial complex. To distinguish a simplicial complex from an abstract simplicial complex, the former is often called a geometric simplicial complex.
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring of a triangulation of an -dimensional simplex contains a cell whose vertices all have different colors.
In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension on simplicial complexes is a canonical method to refine them. Therefore, the barycentric subdivision is an important tool in algebraic topology.
In algebraic topology, simplicial homology is the sequence of homology groups of a simplicial complex. It formalizes the idea of the number of holes of a given dimension in the complex. This generalizes the number of connected components.
In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.
In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
Causal dynamical triangulation (CDT), theorized by Renate Loll, Jan Ambjørn and Jerzy Jurkiewicz, is an approach to quantum gravity that, like loop quantum gravity, is background independent.
In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex, compact subset of a Euclidean space to have a fixed point, i.e. a point which is mapped to a set containing it. The Kakutani fixed point theorem is a generalization of the Brouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result in topology which proves the existence of fixed points for continuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions.
In graph theory, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.
In mathematics, Tucker's lemma is a combinatorial analog of the Borsuk–Ulam theorem, named after Albert W. Tucker.
In mathematics, a shelling of a simplicial complex is a way of gluing it together from its maximal simplices in a well-behaved way. A complex admitting a shelling is called shellable.
In geometry, Monsky's theorem states that it is not possible to dissect a square into an odd number of triangles of equal area. In other words, a square does not have an odd equidissection.
The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the partners, and ask the partners only simple queries such as "which piece do you prefer?".
