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

Scenario Reduction Algorithms in Stochastic Programming II: The Minimal Reduction Distance of a Regular Binary Scenario TreeResearch Paper

Multistage stochastic programs are solved on a finite scenario tree, a discrete probability measure whose atoms are paths of a stochastic process. The size of the deterministic equivalent grows with the number of scenarios, so practitioners replace the original measure P=∑i=1NpiδωiP=\sum_{i=1}^N p_i\delta_{\omega_i}P=∑i=1N​pi​δωi​​ by a measure supported on n<Nn<Nn<N of its scenarios.…

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

Fast Algorithms for Finding Nearest Common Ancestors II: Nearest Common Ancestors in a Complete Binary Tree by Symmetric-Order ArithmeticResearch Paper

The nearest common ancestor (nca) problem asks, for a fixed rooted tree and a sequence of vertex pairs (v,w)(v, w)(v,w), for the deepest vertex that is an ancestor of both. It is a basic step in suffix-tree string algorithms and is equivalent to range-minimum queries (Bender, Farach-Colton, 2000). Harel and Tarjan, Fast Algorithms for Finding Nearest Common Ancestors,…

11 thms3 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

Fast Algorithms for Finding Nearest Common Ancestors I: A Lower Bound for Pointer MachinesResearch Paper

The nearest common ancestor problem asks, for a rooted tree and two of its vertices xxx and yyy, for the deepest vertex that is an ancestor of both, written nca⁡(x,y)\operatorname{nca}(x,y)nca(x,y). It appears as a subroutine in string algorithms (suffix trees), in graph algorithms (path queries, dominators) and in the analysis of set-union structures. Aho, Hopcroft and Ullman (…

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Validation of Subgradient Optimization II: A Unique Optimal Assignment Makes the Dual Optimal Set Full-DimensionalResearch Paper

The subgradient method maximizes a concave, piecewise-linear function w(π)=min⁡k{ck+π⋅vk}w(\pi)=\min_k\{c_k+\pi\cdot v_k\}w(π)=mink​{ck​+π⋅vk​} by moving along a subgradient vkv_kvk​ of an active piece with a prescribed step. Held, Wolfe and Crowder's 1974 paper Validation of subgradient optimization tested the method on three families of Lagrangean duals from combinatorial optimization — the…

6 thms3 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

The Erdős Matching Conjecture and Concentration Inequalities: The Conjecture in a Linear RangeResearch Paper

In 1965 Erdős asked how large a family of kkk-element subsets of an nnn-element set can be if it contains no s+1s+1s+1 pairwise disjoint members. The question, now called the Erdős Matching Conjecture (EMC), contains the Erdős–Ko–Rado theorem (the case s=1s=1s=1) and is one of the central open problems of extremal set theory. Beyond combinatorics it is tied to tail bounds…

23 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma: ℓ1-Proximity of Integer and LP OptimaResearch Paper

Integer programs are routinely solved by first solving their linear programming (LP) relaxation and then searching for an integer optimum near the fractional one. How near an integer optimum must be is the subject of proximity theorems. They bound the search region of branch-and-bound and of dynamic programming, and they turn a fractional optimum into a…

12 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingGraph TheoryOperations Research·Captain: mikedeng1

The Steiner Problem in Graphs: Algorithm A Computes the Length of the Steiner TreeResearch Paper

The Steiner problem in graphs asks for the cheapest way to connect a prescribed set of nodes of a network, where intermediate nodes may be used freely. It is the network version of the classical Euclidean Steiner tree problem surveyed by Gilbert and Pollak (SIAM J. Appl. Math. 16, 1968), and it arises wherever a few sites must be joined through an existing…

10 thms3 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Sorting in c log n Parallel Steps: Sorting Networks of Logarithmic DepthResearch Paper

A sorting network is a sorting procedure whose sequence of comparisons is fixed in advance, independently of the data. Its depth, the number of rounds of simultaneous comparisons on disjoint pairs, is the parallel running time. Sorting networks are used in parallel and hardware sorting, in switching networks, and in cryptography, where a data-independent…

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

Maximizing Non-Monotone Submodular Functions II: A Nonadaptive Algorithm Achieves 1/3 of the OptimumResearch Paper

Maximizing a submodular set function without constraints contains Max Cut, Max Directed Cut, maximum facility location and several graph and hypergraph cut problems as special cases, and it appears in operations research wherever a value exhibits diminishing returns but is not monotone (profit that combines coverage with a cost, for example). These problems…

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

Shortest Connection Networks And Some Generalizations: Construction Principles P1 and P2 Yield a Shortest Spanning Subtree of Every Connected Labelled GraphResearch Paper

Connecting a set of terminals by a network of direct links of least total length is one of the oldest problems of combinatorial optimization. R. C. Prim's 1957 paper in the Bell System Technical Journal (DOI) was motivated by the rate structure for Bell System leased-line services, in which the charge for connecting a set of terminals depends on the length…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

A Simple Parallel Algorithm for the Maximal Independent Set Problem II: The Round Bound of the Derandomized AlgorithmResearch Paper

A maximal independent set (MIS) of a graph is a set of pairwise non-adjacent vertices to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be computed by a fast parallel algorithm was a central question of parallel complexity in the early 1980s: Karp and…

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

Maximizing Non-Monotone Submodular Functions I: A Uniformly Random Set Achieves 1/4 of the Optimum, and 1/2 for Symmetric FunctionsResearch Paper

Many combinatorial optimization problems ask for a subset of a finite ground set that maximizes a set function with diminishing returns: Max Cut and Max Directed Cut in graphs, facility location, maximum entropy sampling, and welfare problems in combinatorial auctions all fit this pattern. The common abstraction is the maximization of a submodular function,…

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

Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper

Minimizing the sum of weighted completion times of jobs on identical parallel machines is one of the basic objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. When the jobs are subject to precedence constraints (a job may start only after certain other jobs have finished), the problem is…

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

Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper

Minimizing the sum of weighted completion times ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on mmm identical parallel machines it is harder still, so the…

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

Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is a basic objective in machine scheduling. It measures how long a job spends in the system on average. With several identical machines, release dates and no preemption (written P∣rj∣∑CjP|r_j|\sum C_jP∣rj​∣∑Cj​), the problem is strongly NP-hard already on one machine. Research has therefore looked for…

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

Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper

Facility location asks where to open service points (warehouses, plants, servers) and how to connect customers to them so that the total opening cost plus the total connection cost is minimum. In the capacitated version each facility can serve only a limited number of customers, which is the situation in most applications: a warehouse has a floor area, a…

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

Local Search Heuristics for k-Median and Facility Location Problems I: Single-Swap Local Search for k-Median Has Locality Gap 5Research Paper

The k-median problem asks where to open kkk facilities so that the total distance from a set of clients to their nearest open facility is as small as possible. It is a basic model of facility location in operations research (placing depots, warehouses or servers) and of clustering with representative centres, and it is NP-hard, so the question of interest is…

8 thms3 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: naimengye

Understanding Machine Learning XXI: Covering NumbersTextbook

Chapter 26 bounded the rate of uniform convergence by the Rademacher complexity; Chapter 27 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), introduces a second, metric measure of the size of a set of vectors, its covering numbers N(r,A)N(r, A)N(r,A), the smallest number of Euclidean balls of…

