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
ProbabilityStatistics·Captain: mikedeng1

Two Moments Suffice for Poisson Approximations: The Chen-Stein Method 1: Total Variation Bound 2[(b₁+b₂)(1−e^{−λ})/λ + b₃′(1∧1.4λ^{−1/2})] for a Sum of Dependent IndicatorsResearch Paper

Counts of rare events often look Poisson even when the events are dependent. For example, a local pattern in a random graph can overlap another copy of the pattern, so the corresponding occurrence indicators are not independent. The useful question is quantitative: how far is the distribution of the total count from a Poisson distribution with the same…

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

On the Graph Structure of Convex Polyhedra in n-Space II: Whitney's Theorem, a Graph Is n-Tuply Connected iff Any Two Points Are Joined by n Disjoint PathsResearch Paper

Vertex connectivity measures how robust a network is against the failure of nodes. It can be measured in two ways that look different. One way counts the fewest nodes whose removal disconnects the network. The other counts the routes between two nodes that share no intermediate node. Whitney's theorem (1932) says that the two measures agree for every pair…

9 thms4 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 2: Attaching New Vertices to a (p+1)-Regular Ramanujan Graph and Adding Loops Keeps Every Nontrivial Eigenvalue at Most √(2(p+1)) + √p + o(1)Research Paper

Sparse graphs whose adjacency spectrum is concentrated near zero, expanders, are used throughout theoretical computer science: in error-correcting codes, derandomization, sorting and routing networks, and the construction of pseudorandom objects (Hoory, Linial and Wigderson, survey). The best possible spectral expansion for a ddd-regular graph is governed by…

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

Maximal Flow Through a Network II: In an ab-Planar Network Some Chain from Source to Sink Meets Every Cut Exactly OnceResearch Paper

The maximum flow problem asks how much of a commodity can be shipped from a source to a sink through a network whose arcs have limited capacities. L. R. Ford, Jr. and D. R. Fulkerson's 1956 paper Maximal Flow Through a Network proved the minimal cut theorem: the largest flow value equals the smallest total capacity of a set of arcs that separates source…

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

Maximal Flow Through a Network I: The Minimal Cut Theorem — the Maximal Flow Value Equals the Minimum Value of a Disconnecting SetResearch Paper

The question behind this mission was posed by T. E. Harris to L. R. Ford, Jr. and D. R. Fulkerson at RAND, in the setting of rail transport: given a rail network linking two cities, with a capacity on every link, find the largest steady flow from one city to the other. Ford and Fulkerson's answer, the minimal cut theorem, published in the Canadian Journal…

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

Maximum Matching and a Polyhedron With 0,1-Vertices: The Vertices of the Matching Polyhedron Are Exactly the Matching VectorsResearch Paper

A matching in a graph is a set of edges no two of which share a node. Given a real weight on every edge, the maximum-weight matching problem asks for a matching of largest total weight. It is one of the basic problems of combinatorial optimization: assignment, pairing and scheduling problems reduce to it, and it is the standard example of a combinatorial…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 2: Sequential Posted Prices e/(e−1)-Approximate the Optimal Revenue under a Partition Matroid ConstraintResearch Paper

A seller who knows the distributions of buyers' values can maximise expected revenue with Myerson's optimal mechanism (Myerson 1981): collect bids, compute virtual values, serve a feasible set of maximum virtual surplus, and charge threshold payments. Real sellers seldom run such auctions. They post prices: a buyer is offered a take-it-or-leave-it price and…

21 thms4 active users
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 1: Sequential Posted Prices 2-Approximate the Optimal Revenue under a Matroid ConstraintResearch Paper

A seller who must decide whom to serve among several buyers with private values can, in principle, run Myerson's revenue-optimal mechanism: collect bids, compute virtual values, serve the feasible set of largest virtual surplus, and charge threshold payments (Myerson 1981). In practice sellers rarely do this. Retail, ticketing and online platforms mostly…

21 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources IV: Every Feasible Schedule Obeys a Minimal Delaying Mode of Each Forbidden SetTextbook

Resource-constrained project scheduling with general temporal constraints, written PS∣temp∣Cmax⁡PS|temp|C_{\max}PS∣temp∣Cmax​, asks for start times of the activities of a project that respect minimum and maximum time lags between activities and the capacities of renewable resources (staff, machines, reactors), and that minimize the project duration. Deciding whether a feasible…

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

Theory of Games and Economic Behavior IX: Solutions for Acyclic RelationsTextbook

The solution concept of von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944) is defined from two ingredients: a set of imputations and a domination relation between them. A solution is a set of imputations that is internally stable (no member dominates another) and externally stable (every non-member is dominated by some member). In…

13 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VII: Simple Games, Weighted Majorities and the Main Simple SolutionTextbook

Many collective decisions are taken by coalitions that either carry the vote or do not: committees, legislatures, shareholder meetings, councils with weighted votes. In such a situation the only aim of a participant is to be part of a coalition that wins, and nothing is left to bargain about except the division of the prize inside the winning coalition.…

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

Numerical Techniques for Stochastic Optimization V: Asymptotic Optimality of List Scheduling for the Machine Investment ProblemTextbook

Two-stage stochastic integer programs combine the two hardest features of mathematical programming: uncertainty in the data and integrality of the decisions. Even evaluating the objective of such a program at a single first-stage decision requires the expected optimal value of an NP-hard combinatorial problem. Chapter 8 of Ermoliev and Wets (eds.), Numerical…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

