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
Number Theory·Captain: marwahaha

Quasipolynomial Bounds for Arithmetic ProgressionsOpen Problem

A divergent reciprocal sum is a sparse largeness condition on integers. The mission asks whether it still forces additive structure of every finite length. The source manuscript presents the surrounding research claim.

34 thms4 active usersReviewed
🏆Completed
Group TheoryRepresentation Theory·Captain: wurtle

A Cyclic Polytabloid Proof of Saxl's ConjectureResearch Paper

The irreducible complex representations of the symmetric group SnS_nSn​ are the Specht modules SλS^\lambdaSλ, indexed by partitions λ⊢n\lambda\vdash nλ⊢n. How a tensor product Sα⊗SβS^\alpha\otimes S^\betaSα⊗Sβ (with diagonal action) decomposes is recorded by the Kronecker coefficients

45 thms4 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: wurtle

The Euclidean Steinitz–Bergström theoremResearch Paper

Given vectors v1,…,vNv_1,\dots,v_Nv1​,…,vN​ in the Euclidean unit ball of Rd\mathbb R^dRd that sum to zero, can they always be reordered so that every partial sum stays in a ball whose radius depends only on ddd? Steinitz's lemma, from his work on rearrangements of conditionally convergent vector series, says yes: in any norm, radius ddd suffices (Grinberg–Sevast'yanov 1980). For…

9 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling IV: A ρ-Approximate Max-m-Cut Gives a (ρ + m(1 − ρ))-Approximate Schedule for Pm | | Σ wⱼCⱼResearch Paper

Scheduling jobs on identical parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​, the problem P ∣ ∣∑wjCjP\,|\,|\sum w_jC_jP∣∣∑wj​Cj​, is one of the basic NP-hard problems of machine scheduling. On a single machine it is solved by Smith's ratio rule (Smith 1956); with several machines the only hard decision is which jobs share a machine. Section 6 of…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Concentration of Measure and Isoperimetric Inequalities in Product Spaces XI: The Random Assignment Problem — Fluctuations of the Optimal Cost of Order (log N)²/(√N log log N)Textbook

The assignment problem asks for a one-to-one matching of NNN agents to NNN tasks that minimizes the total cost. It is one of the basic problems of combinatorial optimization and is solved in polynomial time by the Hungarian method. Its random version, in which the N2N^2N2 costs are independent random variables, is a standard model for the typical behavior of…

7 thms4 active usersReviewed
🏆Completed
Number TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

A New Class of Random Number Generators 2: For Prime m = bʳ − bˢ + 1, Every Nontrivial Subtract-with-Borrow Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper

A pseudorandom number generator replaces repeated random sampling with a deterministic update of a small state. Its useful lifetime depends on the length and structure of the resulting orbit. In Marsaglia and Zaman’s 1991 paper, the subtract-with-borrow generators use only digit subtraction and a one-bit borrow while attaining cycles that can be almost as…

17 thms4 active usersReviewed
🏆Completed
AnalysisFunctional Analysis·Captain: mikedeng1

Quick Approximation to Matrices and Applications II: Every Square-Integrable f on [0,1]² Is a Sum of at Most 1/ε² Cut Functions plus an Error of Cut Norm at Most ε‖f‖₂Research Paper

A large matrix, or a large graph, can be approximated in a weak but useful sense by a short sum of very simple pieces. Frieze and Kannan (Combinatorica 19 (1999) 175–220) proved that every real matrix is, up to an error small in the cut norm, a sum of at most 1/ϵ21/\epsilon^21/ϵ2 cut matrices (constant on a combinatorial rectangle, zero elsewhere). This "weak…

5 thms4 active usersReviewed
🏆Completed
Linear algebraTheoretical Computer Science·Captain: mikedeng1

Quick Approximation to Matrices and Applications I: Every Real Matrix Is a Sum of at Most 1/ε² Cut Matrices plus an Error W with |W(S,T)| ≤ ε√(|S||T|)‖A‖_FResearch Paper

Many dense combinatorial optimization problems (Max-Cut, graph bisection, quadratic assignment on dense instances) have objective functions that are sums of matrix entries over rectangles S×TS\times TS×T. If a matrix can be replaced by a simple surrogate that agrees with it on every rectangle up to a small error, such problems can be solved approximately on the…

5 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

An Introduction to Timetabling 1: Every Class–Teacher Requirement Matrix Has a Timetable over Any p Days with Every Daily Load and Pair Count Between ⌊r/p⌋ and ⌈r/p⌉Research Paper

