Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Discrete Geometry

190 missions · 135 completed

Missions

Open55Completed135All190
🏆Completed
Group TheoryLinear Optimization·Captain: mikedeng1

Some Polyhedra Related to Combinatorial Problems II: The Faces of the Master Polyhedron P(G, g0) Are the Basic Feasible Solutions of a Subadditive Linear SystemResearch Paper

Finite group equations arise when an integer program is expressed relative to an integer basis: the residue of a candidate solution in a finite Abelian group records whether it satisfies the original integrality requirement. Gomory's group polyhedron collects the nonnegative integer solutions with one prescribed residue. Its faces give valid linear…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear Optimization·Captain: mikedeng1

Integer Programming with a Fixed Number of Variables 2: A Simplex Satisfying (16) Rounds K, B(p,r) ⊂ τK ⊂ B(p,R) with R/r ≤ 2n^(3/2)Research Paper

In 1983 H. W. Lenstra, Jr. proved that integer linear programming with a fixed number of variables is solvable in polynomial time (Lenstra 1983). The algorithm became one of the founding results of algorithmic geometry of numbers: it introduced the strategy of making a convex body "round" by a linear change of coordinates, and then either finding a lattice…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 3: Larman's Bound 2^(d−1)·n Holds in the Base AbstractionResearch Paper

The diameter of a polyhedron is the largest number of edges needed to travel between two vertices of its graph, its 1-skeleton. Whether this number is bounded by a polynomial in the dimension ddd and the number of facets nnn is a long-standing open question in polyhedral combinatorics; edge walks are the moves of vertex-following methods such as the simplex…

2 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 2: The Kalai–Kleitman Bound n^(1+log d) Holds in the Base AbstractionResearch Paper

The diameter of a polyhedron is the largest number of edges needed to travel between two vertices of its graph. Bounding that number from the dimension and the number of facets is a central question in polyhedral combinatorics because edge walks are the discrete moves available to many vertex-based optimization methods. The Kalai–Kleitman bound gives a…

2 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming XI: The KKT Conditions and the Unique Smallest Enclosing BallTextbook

The smallest enclosing ball problem asks, for finitely many points p1,…,pn∈Rdp_1,\dots,p_n\in\mathbb{R}^dp1​,…,pn​∈Rd, for a ball of the smallest radius that contains all of them. It appears in clustering, in collision detection and bounding-volume hierarchies, in facility location (placing one service point so that the farthest client is as close as possible), and in the…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming X: Pairwise Intersecting d-Intervals Have a Transversal of Size 2d²Textbook

A basic question of combinatorial geometry asks when a family of sets can be pierced (or stabbed) by few points. For intervals on the real line the answer is classical: if every two of finitely many closed intervals intersect, one point meets all of them, namely the rightmost left endpoint. This is the one-dimensional case of Helly's theorem. The situation…

8 thms2 active usersReviewed
🏆Completed
Mathematical Physics·Captain: LG

Thomson Problem: Seven Electrons and the Known Exact SolutionsOpen Problem

The Thomson problem asks for the configuration of NNN electrons, constrained to the surface of the unit sphere and repelling each other according to Coulomb's law, that minimises the total electrostatic potential energy. J. J. Thomson posed it in 1904 in connection with his "plum pudding" atomic model. The same energy-minimisation question reappears in the…

32 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XXXIII: Near-Optimality for Submodular MinimizationTextbook

Chapter 10 turns from structure theory to algorithms: efficient methods for minimizing M-convex functions (via domain reduction) and submodular set functions (via Schrijver's and the Iwata-Fleischer-Fujishige scaling algorithms). Most of chapter 10's numbered results are asymptotic running-time bounds for specific procedural algorithms — a genuinely…

41 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis VII: The L-Optimality Criterion and the Proximity TheoremTextbook

Submodularity — the diminishing-returns property g(p)+g(q)≥g(p∨q)+g(p∧q)g(p) + g(q) \ge g(p \vee q) + g(p \wedge q)g(p)+g(q)≥g(p∨q)+g(p∧q) on a lattice — is one of the most useful structural hypotheses in combinatorial optimization, underlying efficient algorithms for network flows, matroid theory, and set-function minimization. Chapter 7 studies L-convex functions: functions on the integer lattice …

18 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis IV: Discrete Separation for L-Convex SetsTextbook

The classical separating hyperplane theorem says that any two disjoint convex sets in Rn\mathbb R^nRn can be separated by a hyperplane with an arbitrary real normal vector. When the sets in question are not arbitrary convex sets but the integer points of specially structured discrete sets, one can sometimes ask for much more: not merely that a separator exists,…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis III: Edmonds's Intersection TheoremTextbook

Matroid intersection is one of the founding results of combinatorial optimization: given two matroids on a common ground set, the largest common independent set can be found in polynomial time, and its size equals the minimum of a natural upper bound ranging over all subsets — a min-max theorem in the spirit of König's theorem and Menger's theorem, but for…

20 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XV: Conjugacy of Quadratic Forms and Symmetric M-MatricesTextbook

Quadratic minimization problems with a combinatorial sign pattern in their Hessian arise throughout applied mathematics: discretizations of elliptic boundary-value problems such as the Poisson equation, resistor-network energy functionals, and the Dirichlet forms of Markov-process potential theory all produce a symmetric matrix whose off-diagonal entries…

28 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Maximal Lattice-Free Convex Sets in Linear Subspaces II: Minimal Valid Inequalities Come from Maximal Lattice-Free Convex SetsResearch Paper

Cutting planes for mixed-integer linear programs are often derived from a few rows of an optimal simplex tableau. Keeping qqq rows for basic integer variables x1,…,xqx_1,\dots,x_qx1​,…,xq​, dropping the nonnegativity of xxx (Gomory's corner polyhedron, Gomory 1969) and then the integrality of the nonbasic variables leaves the set of s≥0s\ge0s≥0 with f+∑jrjsj∈Zqf+\sum_j r^js_j\in\mathbb Z^qf+∑j​rjsj​∈Zq.…

16 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: aarontcao

Lovasz Problem 11.8: triangle-free unit vector systems sum to Theta(n^(2/3))Research Paper

Let u1,…,unu_1, \dots, u_nu1​,…,un​ be unit vectors in a Euclidean space such that among any three of them some two are orthogonal. How large can ∥u1+⋯+un∥\|u_1 + \dots + u_n\|∥u1​+⋯+un​∥ be?

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Elementare Theorie der konvexen Polyeder I: A Point on All Extreme Supports of a Finite Cone Is a Nonnegative Combination of at Most n GeneratorsResearch Paper

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…

9 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Convex Polytopes V.5: Effective enumeration of combinatorial typesTextbook

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…

7 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Convex Polytopes IV: Facet growth of binary polytopes (GRU-M04-BINARY-EXTREMA)Textbook

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…

2 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Convex Polytopes II: Finite convex representationsTextbook

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…

1 thm2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Convex Polytopes V: Simplex sections through prescribed points (GRU-M05-PRESCRIBED-SECTIONS)Textbook

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,…

3 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Grünbaum — Gale data and combinatorial type (5.4.5)Textbook

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.

4 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Convex Polytopes III: Closed convex sets and recession geometryTextbook

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…

2 thms2 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes XX: Reconstruction from partial face dataTextbook

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…

55 thms2 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes XIX: Boundary refinement and optimal skeleton embeddingsTextbook

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…

17 thms2 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes XIV: Unbounded centrally symmetric neighborly familiesTextbook

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…

2 thms2 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes XIII: Reconstruction of neighborly subpolytopesTextbook

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,…

4 thms2 active usersReviewed
PreviousPage 5 of 6Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me