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

Online Stochastic Matching: Beating 1-1/e 2: The Suggested Matching Algorithm Achieves 1 − 1/e with High Probability, and This Is Tight Even in ExpectationResearch Paper

Online bipartite matching models decisions that must be made as requests arrive: an advertiser can be assigned to a compatible request once, and an assignment cannot be revised when later requests reveal a better alternative. Display advertising is the motivating example in Feldman, Mehta, Mirrokni, and Muthukrishnan's 2009 preprint: an ad server knows…

12 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Primal-Dual Algorithms for Covering and Packing 3: A Deterministic O(log d log(n/OPT))-Competitive Algorithm for Online Unweighted Set CoverResearch Paper

Online set cover is the basic covering problem in which the requests arrive over time. A ground set of elements and a family of sets are known in advance, but which elements must be covered is revealed one element at a time, and each arriving element has to be covered at once by a set chosen irrevocably. The problem models resource placement under unknown…

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

On the Approximability of Single-Machine Scheduling with Precedence Constraints 2: Every Convex Bipartite Order Has a Realizer of Size 3Research Paper

The single-machine scheduling problem 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_j C_j1∣prec∣∑wj​Cj​ asks for an order in which to process nnn jobs, each with a processing time and a weight, on one machine, respecting a partial order of precedence constraints, so that the weighted sum of completion times is as small as possible. It is NP-hard, and the best known approximation ratio for…

7 thms3 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 3: The Incomparable-Pairs Graphs of Canonical Interval Orders Have Unbounded Chromatic NumberResearch Paper

Single-machine scheduling with precedence constraints asks for an order in which one machine processes jobs while respecting prescribed comparisons between them. For the objective of minimizing total weighted completion time, the structure of the precedence order can influence the quality of approximation algorithms. Ambühl, Mastrolilli, Mutsanas, and…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimizationProbability·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XVII: Goemans–Williamson Rounding of the MAXCUT SDP Relaxation Has Expected Value at Least 0.878 Times the Maximum CutTextbook

MAXCUT asks for a partition of the vertices of a weighted graph into two sets that maximizes the total weight of the edges between them. It is one of Karp's original NP-hard problems, so no polynomial-time exact algorithm is expected, and the natural question is how close a polynomial-time algorithm can come to the optimum. Sampling a uniformly random…

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

On the Approximability of Single-Machine Scheduling with Precedence Constraints 1: A k-Fold Realizer of Size t Yields a Vertex Cover of Expected Weight at Most (2 − 2/(t/k)) Times OptimalResearch Paper

Single-machine scheduling with precedence constraints, written 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_jC_j1∣prec∣∑wj​Cj​ in the notation of Graham et al., asks for an order of nnn weighted jobs on one machine that respects a given partial order and minimizes the weighted sum of completion times. The problem is strongly NP-hard (Lawler 1978; Lenstra and Rinnooy Kan 1978), and closing its…

10 thms3 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 4: Orthogonal Subspaces Have Dual MatroidsResearch Paper

Hassler Whitney introduced matroids in On the Abstract Properties of Linear Dependence (Amer. J. Math. 57, 1935, doi:10.2307/2371182) to capture what linear dependence among the columns of a matrix and the circuit structure of a graph have in common. One of the central constructions of the paper is duality. For graphs, duality exists only for planar graphs…

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

Assortment Optimization under Variants of the Nested Logit Model 4: With Dissimilarity Parameters at Most One, the Knapsack-Relaxation and Singleton LP Optimum Scaled by 2 Is Feasible for the Full LPResearch Paper

Assortment optimization asks which set of products a firm should offer when customers choose among the offered products according to a discrete choice model; it underlies shelf-space planning in retail and fare-class control in airline revenue management (Talluri and van Ryzin, 2004). Under the nested logit model products are grouped into nests, and a…

