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

The Online Set Cover Problem 1: A Deterministic O(log m log n)-Competitive Algorithm for Unweighted Online Set CoverResearch Paper

Set cover asks for the fewest sets from a family S\mathcal SS of mmm subsets of a ground set XXX of nnn elements whose union contains XXX. It is NP-hard, and the best ratio achievable in polynomial time is Θ(log⁡n)\Theta(\log n)Θ(logn) (Feige 1998, doi:10.1145/285055.285059).

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

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

A set function f:2N→Rf : 2^{\mathcal N} \to \mathbb Rf:2N→R on a finite ground set N\mathcal NN is submodular if it has diminishing returns, equivalently if f(A)+f(B)≥f(A∪B)+f(A∩B)f(A) + f(B) \ge f(A \cup B) + f(A \cap B)f(A)+f(B)≥f(A∪B)+f(A∩B) for all A,B⊆NA, B \subseteq \mathcal NA,B⊆N. Cut functions of graphs and hypergraphs, coverage functions, entropy, and many facility-location and welfare objectives are submodular. Unco…

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

Project Scheduling with Time Windows and Scarce Resources V: A Schedule Is Inventory-Feasible iff It Resolves Every Minimal Surplus and Shortage SetTextbook

In make-to-order production, chemical process industries and other manufacturing settings modelled as projects, activities do not only occupy machines for a while: they also consume intermediate products at their start and deposit products into storage facilities at their completion. Storage is bounded above by a tank or warehouse capacity and below by a…

7 thms2 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming X: Pairwise Intersecting d-Intervals Have a Transversal of Size 2d²Textbook

A basic question of combinatorial geometry asks when a family of sets can be pierced (or stabbed) by few points. For intervals on the real line the answer is classical: if every two of finitely many closed intervals intersect, one point meets all of them, namely the rightmost left endpoint. This is the one-dimensional case of Helly's theorem. The situation…

8 thms2 active usersReviewed
🏆Completed
Information TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming VIII: The Delsarte Linear Programming Bound for Binary CodesTextbook

A binary error-correcting code is a set of nnn-bit words chosen so that the words stay distinguishable after a few bits have been corrupted in transmission. A code can correct any rrr errors exactly when every two of its words differ in at least 2r+12r+12r+1 positions. The more words the code has, the more information each transmitted block carries. So the central…

10 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Understanding and Using Linear Programming VII: LP Rounding Schedules Unrelated Machines Within Twice the Optimal MakespanTextbook

Scheduling indivisible jobs on parallel machines to finish all of them as early as possible is a basic problem in operations research and in the theory of algorithms. In the unrelated machines model each job may take a different time on each machine, with no relation between the rows of the time table, as when machines of different types (black-and-white,…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming: Foundations and Extensions III: Network Flows, the Integrality Theorem and König's TheoremTextbook

Minimum-cost network flow problems are the largest special class of linear programs met in practice: transportation, distribution, assignment, communication and electric networks, facility location and financial planning all reduce to moving material along the arcs of a directed network from supply nodes to demand nodes at least cost. Chapter 14 of R. J.…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VI: Splitting Sets and the Decomposition Partition of a GameTextbook

Chapter IX of von Neumann and Morgenstern's Theory of Games and Economic Behavior asks when a game played by many participants is really several separate games played side by side. The authors' motivation (41.1) is methodological: the general theory of the nnn-person game becomes unmanageable as nnn grows, and one way to gain insight into large games is to…

16 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Optimal Two- and Three-Stage Production Schedules with Setup Times Included 2: Johnson's Rule for Three MachinesResearch Paper

Johnson's 1954 paper in Naval Research Logistics Quarterly is the starting point of machine scheduling theory. Its first section solves the two-machine flow shop: nnn items must pass through machine 1 and then machine 2, and an explicit ordering rule minimizes the total elapsed time. Its second section treats three machines. There the problem "loses some of…

19 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Odd Minimum Cut-Sets and b-Matchings 2: A Capacitated b-Matching Blossom Inequality Is Violated iff G(x, d) Has an Odd Cut of Capacity Less Than OneResearch Paper

A b-matching with upper bounds in a graph G=(V,E)G=(V,E)G=(V,E) assigns a nonnegative integer xe≤dex_e\le d_exe​≤de​ to every edge so that the edges at each node iii carry at most bib_ibi​ in total. Maximizing a linear objective over such assignments is an integer program that contains ordinary matching (b≡1b\equiv 1b≡1, d≡1d\equiv 1d≡1) and appears in assignment, transportation and scheduling models…

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

Odd Minimum Cut-Sets and b-Matchings 1: A Minimum-Weight Odd-Splitting Edge of the Gomory–Hu Cut-Tree Defines an Odd Minimum Cut-SetResearch Paper

Edmonds showed that the convex hull of the matchings of a graph is described by the degree constraints together with the blossom inequalities, one for every odd set of nodes (Edmonds 1965). There are exponentially many of them, so any cutting-plane method for matching and b-matching problems must answer a separation question: given a fractional point, find…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

A New Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem: Safe Shrinking of Customer SetsResearch Paper

The capacitated vehicle routing problem (CVRP) asks for minimum-cost routes, starting and ending at a depot, that serve every customer exactly once without any vehicle carrying more than its capacity. It is one of the central problems of operations research and logistics, and exact algorithms for it have been built on branch-and-cut for three decades: a…

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

Optimal Two- and Three-Stage Production Schedules with Setup Times Included 1: Johnson's Rule Minimizes the Total Elapsed Time on Two MachinesResearch Paper

A two-machine flow shop is the simplest multi-stage production system: every job visits machine 1 and then machine 2, each machine works on one job at a time, and the goal is to finish all jobs as early as possible. S. M. Johnson's 1954 paper (Naval Research Logistics Quarterly 1(1):61–68, doi:10.1002/nav.3800010110) answered this question, posed by R.…

16 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XII: Steepest Descent for M-Convex Function MinimizationTextbook

Chapters 6 through 9 characterized minimality for M-convex functions structurally (the M-optimality criterion, Theorem 6.26: a point is a global minimizer iff no local swap improves it) without saying how to find one. Chapter 10 turns that structural fact into an algorithm: the local characterization is the termination test of the simplest possible…

17 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Applied Combinatorics VII: Minimum Spanning Trees and Dijkstra's AlgorithmTextbook

Two optimization problems on weighted networks sit at the base of operations research and algorithm design. The first asks for the cheapest way to connect every node of a network, such as a cable, pipeline or communication network. The answer is a minimum weight spanning tree. The second asks for the shortest route from a depot to every other node of a road…

8 thms2 active usersReviewed
🏆Completed
Captain: mikedeng1

Applied Combinatorics III: Inclusion–Exclusion and the Number of SurjectionsTextbook

Counting the objects that avoid every one of a list of conditions is one of the most frequent tasks in enumerative combinatorics: functions that miss no value, permutations that fix no point, integers that share no prime factor with a given number. The Principle of Inclusion-Exclusion converts such a count into an alternating sum of counts of objects that do…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem IV: Insertion Heuristics Can Return Poor k-Optimal ToursResearch Paper

Insertion heuristics build a traveling salesman tour one city at a time: start from a single city, and at each step choose a city not yet on the subtour and splice it into the subtour where it lengthens the subtour least. Local search heuristics start from a tour and repeatedly replace a few of its edges by others while this shortens the tour. Both families…

14 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems III: The Worst-Case Ratio of the Weighted Algorithm B2Research Paper

MAXIMUM SATISFIABILITY asks for a truth assignment satisfying as many clauses of a given set as possible. It was among the first NP-hard optimization problems for which an approximation algorithm came with a proven worst-case guarantee. In Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9, 1974, doi:10.1016/S0022-0000(74)80044-9),…

