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
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Hypergraph Matching with Delays: Randomized Batching with Depth-k Greedy Is 1/d-Competitive for Online-(k, d)-Max-MatchingResearch Paper

Ride-pooling platforms receive trip requests one at a time and must decide, within a short waiting window, which requests to group into a shared vehicle. A request that is not grouped before its window closes is served alone or lost. Online hypergraph matching with delays is the combinatorial core of this decision: requests are vertices that arrive over…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP: The Circlet Inequality Is Valid and Facet-Defining for the Symmetric TSP Polytope When 4 Divides nResearch Paper

The symmetric traveling salesman polytope STSP(n)STSP(n)STSP(n) is the convex hull of the incidence vectors of all Hamiltonian cycles of the complete graph KnK_nKn​. Minimizing a linear cost over it is the traveling salesman problem, and polyhedral methods for the TSP (cutting planes, branch and cut, LP relaxations and their integrality gaps) depend on linear inequalities…

19 thms3 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research+1·Captain: mikedeng1

Binary Extended Formulations and Sequential Convexification: Among All d-Hypercube Binarizations, the Logarithmic Binarization Has Minimum RankResearch Paper

Mixed-integer programs often contain general integer variables x∈{0,…,k}x \in \{0, \dots, k\}x∈{0,…,k}. A standard modelling device replaces such a variable by ddd binary variables y∈{0,1}dy \in \{0,1\}^dy∈{0,1}d linked to xxx through a polytope, a binarization. Examples are the unary encoding, the "full" encoding with one indicator per value, and the logarithmic encoding x=∑i2i−1yix = \sum_i 2^{i-1} y_ix=∑i​2i−1yi​.…

15 thms3 active usersReviewed
Operations ResearchOptimization·Captain: Shuze Chen

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties: Polynomial approximation for monotone submodular maximizationResearch Paper

Selecting a valuable subset subject to several simultaneous restrictions is a common combinatorial optimization problem. A facility may contribute less after nearby facilities have already been selected; a collection of observations may provide overlapping information. Such diminishing returns are captured by submodular objectives. Matroid constraints…

16 thms3 active usersReviewed
Quantum InformationRepresentation Theory·Captain: mikedeng1

Optimal Quantum Purity Amplification: Removing the Bottom Box of the Last Column of Each Schur-Sampled Young Diagram Gives the Optimal Choi Matrix for Purifying n Depolarized QuditsResearch Paper

Quantum devices rarely prepare the state they are asked for. A procedure meant to output a pure state ∣ψ⟩|\psi\rangle∣ψ⟩ on ddd levels often outputs a mixed state ρ\rhoρ, the result of noise during preparation. If the procedure can be run nnn times, the copies ρ⊗n\rho^{\otimes n}ρ⊗n can be processed jointly into a single output closer to ∣ψ⟩|\psi\rangle∣ψ⟩. This task is quantum…

15 thms3 active usersReviewed
AlgebraRepresentation Theory·Captain: mikedeng1

Representations of Temperley–Lieb Algebras: Closed Product Formula for the Gram Determinants of the Cell ModulesResearch Paper

The Temperley–Lieb algebra is a family of algebras built from generators that satisfy local relations. It appears in diagrammatic representation theory and provides a tractable setting in which to study cellular bases and Gram determinants. A Gram determinant tests whether the bilinear form on a module is degenerate after specializing its parameter. Thus an…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Network Inspection for Detecting Strategic Attacks: The Equilibrium Detection Rate and Inspection Strategies Do Not Depend on the Attacker's Number of ResourcesResearch Paper

