Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Combinatorics

1,238 missions · 706 completed

The mathematics of finite and discrete structures — counting the arrangements of a set, deciding when a configuration meeting prescribed constraints can exist, and characterizing the patterns such structures are forced to contain. It encompasses enumerative and extremal combinatorics, graph theory, design theory, and additive combinatorics, with deep ties to algebra, probability, and computer science.

Missions

Open532Completed706All1238
🏆Completed
Graph TheoryNumber Theory·Captain: FormallyCorrect

Proofs from THE BOOKTextbook

This Textbook project develops a reusable Lean library around Martin Aigner and Günter M. Ziegler's Proofs from THE BOOK. It combines results imported from the existing proof_in_the_book repository with precise contribution targets from the sixth edition (2018). The aim is to preserve mathematical meaning, reuse existing proofs, and make the remaining work…

209 thms11 active users
🏆Completed
Complexity Theory·Captain: Shuze Chen

Hardness of Counting Orderings: Taking Gadget Amplification to the LimitResearch Paper

A linear extension of a finite partially ordered set (poset) PPP is an ordering of its elements in which every element comes after all of its predecessors. Counting them, #LE(P)\#\mathrm{LE}(P)#LE(P), is a basic problem of order theory with uses in sorting under partial information, scheduling, and Bayesian inference over orderings. Brightwell and Winkler proved in 1991…

34 thms10 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 1: Minimizing the Total Discrepancy from Preferred Times Is NP-CompleteResearch Paper

Scheduling with earliness and tardiness penalties asks for schedules in which a job finishing early is as undesirable as a job finishing late. The model fits production planned for just-in-time delivery, where finished goods held before their due date cost money, and sequences of experiments tied to fixed external events. It departs from classical…

37 thms10 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Edge Dominating Sets in Graphs: The Edge Dominating Set Problem Is NP-Complete for Bipartite Graphs of Maximum Degree 3Research Paper

A set FFF of edges of a graph dominates the graph if every other edge shares an endpoint with an edge of FFF. Every maximal matching is an edge dominating set, and conversely a minimum edge dominating set can be turned into a minimal maximal matching of the same size, so the edge dominating set problem is the problem of finding a minimum maximal matching.…

23 thms9 active usersReviewed
🏆Completed
Discrete GeometryLinear Optimization·Captain: mikedeng1

A Quasi-Polynomial Bound for the Diameter of Graphs of Polyhedra: Every Polyhedron Given by n Inequalities in ℝ^d, Bounded or Not, Has Graph Diameter at Most n^(log₂ d + 2)Research Paper

The simplex method solves a linear program by walking along the edges of the feasible polyhedron, from vertex to vertex. However cleverly a pivot rule chooses its steps, it cannot reach the optimum in fewer steps than the graph distance from the starting vertex. The largest possible graph diameter of a polyhedron therefore bounds from below the worst-case…

19 thms9 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: LG

4-to-1 Games with Perfect CompletenessResearch Paper

Many approximation problems resist the standard PCP toolkit: the best known NP-hardness factors for Max-Cut, Vertex-Cover and approximate graph colouring are far from the best known polynomial-time algorithms. To explain this gap, Khot (CCC 2002) proposed the Unique-Games Conjecture and the family of ddd-to-1 Games Conjectures. The ddd-to-1 conjectures assert pe…

21 thms9 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

On General Routing Problems: The Rural Postman Problem Is NP-Complete on Undirected and on Directed GraphsResearch Paper

Arc routing problems model street sweeping, snow ploughing, mail delivery and meter reading: a vehicle must traverse certain streets of a road network and return to its depot at least cost. Orloff (Networks 4, 1974) proposed the general routing problem (GRP), which asks for a minimum-weight closed tour in a graph that visits a set of required nodes and…

28 thms8 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity I: Unit-Time Chains on Two Identical Machines with One Unit Resource Are Strongly NP-hardResearch Paper