The Distributionally Robust Chance-Constrained Vehicle Routing Problem I: With a Subadditive Demand Estimator the Two-Index Vehicle Flow Formulation Is ExactResearch Paper

The capacitated vehicle routing problem (CVRP) asks for delivery routes of minimum cost. Each route starts and ends at a depot, every customer is visited exactly once, and the demand served on a route does not exceed the vehicle capacity. The problem is central in logistics and one of the most studied problems in combinatorial optimization. Its standard…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: Shuze Chen

Discrete Convex Analysis XX: Integral Convexity of L-Convex SetsTextbook

Shortest-path distances and network potentials are among the oldest objects in combinatorial optimization: a directed graph with arc lengths, its shortest-path distances, and the "feasible potentials" (vertex labels consistent with those lengths) underlie duality in min-cost flow, scheduling, and difference-constraint systems. Murota's Discrete Convex…

23 thms4 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis I: Valuated MatroidsTextbook

Matroids abstract the combinatorial content of linear independence: which sets of columns of a matrix are independent, which are maximal (bases), and how bases relate to each other. This abstraction, isolated independently by Whitney (1935) and van der Waerden's school, turned out to be exactly the right level of generality for a large family of greedy and…

13 thms4 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Three Partition Refinement Algorithms 2: Refining by the Smaller HalfResearch Paper

Many equivalence problems on finite structures reduce to computing the coarsest partition of a finite set that is compatible with a relation. Deciding whether two states of a finite labelled transition system are bisimilar, testing congruence of finite-state processes in Milner's calculus of communicating systems (CCS), and minimizing a deterministic finite…

12 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XVI: Unions of Upper Monotone Polytopes and PolymatroidsTextbook

This mission is the sixteenth and last of the Disjunctive Programming series, and its goal theorem is the book's own closing result. The chapter's arc closes a loop opened at the very start of the book: Theorem 2.1 (02a-convex-hull) gave the convex hull of a union of polyhedra in the same space via lifting; this chapter's Theorem 13.13 (not drafted in this…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Disjunctive Programming XV: Dominants of Polytopes and Upper SeparationTextbook

Many real-world disjunctive models are not unions of polyhedra in a single shared space, but unions of polyhedra in different spaces linked by a logical implication: some action affecting one set of entities has consequences for another. Balas's treatment of such models (§17 of the book, following [17]) reduces to understanding a single auxiliary object…

8 thms4 active users
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization II: One Round of N on the Stable Set Polytope Gives Exactly the Odd Hole ConstraintsResearch Paper

The stable set problem (vertex packing) asks for a largest set of pairwise non-adjacent nodes of a graph. It is NP-hard, and its polyhedral study, the description of the stable set polytope STAB(G)\mathrm{STAB}(G)STAB(G) by linear inequalities, is one of the most studied topics of polyhedral combinatorics. Classes of valid inequalities (clique, odd hole, odd antihole,…

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

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems 2: The Augmentation Bound for Maximum-Augmentation PathsResearch Paper

The maximum flow problem asks how much of a commodity can be sent from a source to a sink through a network whose arcs have capacities. It underlies bipartite matching, transportation, scheduling and many reductions in combinatorial optimization. The classical method for it, the labeling method of Ford and Fulkerson (Flows in Networks, 1962), repeatedly…

11 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem I: Nearest Neighbor Tours Can Be Far from OptimalResearch Paper

The traveling salesman problem with the triangle inequality asks for a shortest closed tour through nnn points whose distances form a metric. It is NP-hard, so in practice tours are built by fast construction heuristics, and the natural question is how far such a tour can be from optimal in the worst case. Rosenkrantz, Stearns and Lewis (SIAM J. Comput. 6(3),…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 4: First-Fit Decreasing Uses at Most 71/60 L* + 5 Bins When No Item Exceeds 1/2Research Paper

Bin packing asks how to place a list of items with sizes in (0,1](0,1](0,1] into as few unit-capacity bins as possible. It models the cutting of stock material, the packing of files onto tracks of a disc and the assignment of jobs to machines with a common deadline. Deciding the optimum is NP-hard, so in practice simple rules are used, and the question is how far…

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

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 3: First-Fit Decreasing and Best-Fit Decreasing Use at Most 11/9 L* + 4 BinsResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models table formatting, the placement of program segments on pages, and the allocation of files to disc tracks, and it is NP-complete, so exact solutions require search in general. Johnson, Demers, Ullman, Garey and Graham (SIAM J. Comput. 3 (1974)) therefore…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 2: First-Fit and Best-Fit with Bounded Item SizesResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models cutting stock, memory allocation, file placement and the loading of trucks, and it is NP-hard, so in practice lists are packed by simple rules that look at one item at a time. The two most widely used rules are First-Fit and Best-Fit, and the question that…

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

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 1: First-Fit and Best-Fit Have Asymptotic Worst-Case Ratio 17/10Research Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It is one of the first problems studied through the worst-case analysis of approximation algorithms, and it models storage allocation, paging and file placement on tracks, as well as cutting-stock problems in operations research. Deciding the optimum exactly is NP-hard,…

9 thms4 active usersReviewed
PreviousPage 6 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