School and university timetabling is one of the oldest applications of combinatorial optimization. In his invited review An introduction to timetabling (European Journal of Operational Research, 1985), D. de Werra opens with the class–teacher model: classes meet teachers for a prescribed number of one-period lectures, and the lectures must be placed into…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

Strategy-Proofness and Arrow's Conditions 1: A Strict Voting Procedure with at Least Three Possible Outcomes Is Strategy-Proof Iff It Is DictatorialResearch Paper

A committee that chooses one alternative by voting would like a voting procedure under which no member can gain by misreporting their preferences. Such a procedure is called strategy-proof. Gibbard (Econometrica 41, 1973) and Satterthwaite (J. Econ. Theory 10, 1975) proved independently that, once at least three outcomes are possible, the only…

12 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Edge-Disjoint Spanning Trees of Finite Graphs: A Finite Multigraph Has k Edge-Disjoint Spanning Trees iff Every Partition P of Its Vertices Is Crossed by at Least k(|P| − 1) EdgesResearch Paper

A connected network survives the failure of any single link exactly when it has no bridge, but a stronger and more useful property is to carry several edge-disjoint spanning trees: each tree can broadcast to every node on its own, so kkk such trees give kkk independent routing or broadcast structures, and the network stays connected after any k−1k-1k−1 link failures.…

15 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchTheoretical Computer Science·Captain: mikedeng1

The Weighted Majority Algorithm 7: On a Class Shattered by Its Domain, Every Deterministic Learner's Mistake Bounds Satisfy Σ 2^(−M_i) < 2Research Paper

An online learner predicts a binary label for each instance before seeing that instance's correct label. Its guarantee is usually measured by its worst possible number of mistakes against a target function. Such guarantees can differ greatly across target functions: an algorithm might learn one target quickly while taking much longer on another. Littlestone…

5 thms4 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 1: Every Multicommodity Flow Network with k Source-Sink Pairs Has a Cut S with Cap(S)/Dem(S) ≤ O(log k) · maxflowResearch Paper

Routing several commodities through one capacitated network at the same time is a basic problem of network optimization, with applications to communication networks, VLSI layout and divide-and-conquer graph algorithms. Its optimum is the value of a linear program, but the natural certificates of an upper bound are combinatorial: every cut of the network…

9 thms4 active usersReviewed
🏆Completed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

On the Generalized “Birth-and-Death” Process 2: For Constant Rates λ₀ ≤ μ₀ the Cumulative Population M_∞ Has Law Q_M = ((λ₀+μ₀)/2λ₀)(2M)! x^M/(2^{2M}(M!)²(2M−1))Research Paper

A birth-and-death process describes a population in which each individual independently gives birth and dies at given rates. Kendall's 1948 paper (doi:10.1214/aoms/1177730285) solved the process with arbitrary time-dependent rates and, in its §4, introduced a second random variable alongside the population size: the cumulative population MtM_tMt​, the number of…

5 thms4 active usersReviewed
🏆Completed
Discrete GeometryGroup Theory·Captain: mikedeng1

Some Polyhedra Related to Combinatorial Problems IV: In a Group All of Whose Elements Have Order 2, or All Order 3, the Irreducible Solutions of the Group Equation Are Exactly the VerticesResearch Paper

Every pure integer program min⁡{c⋅x:Ax=b, x≥0 integer}\min\{c\cdot x : Ax = b,\ x \ge 0 \text{ integer}\}min{c⋅x:Ax=b, x≥0 integer} can be relaxed, by dropping the nonnegativity of the basic variables of an optimal linear-programming basis, to a problem over a finite Abelian group: find nonnegative integers t(g)t(g)t(g), one for each nonzero group element, with ∑t(g)⋅g=g0\sum t(g)\cdot g = g_0∑t(g)⋅g=g0​. R. E. Gomory's 1969 paper Some…

8 thms4 active usersReviewed
🏆Completed
Computational GeometryDiscrete GeometryGraph Theory·Captain: mikedeng1

A Combinatorial Theorem in Plane Geometry: Every n-Triangulation Can Be Partitioned into at Most ⌊n/3⌋ FansResearch Paper

In a conversation reported by Chvátal, Victor Klee asked for the smallest number f(n)f(n)f(n) such that every region bounded by a simple closed nnn-gon is dominated by f(n)f(n)f(n) points: every point of the region sees one of them along a segment inside the region. In the picturesque language that gave the problem its name, f(n)f(n)f(n) is the number of guards needed to watch any ar…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

An Additive Algorithm for Solving Linear Programs with Zero-One Variables: In Finitely Many Iterations the Additive Algorithm Yields an Optimal Solution or Proves InfeasibilityResearch Paper