Machine scheduling asks how to assign jobs to machines over time so that a criterion such as the makespan Cmax⁡C_{\max}Cmax​, the time at which the last job completes, is as small as possible. In practice jobs also compete for scarce resources beyond the machines themselves: tools, operators, memory, power. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the…

46 thms8 active usersReviewed
🏆Completed
Complexity TheoryOperations Research·Captain: mikedeng1

Near-Logarithmic Inapproximability of Parameterized Set CoverResearch Paper

Set Cover asks for a smallest selection from a family of subsets whose union contains every element of a specified universe. It is a basic model for selecting resources that jointly satisfy coverage requirements. Its approximation behavior depends on both the number of available sets and the number of elements requiring coverage. When the universe is small,…

42 thms7 active usersReviewed
🏆Completed
Complexity TheoryInformation TheoryTheoretical Computer Science·Captain: mikedeng1

Finding Short Synchronizing Words for Prefix Codes: Unless P = NP, the Shortest Synchronizing Word of a Binary Huffman Decoder Cannot Be Approximated Within c log nResearch Paper

A prefix code is a set of binary words none of which is a prefix of another; Huffman codes are the standard example. Such a code is decoded by an automaton that walks down the code tree and returns to the root after each codeword. A transmission error can make the decoder lose track of codeword boundaries. A synchronizing word brings the decoder to one…

41 thms7 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryOperations Research+1·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity II: Unit-Time Jobs on Two Uniform Machines with Unit Resources Are Strongly NP-hardResearch Paper

Machine scheduling asks how to assign jobs to machines over time. In many applications a job also needs additional scarce resources while it runs: a tool, a skilled operator, a memory bank, a channel. Adding such resources can turn a problem with a polynomial algorithm into an NP-hard one. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the standard…

41 thms7 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Convexity and Steinitz's Exchange Property III: Fenchel-Type Min-Max Duality with Primal and Dual Integrality for M-Concave and M-Convex FunctionsResearch Paper

Several classical min-max theorems of combinatorial optimization say that a discrete maximization problem and a continuous minimization problem have the same optimal value, and that both have integral optimal solutions when the data are integral. Edmonds' polymatroid intersection theorem (1970), Fujishige's Fenchel-type duality for submodular functions…

21 thms7 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Convexity and Steinitz's Exchange Property II: The Local Supermodularity Theorem for the Concave ConjugateResearch Paper

Matroids and their integral generalizations, integral base polytopes, are the combinatorial structures on which the greedy algorithm is exact. Edmonds' theory relates them to submodular and supermodular set functions: a polytope is a base polytope exactly when its support function, restricted to 0/10/10/1 vectors, is supermodular and the greedy formula evaluates…

18 thms7 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Convexity and Steinitz's Exchange Property I: The Extension Theorem — M-Concavity Is Concave Extendability with Integral Base Polytope MaximizersResearch Paper

Linear optimization over the bases of a matroid, over the integer points of a polymatroid, or over the flows of a network is well understood: the greedy algorithm is exact, the feasible sets are the integer points of polytopes described by submodular functions, and min-max theorems of Edmonds and Frank hold with integrality. Nonlinear objectives on the same…

24 thms7 active usersReviewed
🏆Completed
Number Theory·Captain: LG

Erdős Problem 3: arithmetic progressions in sets with divergent reciprocal sumOpen Problem

Which sets of positive integers are forced to contain long arithmetic progressions? Van der Waerden (1927) showed that in any finite colouring of N\mathbb NN some colour class does; Erdős and Turán (1936) asked for a density version, which became Szemerédi's theorem. Erdős then proposed the strongest natural size condition: divergence of the reciprocal sum. Er…

54 thms7 active usersReviewed
🏆Completed
Number Theory·Captain: aarontcao

The Komlos-Sulyok-Szemeredi bound: every finite set of reals has a Sidon subset of size c sqrt nResearch Paper

Call a set of reals a Sidon set when all its pairwise sums are distinct: if a+b=c+da + b = c + da+b=c+d with all four in the set, then {a,b}={c,d}\{a,b\} = \{c,d\}{a,b}={c,d}.