9 thms2 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis IV: Discrete Separation for L-Convex SetsTextbook

The classical separating hyperplane theorem says that any two disjoint convex sets in Rn\mathbb R^nRn can be separated by a hyperplane with an arbitrary real normal vector. When the sets in question are not arbitrary convex sets but the integer points of specially structured discrete sets, one can sometimes ask for much more: not merely that a separator exists,…

18 thms2 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis III: Edmonds's Intersection TheoremTextbook

Matroid intersection is one of the founding results of combinatorial optimization: given two matroids on a common ground set, the largest common independent set can be found in polynomial time, and its size equals the minimum of a natural upper bound ranging over all subsets — a min-max theorem in the spirit of König's theorem and Menger's theorem, but for…

20 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem III: Nearest and Cheapest Insertion Are Within a Factor of TwoResearch Paper

The traveling salesman problem (TSP) asks for a shortest closed route through a finite set of points. It is NP-hard, and in practice tours are built by fast constructive heuristics whose output is then improved or used as is. A central question in the analysis of algorithms, raised in this form by Rosenkrantz, Stearns and Lewis in 1977, is how far such a…

10 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

A Faster Algorithm Computing String Edit Distances 2: Discrete Edit Costs Are NecessaryResearch Paper

The edit distance between two strings is the least total cost of a sequence of single-character insertions, deletions and replacements that turns one string into the other. It underlies spelling correction, sequence alignment in computational biology, and file comparison. Wagner and Fischer (J. ACM 21, 1974) computed it for strings of length nnn in time O(n2)O(n^2)O(n2)…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions III: Guarantees of Deterministic Local SearchResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a function with diminishing returns: the cut of a graph or a directed graph, the value of a facility-location configuration, the entropy of a set of random variables, or a welfare function in combinatorial auctions. These functions are submodular but typically non-monotone:…

14 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

On Certain Polytopes Associated with Graphs III: The Stable Set Polytope after Substituting a Graph for a VertexResearch Paper

Many combinatorial optimization problems on graphs are linear programs over a polytope whose inequality description is unknown. The stable set polytope is the standard example: maximizing a linear function over it is the maximum weight stable set problem, which is NP-hard, and no complete inequality description is known for general graphs. A productive line…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems II: p-Swap Local Search for k-Median Has Locality Gap 3 + 2/pResearch Paper

The k-median problem asks to open kkk facilities among a set of candidate sites so that the total distance from clients to their nearest open facility is as small as possible. It is a basic model of facility location and of clustering, and it is NP-hard, so the question studied in approximation algorithms is how close a polynomial-time method can get to the…

8 thms2 active usersReviewed
PreviousPage 25 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