7 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: naimengye

Understanding Machine Learning XVII: ClusteringTextbook

Clustering is the most widely used tool of exploratory data analysis and, at the same time, the least well defined: similar points should share a cluster and dissimilar points should not, but similarity is not transitive while cluster membership is, and without labels there is no ground truth against which to evaluate a proposed grouping. Chapter 22 of…

7 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

An Introduction to Computational Learning Theory V: Classification Noise and Statistical QueriesTextbook

Chapter 5 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks what happens to PAC learning when the labels are unreliable. In the classification noise model of Angluin and Laird, each label returned by the oracle is flipped independently with a fixed probability η<1/2\eta < 1/2η<1/2. The…

7 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

An Introduction to Computational Learning Theory IV: Weak and Strong Learning, Boosting and Chernoff BoundsTextbook

Chapter 4 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks whether the PAC model's demand for arbitrarily small error and confidence is essential. A weak learning algorithm need only, with some fixed positive probability, output a hypothesis that beats random guessing by a…

7 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Fundamentals of Supply Chain Theory VI: Pooling and FlexibilityTextbook

A firm that holds inventory in five warehouses needs more safety stock than one that holds the same inventory in one warehouse, because the demands of five regions do not all run high at once. Eppen (1979) made this precise for a multi-location newsvendor and gave it its name, the risk-pooling effect. Chapter 7 of Snyder and Shen's Fundamentals of Supply…

10 thms3 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Convex Polytopes V: Recognition from projections (GRU-M05-PROJECTION-RECOGNITION)Textbook

A convex set can be studied through its images in spaces of smaller dimension. Each image records part of the geometry, while losing the information along the directions that are collapsed. A finite convex hull always has finite convex hulls as its affine images. The converse asks whether sufficiently rich projection data can force the original set to have…

5 thms3 active usersReviewed
🏆Completed
Mechanism Design·Captain: Shuze Chen

Algorithmic Game Theory V: Stable Matching and Trading without MoneyTextbook

When money is off the table and the Gibbard–Satterthwaite theorem (Mission III of this series) blocks general strategyproof choice, restricted preference domains reopen the door. The two great examples both come from allocation: Shapley–Scarf's housing market (1974), where Gale's Top Trading Cycle algorithm finds the unique core allocation and Roth (1982)…

9 thms3 active usersReviewed
Graph Theory·Captain: hao jia

Six Colors for Star Edge-Coloring Subcubic Graphs (OPG-37271)Open Problem

A star edge coloring is a proper edge coloring with an additional local restriction: no path or cycle of four edges may use only two colors. It sits between ordinary proper edge coloring and strong edge coloring. The problem is local enough to admit finite obstruction searches, but global enough that independently valid local colorings may fail to fit…

11 thms3 active usersReviewed
PreviousPage 24 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