17 thms7 active usersReviewed
🏆Completed
Graph TheoryNumber Theory·Captain: iris

Prime cordial labeling of Knödel graphResearch Paper

Graph labelings assign integers to the vertices of a graph subject to arithmetic conditions on the edges; Gallian's dynamic survey (Electron. J. Combin., DS6) lists several thousand papers on them. A prime labeling asks for distinct labels 1,…,∣V∣1,\dots,|V|1,…,∣V∣ with coprime labels on every edge. Its relaxation, the prime cordial labeling of Sundaram, Ponraj and…

88 thms6 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation: Optimal competitiveness of generalized perturbed greedyResearch Paper

An allocation decision does not always produce a reward. An advertisement may receive no click, or a recommended product may not be purchased. In online matching with stochastic rewards, a failed offer uses the customer's opportunity but leaves the resource available for a later customer. This distinction changes both the algorithm and the benchmark against…

24 thms6 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems 3: Capacity Scaling for the Hitchcock ProblemResearch Paper

The Hitchcock transportation problem asks how to ship a commodity from mmm supply points to nnn demand points at minimum total cost. It was posed by Hitchcock in 1941 and is one of the founding problems of linear programming and network optimization; it is solved routinely in logistics, and its structure (a bipartite network with supplies, demands and per-unit…

12 thms6 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Cores of Convex Games: The Core of a Convex Game Is Its Unique von Neumann-Morgenstern Stable SetResearch Paper

A cooperative game with transferable utility assigns to every coalition of players the total payoff the coalition can secure on its own. Two solution concepts for such games go back to the foundations of game theory: the core, the set of payoff divisions no coalition can improve upon, and the stable set (von Neumann–Morgenstern solution), a set of divisions…

20 thms6 active usersReviewed
🏆Completed
Number Theory·Captain: aarontcao

Long-Wagner Conjecture 5.1: cube-free subsets of Z/2^nZ have density at most 5/8Open Problem

Call A⊆Z/2nZA \subseteq \mathbb{Z}/2^n\mathbb{Z}A⊆Z/2nZ cube-free if no triple x,y,zx, y, zx,y,z has all seven of xxx, yyy, zzz, x+yx+yx+y, y+zy+zy+z, z+xz+xz+x, x+y+zx+y+zx+y+z inside AAA. The triple is unconstrained, so a degenerate one counts. Write f(n)f(n)f(n) for the largest size of a cube-free subset.

18 thms6 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: hao jia

Immune High-Girth Bipartite Graphs (Feghali-Lucke-Paulusma-Ries 2025)Research Paper

A matching cut is a vertex bipartition whose crossing edges form a matching. The property was introduced under the name decomposability and has links to graph algorithms, stable cutsets in line graphs, and several graph-labeling problems. An Open Problem Garden question asked whether sufficiently large girth forces a matching cut once average degree is…

20 thms6 active usersReviewed
🏆Completed
Graph Theory·Captain: hao jia

Formalizing an 8-Vertex Candidate Counterexample to the Geodesic-Cycle Assignment Problem (OPG-500)Open Problem

[VM-STATUS-20260908-R05-PROVED]

9 thms6 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mysticflounder

Erdős Problems 97 and 96: Convex Point Sets and Unit DistancesOpen Problem

Adam McKenna closed this mission on 13 September 2026 following Unit distances in convex polygons, by Liam Kruer, Jensen Kohlmeyer, and Liam Price. Their construction gives strictly convex point sets with Ω(n log log n) unit-distance pairs and arbitrarily large minimum unit-distance degree, answering both questions and the general fixed-k version of Problem…

81 thms6 active usersReviewed
🏆Completed
Number Theory·Captain: ShouqiaoWang

Erdős Problem 390: Exact Second-Order AsymptoticResearch Paper

Determine the exact second-order term in the least possible largest factor in a factorization of n!n!n! into distinct integers exceeding nnn, with the proposed rational constant 4029639598/259700381854029639598/259700381854029639598/25970038185.

97 thms6 active usersReviewed
PreviousPage 1 of 29Next

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