Lovasz Problem 11.8: triangle-free unit vector systems sum to Theta(n^(2/3))Research Paper
Let be unit vectors in a Euclidean space such that among any three of them some two are orthogonal. How large can be?
190 missions · 135 completed
Let be unit vectors in a Euclidean space such that among any three of them some two are orthogonal. How large can be?
A polyhedral cone can be described in two ways: as the set of nonnegative combinations of finitely many vectors (a finitely generated cone), or as the intersection of finitely many closed half-spaces through the origin. That the two descriptions give the same class of sets is the Minkowski–Weyl theorem. It is the structural basis of linear programming: the…
The combinatorial diameter of a polyhedron is the largest distance, in its vertex-edge graph, between two vertices. It is a lower bound on the number of pivots any edge-following method such as the simplex method needs in the worst case, which is why the polynomial Hirsch conjecture — the diameter of is bounded by a…
A convex polytope has both geometric coordinates and a finite pattern of faces. Moving its vertices can change distances and angles while preserving which vertices belong to which faces. Enumeration by combinatorial type asks for those incidence patterns, with geometrically different realizations of the same pattern counted together. Grünbaum’s enumeration…
A vector whose coordinates are all zero or one records a collection of yes-or-no choices. Taking the convex hull of a collection of these vectors gives a 0/1-polytope, also called a binary polytope. Such objects connect discrete choices with geometry: points describe feasible combinations, while supporting inequalities describe restrictions that every…
A convex combination expresses a point as a weighted average of other points. Such representations connect geometric sets with finite lists of coordinates and coefficients. A point in a convex hull may initially be described using many generators, even when the ambient space has small dimension. Carathéodory's theorem gives a bound depending only on that…
A polytope can be represented by cutting a higher-dimensional simplex with an affine flat. The geometry of the cut determines the resulting polytope. Perles's prescribed-point theorem adds a constraint to this representation: the cutting flat must pass through a point chosen in advance inside the simplex. Theorem 5.1.10 in Branko Grünbaum's Convex Polytopes,…
A convex polytope has geometric coordinates and a combinatorial structure: its faces, ordered by inclusion. Different coordinates can describe the same combinatorial type. Gale transforms connect these viewpoints by encoding affine dependencies among the vertices as another point configuration, often in a smaller-dimensional space.
A convex set contains the segment joining any two of its points. For a bounded closed convex set in finite-dimensional real space, extreme points describe the set through convex combinations. An extreme point cannot lie strictly between two distinct points of the set. Allowing unbounded sets introduces a second ingredient: directions in which one can move…
A convex polytope has both a geometric realization and a finite combinatorial structure: its faces, ordered by inclusion. Reconstruction asks how much of that structure must be known before the rest is forced. Chapter 12 of Branko Grünbaum's Convex Polytopes distinguishes several forms of unambiguity and then proves reconstruction results for general…
A convex polytope carries more than its underlying topological ball. Its faces form a finite complex whose incidence relations record the polytope's combinatorial structure. Chapter 11 of Branko Grünbaum's Convex Polytopes asks how this structure can be represented by subdivisions and by embeddings into Euclidean spaces of smaller dimension. The first…
A neighborly family of convex polytopes is a collection in which every two distinct members meet in the largest dimension possible without having a full-dimensional overlap: their intersection has codimension one. The question is extremal. For a fixed ambient dimension, how large can such a family be when its members must also satisfy a geometric…
A convex polytope can be studied metrically, through coordinates and lengths, or combinatorially, through the inclusion order of its faces. Grünbaum's Convex Polytopes develops the second viewpoint systematically: two polytopes have the same combinatorial type when their complete face posets are order-isomorphic. Chapter 7 studies neighborly polytopes,…
A basic classification question in polytope theory asks what combinatorial types can occur when the dimension and number of vertices are fixed. The question is not merely whether there are finitely many types. Effective enumeration asks for a uniform algorithm which produces the complete list, with no omissions and no repeated combinatorial type. This…
A polytope can be represented not only by vertices or supporting inequalities, but also as a section of a simplex in a higher-dimensional space. Perles's prescribed-point theorem strengthens this representation: the cutting flat can be required to pass through an interior point selected in advance. This is Theorem 5.1.10 in Branko Grünbaum's Convex Polytopes…
The face structure of a cube is unusually regular: its vertices, edges, and higher dimensional faces are indexed by choices of fixed and free coordinates. A natural realization question asks how much of this structure can survive in a polytope of lower dimension. In §4.9 of Convex Polytopes, Grünbaum reports the Joswig–Ziegler construction of neighborly…
A polytope may be described by its vertices or by its facets. These descriptions can differ sharply in size even when every vertex has only binary coordinates. Grünbaum's account of 0/1-polytopes in §4.9 records a result of Bárány and Pór: the maximal number of facets grows superexponentially with dimension. The result is an existence statement about the…
Convex hulls are often defined using arbitrary finite convex combinations. In finite dimensional geometry, Carathéodory's theorem gives a uniform bound on how many points are needed to represent any one point of the hull. This is the finite representation result stated in Branko Grünbaum's Convex Polytopes, second edition (2003), §2.3, Theorem 2.3.5,…
This mission asks how restrictions on collinear and cocircular points limit the reuse of distances in the plane. Its central question is Erdős Problem 98: must the minimum number of distances grow faster than the number of points?
A space group describes the rigid motions compatible with a periodic spatial symmetry. The classification concerns possible symmetry types, rather than the size or shape of a particular drawing of a crystal. The classical three-dimensional numbers are 230, 219 when mirror-related types are identified, and 65 for the orientation-preserving subfamily. These…
Placing points on the unit sphere so as to minimize the logarithmic energy
Three-dimensional packing occurs when a collection of parts must share a container and its volume determines a cost. In additive manufacturing, the orientation of a part can be chosen before its position because orientation affects surface quality, support requirements, and production time. A mathematical version therefore keeps each shape's orientation…
Non-expansive maps of a metric space into the real line with small average distortion are a standard rounding device for graph partitioning. A relaxation (a linear or semidefinite program) produces a metric on the vertices; a 1-Lipschitz map to the line that preserves the average distance up to a factor is then thresholded into a cut, and becomes the…
A randomized algorithm is ρ-replicable if two runs on independent samples, sharing their random seed, return the same output with probability at least (Impagliazzo–Lei–Pitassi–Sorrell 2022). Many replicable algorithms (PAC learning, bandits, hypothesis testing) reduce to replicable mean estimation in . Hopkins, Impagliazzo, Kane, Liu and…
A Delaunay triangulation of a finite point set is a triangulation in which the open circumdisk of every triangle contains no point of . Its stretch factor is the worst ratio over pairs of , where is the length of a shortest path from to along the edges of . A uniform bound on this ratio makes…