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
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XIV: The König-Egerváry Theorem for Mixed MatricesTextbook

Every physical or engineering model built from linear relations mixes two kinds of numbers. Some coefficients are exact — the ±1\pm 1±1 entries recording Kirchhoff's current and voltage laws in an electrical network, or the incidence structure of a mechanical linkage — because they come from a topological or combinatorial fact, not a measurement. Others are…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XXXV: Gross Substitutes and Equilibrium PricesTextbook

This mission continues chapter 11's account of the M♮-concave/M♮-convex exchange-economy model begun in mission 14-economic-equilibrium, placing seven of that chunk's own results that were previously left out-of-cone: the two gross-substitutes-style characterizations of M♮-concavity (§11.3), the transfer theorem that lifts an equilibrium of the continuous…

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

Discrete Convex Analysis XXXI: The Potential Criterion for Network FlowsTextbook

Chapter 9 is where discrete convex analysis meets classical network flow theory: the minimum cost flow problem's three hallmark properties — an optimality criterion by potentials, an optimality criterion by negative cycles, and integrality of optimal solutions — are shown to survive, in a precise and increasingly general form, first for arbitrary polyhedral…

88 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XXX: Lagrangian Duality for M-Convex ProgramsTextbook

Missions 29-ch08b-conjugacyduality and 30-ch08c-conjugacyduality built the M2-/L2-convex function classes and proved their conjugacy correspondence is nearly complete. This mission finishes that correspondence (Theorems 8.48-8.49) and then turns to chapter 8's capstone application: a Lagrangian duality theory for integer programs, built entirely from the…

56 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis IX: The Discrete Conjugacy TheoremTextbook

The Legendre-Fenchel transform is the single most structurally important operation in convex analysis: for a proper closed convex function fff, its conjugate f∙(p)=sup⁡x{⟨p,x⟩−f(x)}f^\bullet(p) = \sup_x \{\langle p,x\rangle - f(x)\}f∙(p)=supx​{⟨p,x⟩−f(x)} is again proper closed convex, and the transform is an involution — f∙∙=ff^{\bullet\bullet} = ff∙∙=f. This one fact underlies duality theory across optimization:…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis VIII: Quasi L-Convex Functions and the Quasi-Proximity TheoremTextbook

Milgrom and Shannon's theory of quasi-supermodularity, developed for monotone comparative statics in economics, showed that many of the consequences of lattice submodularity survive under a much weaker, purely ordinal relaxation of the defining inequality. Chapter 7's final section imports this idea into discrete convex analysis: does L-convexity's…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XXI: The Exchange Axiom as Local OptimalityTextbook

Convexity on the integer lattice cannot be defined by the classical secant-line inequality alone: a function can be midpoint-convex along every line and still admit no useful global optimality theory, because integer points off a chosen line are invisible to it. M-convex functions, introduced by Murota, resolve this by replacing the secant condition with an …

38 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis VI: Quasi M-Convex Functions and the Quasi-Proximity TheoremTextbook

Convexity is normally defined additively — a function's value at a mixture is bounded by the mixture of its values — but many of the properties that make convexity useful in optimization (a local minimum is global, level sets are well-behaved) survive under a much weaker, purely ordinal notion: quasi-convexity, which compares function values rather than…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis V: The M-Optimality Criterion and the Proximity TheoremTextbook

Scaling algorithms are one of the standard techniques for solving discrete optimization problems efficiently: instead of searching a huge integer domain directly, an algorithm first solves a coarsened version of the problem — checking optimality only against neighbors reached by a large step size α\alphaα — and then refines the resulting approximate solution…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XIX: Discrete Separation for M-Convex SetsTextbook

Submodular set functions are the combinatorial stand-in for convexity: a function ρ:2V→R\rho : 2^V \to \mathbb Rρ:2V→R on the subsets of a finite ground set VVV is submodular if ρ(X)+ρ(Y)≥ρ(X∪Y)+ρ(X∩Y)\rho(X) + \rho(Y) \ge \rho(X \cup Y) + \rho(X \cap Y)ρ(X)+ρ(Y)≥ρ(X∪Y)+ρ(X∩Y), and this single diminishing-returns inequality drives an enormous range of combinatorial optimization — matroid rank functions, graph cut…

29 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XVIII: Integral Convexity of Minimizer SetsTextbook

A classical convex function's global minimality is equivalent to its local minimality — the single fact that makes convex optimization tractable, since checking a small neighborhood suffices to certify a global guarantee. The discrete analogue is not automatic: a function on the integer lattice can fail to have any well-behaved "local" notion at all, and…

28 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XVII: Fenchel Duality and Linear-Programming IntegralityTextbook

Duality is the organizing principle of convex optimization: a minimization problem's optimal value equals a maximization problem's optimal value, and this coincidence, rather than being a lucky accident, follows from a separating-hyperplane argument that applies whenever the two problems' feasible regions are shaped compatibly enough. Werner Fenchel…

37 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationOperations Research+1·Captain: mikedeng1

Lifts of Convex Sets and Cone Factorizations II: Antichain and Face-Count Lower Bounds on the Nonnegative Rank of a PolytopeResearch Paper

Many polytopes that arise in combinatorial optimization, such as the matching, cut, stable set and travelling salesman polytopes, have exponentially many facets, yet some of them can be written as the linear projection of a polyhedron with far fewer facets. The smallest number of facets of such a lift decides whether the polytope admits a compact…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

On Polyhedral Approximations of the Second-Order Cone II: A Lower Bound on the Size of Polyhedral ApproximationsResearch Paper