20 thms3 active users
🏆Completed
Number Theory·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 1: For Distinct Primes q₁, q₂, Every Large n Has an LPS Vertex Count Q(q₁, q₂, s, t) Between n and n + o(n)Research Paper

An (n,d,λ)(n,d,\lambda)(n,d,λ)-graph is a ddd-regular graph on nnn vertices in which every eigenvalue of the adjacency matrix other than the top eigenvalue ddd has absolute value at most λ\lambdaλ. Graphs of this kind with λ\lambdaλ small compared with ddd are expanders. They are used in derandomization, error-correcting codes, sorting networks and many other constructions in…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 2: Randomized Double Greedy Achieves 1/2 of the Optimum in ExpectationResearch Paper

Many selection problems assign a value to each subset of a finite collection: the coverage supplied by chosen facilities, the influence reached by chosen seeds, or the value of a coalition. A submodular set function has diminishing returns in the precise sense that the combined value of two sets, counting their overlap once, does not exceed the sum of their…

11 thms3 active usersReviewed
🏆Completed
Graph TheoryOptimization·Captain: mikedeng1

Two Theorems in Graph Theory: A Matching Is Maximum If and Only If No Alternating Chain Joins Two Neutral PointsResearch Paper

A matching of a graph is a set of edges no two of which share a vertex. A matching with as many edges as possible is a basic object of combinatorial optimization. Assignment problems, pairing and scheduling problems, and the Chinese postman problem reduce to it, and it is the standard example of a problem with a polynomial-time algorithm that is not an…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchProbability+1·Captain: mikedeng1

Secretary Problems: Weights and Discounts 5: A 3e-Competitive Algorithm for the Graphic Matroid Secretary ProblemResearch Paper

In the secretary problem, nnn items with nonnegative values arrive one at a time in a uniformly random order, and an online algorithm must decide on each arrival, irrevocably, whether to keep it. The classical version keeps one item; the rule that observes a 1/e1/e1/e fraction of the arrivals and then takes the first item better than everything seen picks the best…

10 thms3 active usersReviewed
🏆Completed
Complexity TheoryDiscrete GeometryLinear Optimization+1·Captain: mikedeng1

Exponential Lower Bounds for Polytopes in Combinatorial Optimization: The TSP Polytope Has Extension Complexity 2^Ω(√n)Research Paper

Combinatorial optimization problems are routinely solved by writing the convex hull of their feasible solutions as the feasible region of a linear program. When that convex hull has exponentially many facets, a classical trick is to add auxiliary variables: a polytope with many facets may be the linear projection of a higher-dimensional polyhedron with few.…

21 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization 3: Fractional Double Greedy on the Multilinear Extension Achieves 1/2 of the OptimumResearch Paper

Unconstrained submodular maximization (USM) asks for a subset SSS of a finite ground set N\mathcal NN maximizing a nonnegative submodular function fff. It contains Max-Cut, Max-DiCut and maximum facility location as special cases, and it is the basic subproblem of many constrained submodular maximization algorithms. Because fff is given only through a value oracle,…

11 thms3 active usersReviewed
🏆Completed
Computational GeometryDiscrete GeometryOperations Research·Captain: mikedeng1

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed: The Lattice-Point Count of an Integral Simplex Is a Short Signed Sum over Primitive ConesResearch Paper

How many integral points does a polytope contain? The question arises in integer programming, where it measures the size of a feasible set, in combinatorics, where many enumeration problems are lattice-point counts in a polytope (contingency tables, magic squares, flows), in the representation theory of Lie groups, and in the analysis of loop nests in…

16 thms3 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design 1: Pseudo-Dimension Bound from a Piecewise-Decomposable Dual ClassResearch Paper

Many algorithms in operations research and computer science have tunable parameters: sequence-alignment weights, clustering linkage interpolations, branch-and-bound branching rules, auction reserve prices. In data-driven algorithm design the parameters are chosen by optimizing average performance over a training set of problem instances drawn from an…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

