10 Theorems in discrete geometry

In polyhedral combinatorics, a branch of mathematics, Balinski's theorem is a statement about the graph-theoretic structure of three-dimensional polyhedra and higher-dimensional polytopes. It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional polyhedron or polytope, then the resulting graph is at least d-vertex-connected: the removal of any d − 1 vertices leaves a connected subgraph. For instance, for a three-dimensional polyhedron, even if two of its vertices are removed, for any pair of vertices there will still exist a path of vertices and edges connecting the pair.

Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of Rd lies in the convex hull of a set P, then x can be written as the convex combination of at most d + 1 points in P. Namely, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where . The smallest r that makes the last statement valid for each x in the convex hull of P is defined as the Carathéodory's number of P. Depending on the properties of P, upper bounds lower than the one provided by Carathéodory's theorem can be obtained. Note that P need not be itself convex. A consequence of this is that P′ can always be extremal in P, as non-extremal points can be removed from P without changing the membership of x in the convex hull.

In a 1969 paper, Dutch mathematician Nicolaas Govert de Bruijn proved several results about packing congruent rectangular bricks into larger rectangular boxes, in such a way that no space is left over. One of these results is now known as de Bruijn's theorem. According to this theorem, a "harmonic brick" can only be packed into a box whose dimensions are multiples of the brick's dimensions.

In mathematics, the Erdős–Szekeres theorem is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every infinite sequence of distinct real numbers contains a monotonically increasing infinite subsequence or a monotonically decreasing infinite subsequence, the result proved by Paul Erdős and George Szekeres goes further. For given r, s they showed that any sequence of distinct real numbers with length at least (r − 1)(s − 1) + 1 contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s. The proof appeared in the same 1935 paper that mentions the Happy Ending problem.

The classical four-vertex theorem of geometry states that the curvature function of a simple, closed, smooth plane curve has at least four local extrema. The name of the theorem derives from the convention of calling an extreme point of the curvature function a vertex. This theorem has many generalizations, including a version for space curves where a vertex is defined as a point of vanishing torsion.

Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Radon (1921) and König (1922) had already appeared. Helly's theorem gave rise to the notion of a Helly family.

In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).

The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

In discrete geometry, Tverberg's theorem, first stated by Helge Tverberg (1966), is the result that sufficiently many points in d-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any set of

In geometry, the Wallace–Bolyai–Gerwien theorem, named after William Wallace, Farkas Bolyai and Paul Gerwien, is a theorem related to dissections of polygons. It answers the question when one polygon can be formed from another by cutting it into a finite number of pieces and recomposing these by translations and rotations. The Wallace–Bolyai–Gerwien theorem states that this can be done if and only if two polygons have the same area.