A conic quadratic program minimizes a linear objective subject to constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ\|A_\ell x-b_\ell\|_2\le c_\ell^Tx-d_\ell∥Aℓ​x−bℓ​∥2​≤cℓT​x−dℓ​. Interior-point methods solve such programs in polynomial time, but around 2000 the available solvers handled far smaller instances than linear programming codes did. Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 2001) asked…

10 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Convex Polytopes V: Recognition from projections (GRU-M05-PROJECTION-RECOGNITION)Textbook

A convex set can be studied through its images in spaces of smaller dimension. Each image records part of the geometry, while losing the information along the directions that are collapsed. A finite convex hull always has finite convex hulls as its affine images. The converse asks whether sufficiently rich projection data can force the original set to have…

5 thms3 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes XVIII: Complete characterization of simplicial face vectorsTextbook

A convex polytope has finitely many faces in each dimension, and their numbers form its f-vector. Determining which integer vectors occur is a basic realization problem in discrete geometry: necessary identities such as Euler's relation do not by themselves decide whether a proposed vector comes from a polytope. For simplicial polytopes, whose facets are…

56 thms3 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes X: Recognition from projectionsTextbook

A convex set can be studied through its images in lower-dimensional spaces. Each image retains part of the geometry while discarding information along the directions that are collapsed. Finite convex hulls behave well under affine maps: the image of a convex hull of finitely many points is again the convex hull of finitely many points. The converse is…

2 thms3 active usersReviewed
🏆Completed
Captain: mikedeng1

Convex Polytopes V: Face-lattice recovery from ray queriesTextbook

A polytope can be given by a list of vertices, a list of inequalities, or much less explicit access. The last case arises when geometric information is available through queries to a physical or computational object but a full description is unavailable. Grünbaum's account of a result by Gritzmann, Klee, and Westwater asks how much of a polytope can be…

50 thms3 active usersReviewed
🏆Completed
CombinatoricsComputational Geometry·Captain: mikedeng1

Strong Lower Bounds for Weak Epsilon-NetsResearch Paper

A collection of regions often has to be met by a small set of representative points. In discrete geometry this is a piercing problem: every region must contain at least one chosen point. When the regions are convex and each contains a prescribed fraction of a finite input set, the minimum required number of representatives is the weak epsilon-net problem.…

11 thms2 active usersReviewed
🏆Completed
Computational GeometryMachine Learning·Captain: mikedeng1

Geometric Deep Learning VI: Cotangent Weights Are Intrinsic, cot ∠uqv = (ℓ²_uq + ℓ²_vq − ℓ²_uv)/(4a_uvq) with Heron's Area a_uvqTextbook

Surfaces of three-dimensional objects are stored in computer graphics, vision and geometry processing as triangular meshes: finitely many points glued together by triangles. Geometric deep learning on such data needs a discretisation of the Laplace–Beltrami operator, because spectral filters, diffusion and many graph neural network layers on meshes are…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Geometrical Bounds for Variance and Recentered Moments: Among Measures with Support Diameter at Most d, Equal Mass on the Vertices of a Regular n-Simplex Maximizes Every Recentered MomentResearch Paper

A probability distribution can spread its mass while remaining inside a set of limited diameter. A bound on the diameter alone does not specify its center, shape, or number of support points. Lim and McCann ask how large a recentered moment can become under this sparse geometric information. Their answer identifies a regular simplex as the extremal…

7 thms2 active usersReviewed
🏆Completed
Captain: iris

Colorful Helly and colorful fractional Helly theoremsResearch Paper

Helly's theorem says that a finite family of convex sets in Rd\mathbb R^dRd has a common point whenever every d+1d+1d+1 of its members do. Two of its best-known strengthenings weaken the hypothesis in different directions. The colorful Helly theorem, due to Lovász and first published by Bárány (1982), distributes the sets into d+1d+1d+1 color classes and only asks that…

2 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Many Non-Equivalent Realizations of the Associahedron 3: Two Santos Associahedra Are Normally Isomorphic iff Their Seed Triangulations Agree up to Rotation and ReflectionResearch Paper

An associahedron is a polytope whose faces encode ways to dissect a convex polygon without crossing diagonals. Its vertices represent triangulations. Associahedra occur in geometric combinatorics because the same combinatorial object admits many geometric realizations. Ceballos, Santos and Ziegler ask when two such realizations have the same normal fan up…

9 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Many Non-Equivalent Realizations of the Associahedron 1: The Chapoton–Fomin–Zelevinsky Associahedron Is the Only One Normally Isomorphic to Both a Hohlweg–Lange and a Santos AssociahedronResearch Paper

An associahedron is a polytope whose vertices represent triangulations of a convex polygon and whose edges represent flips between triangulations. The same combinatorial polytope can be realized in different vector spaces with different facet directions. This matters when a construction uses the geometry of the realization, rather than only its face…

12 thms2 active usersReviewed
🏆Completed
AlgebraCombinatoricsLinear algebra·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 3: A Maximum h-Scattered Subspace of Dimension rn/(h + 1) Meets Every Hyperplane in Dimension Between rn/(h + 1) − n and rn/(h + 1) − n + hResearch Paper

Scattered subspaces are a central object of finite geometry. An Fq\mathbb F_qFq​-subspace UUU of an rrr-dimensional vector space over Fqn\mathbb F_{q^n}Fqn​ defines an Fq\mathbb F_qFq​-linear set of the projective space PG(r−1,qn)\mathrm{PG}(r-1,q^n)PG(r−1,qn), and when UUU is scattered this linear set has the largest possible number of points for its rank. Maximum scattered subspaces give rise to…

18 thms2 active usersReviewed
PreviousPage 3 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