Utility networks such as water pipelines, gas distribution systems and power grids are exposed to attacks on their physical components. An operator who cannot monitor every component must decide where to place a limited number of detectors, without knowing which components an adversary will target or how many of them. Dahan, Sela and Amin (arXiv:1705.00349,…

11 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.1308255793978239…2.1308255793978239\ldots2.1308255793978239…Open Problem

A Boolean function can react differently to changing one input coordinate and changing several coordinates together. Measuring this difference is a question about the local complexity of total Boolean functions. The Block Sensitivity vs. Sensitivity campaign records exponents that quantify how large this difference can become along families of functions…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Improved Approximations for a CVRP with Unsplittable Demands: The Cheaper of a Matching-Plus-Tank Solution and a Tank-Split TSP Tour Is an (α + 1.75)-ApproximationResearch Paper

Capacitated vehicle routing asks how to serve clients from a depot with vehicles that can carry only a limited load. In the unsplittable version, one vehicle must deliver each client's entire demand. This makes the choice of routes interact with bin packing: a short tour can fail because its total demand exceeds the vehicle's capacity. Approximation…

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

Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number: For Every ε in (0, 1/2] a (1 − ε)-EFX Allocation Leaves at Most 64(n/ε)^(4/5) Goods UnallocatedResearch Paper

Dividing indivisible goods fairly is a central problem of fair division, with applications from inheritance and course allocation to the division of computing resources. Since envy-free allocations of indivisible goods need not exist (one good, two agents), the field studies relaxations. The most prominent is envy-freeness up to any good (EFX): no agent…

18 thms3 active usersReviewed
🏆Completed
ProbabilityQuantum Information·Captain: mikedeng1

Tight Detection Efficiency Bounds of Bell Tests in No-Signaling Theories: Two-Party Bell Tests with M_A and M_B Inputs Need Detector Efficiency η*_NS ≤ (M_A + M_B − 2)/(M_A M_B − 1)Research Paper

A Bell test certifies that correlations between two separated parties cannot be produced by any classical mechanism, that is, by a local hidden variable (LHV) model (Bell 1964). The same tests are the basis of device-independent protocols, where an adversary is only constrained by the no-signaling condition: neither party can learn the other's input from…

10 thms3 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

Regular Matroids Have Polynomial Extension Complexity: The Independence Polytope of Every Regular Matroid on n Elements Has Extension Complexity O(n⁶)Research Paper

Many combinatorial optimization problems are linear programs over a polytope with exponentially many facets, and one way to solve them by a polynomial-size linear program is to write the polytope as the projection of a higher-dimensional polytope with few facets. The minimum number of facets needed is the extension complexity of the polytope. It is now…

20 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: Shuze Chen

A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions: The Algorithm of Figure 3 Returns a Minimizer of Every Real Submodular Function in O(n⁷ log n) StepsResearch Paper

Submodular function minimization asks for a subset XXX of a finite set VVV that minimizes a set function fff satisfying f(X)+f(Y)≥f(X∪Y)+f(X∩Y)f(X) + f(Y) \ge f(X \cup Y) + f(X \cap Y)f(X)+f(Y)≥f(X∪Y)+f(X∩Y). Cut functions, matroid rank functions and entropy are submodular, and minimizing them is a subroutine in dynamic flows, facility location and source coding. Grötschel, Lovász and Schrijver showed in…

15 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

The Traveling-Salesman Problem and Minimum Spanning Trees: The 1-Tree Gap Vanishes Exactly When the Subtour LP Has an Integral Optimal SolutionResearch Paper

The symmetric traveling-salesman problem asks for a cheapest cycle through all nnn vertices of a complete graph with real edge weights. Every exact method for it rests on lower bounds, and the most widely used one comes from Held and Karp's two papers of 1970–71 (Held & Karp 1970; Part II, 1971). Their bound is built from 1-trees, a slight variant of spanning…

12 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: Shuze Chen

Flows in Networks V: Common Systems of Restricted RepresentativesTextbook

Assignment questions ask whether every member of a family can be served by a different resource: committees that each need a distinct member as representative, or tasks that each need an admissible worker. The classical answer is Hall's theorem (Hall 1935): a family of sets has a system of distinct representatives exactly when every kkk of its sets together…

10 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Reach 2.13Open Problem

Improve the separation exponent between block sensitivity and sensitivity of total Boolean functions. This mission targets α≥2.13\alpha\ge2.13α≥2.13; higher is better.

6 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.13032.13032.1303Open Problem

Two natural ways to measure the local instability of a Boolean function can behave differently. One counts individual input bits whose flips change the answer. The other permits several bits to change together, provided the chosen groups are disjoint. Quantifying the largest possible gap is a question in the complexity of total Boolean functions, and the Blo…

8 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.13012.13012.1301Open Problem

Two natural ways to measure the local instability of a Boolean function can behave differently. One counts individual input bits whose flips change the answer. The other permits several bits to change together, provided the chosen groups are disjoint. Quantifying the largest possible gap is a question in the complexity of total Boolean functions, and the Blo…

7 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Periodic exponent 2.1192.1192.119Open Problem

A rule that assigns an output bit to every input string can respond differently to changing one bit and changing a group of bits. Sensitivity counts individual changes that affect an output. Block sensitivity permits disjoint groups of coordinates to change separately. Understanding the largest possible difference between these measures is a question about…

5 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Eight-layer exponent 2.0852.0852.085Open Problem

A rule that assigns an output bit to every input string can react very differently to changing one bit and changing several bits together. Quantifying that difference is a basic question about Boolean functions in theoretical computer science. Sensitivity measures how many individual bit changes can affect one output; block sensitivity allows disjoint…

5 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Extension of Additive Valuations to General Valuations on the Existence of EFX: A Complete EFX Allocation Exists When Every Agent Has One of Two General ValuationsResearch Paper

Dividing indivisible goods fairly among agents with different preferences is a central problem of fair division, with uses ranging from inheritance and divorce settlements to course allocation and fair-division services such as Spliddit (Goldman–Procaccia 2014). Envy-freeness cannot always be achieved with indivisible goods (one good, two agents), so…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Probability Distributions on Partially Ordered Sets and Network Interdiction Games: Under the Conservation Law, Element Marginals and Maximal-Chain Hitting Bounds Are Jointly AchievableResearch Paper

Network interdiction asks how an inspector should randomize over sets of links when a router can choose a path through a network. Link inspection probabilities and path interception probabilities describe different features of the same random choice. Specifying both sets of numbers separately does not guarantee that one distribution over inspection sets…

11 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: Robin Kothari

Block Sensitivity vs. Sensitivity: Reach 2.075Open Problem

Sensitivity and block sensitivity measure how a Boolean function responds to changes in its input. They are central examples of query complexity measures: an algorithm learns an unknown input by querying its individual coordinates, while these measures describe how many changes the function can detect at a single input. Understanding their relationship…

5 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Fair Allocation of Indivisible Goods: Improvement and Generalization: Every Instance with Additive Valuations Admits a 3/4-MMS AllocationResearch Paper

Dividing a set of indivisible goods among agents with different preferences is a basic problem of fair division, with applications to inheritance, course allocation and the division of shared assets. With indivisible goods, envy-freeness and proportionality cannot always be achieved: a single good and two agents already rule both out. Budish (The…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution: Without Samples, No Stopping Rule Guarantees More Than 1/e of the Expected MaximumResearch Paper

A prophet inequality compares the value obtained by an online decision maker with the largest value in a sequence that could be chosen by someone who sees the entire sequence. The online decision maker observes values one at a time and must decide whether to accept the current value before seeing future values. When the common distribution of the values is…

9 thms3 active usersReviewed
PreviousPage 17 of 50Next

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