Binary decisions arise when a variable records whether a project is selected, a facility is opened, or an action is taken. Linear constraints then describe the resources or conditions those choices must satisfy. Egon Balas's 1965 paper gives a direct algorithm for a finite linear program with zero-one variables: it begins with all variables at zero, adds…

10 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman IV: Every Connected, Even, Symmetric Mixed Graph Has an Euler TourResearch Paper

A postman, a snowplough or a street sweeper must traverse every street of a district and return to the depot. When some streets are one-way, the street network is a mixed graph: some edges are directed and must be traversed in a prescribed direction, the others are undirected and may be traversed either way. The first question about such a route is whether…

7 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Paths, Trees, and Flowers I: Matching-Duality Theorem — the Maximum Cardinality of a Matching Equals the Minimum Capacity-Sum of an Odd-Set CoverResearch Paper

A matching in a graph is a set of edges no two of which share a vertex. Finding a matching of maximum cardinality is one of the basic problems of combinatorial optimization: it models pairing tasks (workers to shifts, kidney donors to recipients, players to rounds), it is a subroutine of algorithms for the travelling salesman and Chinese postman problems,…

16 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows: With No Negative Marginal Cost Column, the Set Covering LP Is Optimal and Bounds the VRPTW Optimum from BelowResearch Paper

The vehicle routing problem with time windows (VRPTW) asks for minimum-cost routes from a central depot that serve every customer exactly once, respecting vehicle capacity and a time interval in which each customer's service must begin. It models school bus routing, parcel and retail distribution, and dial-a-ride services. Desrochers, Desrosiers and Solomon…

13 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Scheduling of Vehicles from a Central Depot to a Number of Delivery Points: The Savings Procedure Always Ends in a Feasible Truck Allocation Whose Mileage Is the Initial Less the Linked SavingsResearch Paper

Delivering goods from one depot to many customers with a fleet of trucks is the vehicle routing problem. Dantzig and Ramser formulated it in 1959 as the "truck dispatching problem" (Management Sci. 6 (1959), doi:10.1287/mnsc.6.1.80). Five years later Clarke and Wright proposed the savings procedure (Oper. Res. 12 (1964), 568–581, doi:10.1287/opre.12.4.568):…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Assortment Optimization under Variants of the Nested Logit Model 6: For δ > 1, the Powers-of-δ LP Optimum Scaled by (δ^(2γ̄+1), δ^(γ̄+1)) Is Feasible for the Full LPResearch Paper

Assortment optimization asks which products a retailer should offer when customers choose among the offered products according to a probabilistic choice model, so as to maximize expected revenue. Under the nested logit model the products are grouped into nests: a customer first picks a nest, then a product inside it. The model is the standard relaxation of…

21 thms4 active users
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

An Optimal Algorithm for On-line Bipartite Matching 1: RANKING Finds a Matching of Expected Size at Least n(1 − 1/e) − o(n) on Every Graph with a Perfect MatchingResearch Paper

Online matching describes allocation when requests must be answered as they arrive. A matching decision uses only the edges revealed so far and cannot be revised when later requests appear. In the bipartite setting studied by Karp, U. Vazirani, and V. Vazirani, the arriving vertices are girls and the possible partners are boys. Even when the full graph has…

10 thms4 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: mikedeng1

The Chromatic Number of Random Graphs: For Fixed 0 < p < 1, Almost Every G(n,p) Has n/s₀ ≤ χ(G) ≤ (n/s₀)(1 + 3 log log n / log n), where s₀ ≈ 2 log_d n and d = 1/(1−p)Research Paper

The chromatic number χ(G)\chi(G)χ(G) of a graph is the least number of colours in a proper vertex colouring. Determining it for a typical graph was, in the words of the paper, "one of the best known and most studied unsolved problems in the theory of random graphs". For the dense random graph Gn,pG_{n,p}Gn,p​ with fixed edge probability ppp, the clique number had been known…

15 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Two Moments Suffice for Poisson Approximations: The Chen-Stein Method 2: A Dependent Bernoulli Process Is Within 2(2b₁+2b₂+b₃) of a Poisson Process in Total VariationResearch Paper

Many counting problems in probability, combinatorics and statistics ask for the law of the number of occurrences of rare, weakly dependent events: long head runs in coin tossing, matching segments between two DNA sequences, isolated vertices or small subgraphs in a random graph, clusters of points in a scan statistic. Chen's 1975 adaptation of Stein's…

8 thms4 active usersReviewed
PreviousPage 5 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