A Polylogarithmic-Competitive Algorithm for the k-Server Problem: Randomized k-Server Is O(log² k · log³ n · log log n)-Competitive on Every n-Point MetricResearch Paper

The k-server problem (Manasse, McGeoch and Sleator, 1990) is the central problem of online computation: kkk servers sit on points of a metric space, requests arrive one at a time at points of the space, and each request must be served by moving a server to it, at a cost equal to the distance travelled. An online algorithm decides without knowing future…

16 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time: Delayed SWPT Has Competitive Ratio 2Research Paper

A single machine must process nnn jobs that arrive over time. Job jjj is released at time rjr_jrj​, needs pjp_jpj​ units of uninterrupted processing, and has weight wj>0w_j > 0wj​>0; the goal is to minimize the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​. Offline, with all release dates equal to zero, Smith's rule (sequence by nondecreasing pj/wjp_j/w_jpj​/wj​) is optimal (Smith 1956);…

11 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources II: A Time-Feasible Strict Order Is Feasible iff It Breaks Up Every Minimal Forbidden SetTextbook

Resource-constrained project scheduling asks for start times of the activities of a project so that prescribed time lags between activities are respected and, at every moment, the activities in progress do not require more of any renewable resource (staff, machines, reactors) than is available. When the time lags include maximum time lags (deadlines…

9 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming I: Integral Bipartite Matchings, Total Unimodularity and König's TheoremTextbook

Many combinatorial optimization problems are integer programs: linear objectives and linear constraints, with the extra requirement that the variables be integers. Dropping that requirement gives the LP relaxation, which is solvable efficiently but in general only bounds the integer optimum. For a small but important class of problems the relaxation loses…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

An Introduction to the Theory of Mechanism Design IX: Monotone Direct Mechanisms Are Dictatorial (Gibbard–Satterthwaite)Textbook

Voting rules, committee procedures and any other method that turns individual rankings into one collective choice face the same question: can the rule be designed so that no participant ever gains by misreporting their ranking? The Gibbard–Satterthwaite theorem (Gibbard, 1973; Satterthwaite, 1975) answers no. When at least three alternatives can be chosen…

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

Theory of Games and Economic Behavior II: Games with Perfect Information Are Strictly DeterminedTextbook

Chess, checkers, Go and Backgammon share a feature that card games such as Poker lack: whenever a player moves, the player knows everything that has happened so far. von Neumann and Morgenstern call this perfect information and devote §15 of Theory of Games and Economic Behavior (1944; 3rd ed. 1953) to it. Their result is that such a game, viewed as a…

14 thms3 active usersReviewed
Graph TheoryLinear algebra·Captain: mikedeng1

On a Conjecture of Spectral Extremal Problems: If the Extremal Graphs for F Are Turán Graphs Plus a Fixed Number of Edges, Every F-Free Graph of Maximum Spectral Radius Is ExtremalResearch Paper

Extremal graph theory asks how many edges a graph on nnn vertices can have without containing a fixed graph FFF. The answer, the Turán number ex(n,F)\mathrm{ex}(n,F)ex(n,F), and the graphs attaining it, the set Ex(n,F)\mathrm{Ex}(n,F)Ex(n,F) of extremal graphs, are known precisely only for special FFF; the Erdős–Stone–Simonovits theorem gives …

24 thms3 active users
🏆Completed
Discrete GeometryOperations Research·Captain: mikedeng1

Extremal Problems in Discrete Geometry: The Szemerédi–Trotter Incidence BoundResearch Paper

How many times can nnn points and ttt lines in the plane meet? The question is the prototype of incidence geometry, and the answer controls a long list of problems in discrete and computational geometry: the number of lines rich in points, the number of distinct distances or unit distances among nnn points, the complexity of arrangements, and sum–product…

8 thms3 active usersReviewed
🏆Completed
Discrete GeometryOperations 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
PreviousPage 22 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