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

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms: O(log n) Amortized Time for Delete Min and Delete, O(1) for Every Other F-Heap OperationResearch Paper

Many network optimization algorithms spend most of their time in a heap (priority queue): a set of items with real keys that supports inserting an item, finding and deleting an item of minimum key, melding two heaps, decreasing the key of an item, and deleting an arbitrary item. Dijkstra's shortest-path algorithm performs at most one delete min per vertex…

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

Matching, Euler Tours and the Chinese Postman II: The Parity Problem Is a Minimum 1-Matching of the Odd Nodes under Shortest-Path LengthsResearch Paper

A postal route that must traverse every street and return to its starting point is a Chinese postman tour. In a street network, crossings are nodes, streets are edges, and the cost of a route is the sum of the lengths of the streets it traverses, counted with repetition. The practical question is which streets must be repeated, and how often. Edmonds and…

8 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman III: Next-Node Lists Describe an Euler Tour iff Their Last-Exit Edges Form an ArborescenceResearch Paper

The Chinese postman problem asks for a shortest closed walk in a graph that traverses every edge at least once. Edmonds and Johnson (Math. Programming 5 (1973) 88–124) reduce it to two subproblems: choosing, by matching, which edges to duplicate so that every node has even degree, and then actually finding an Euler tour of the resulting even graph, a closed…

8 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Minimum Partition of a Matroid Into Independent Subsets: A Matroid Splits Into k Independent Sets Iff Every Subset A Has |A| ≤ k·r(A)Research Paper

A matroid abstracts the dependence structure of the columns of a matrix: which sets of columns are linearly independent, forgetting the numbers themselves. Graphs are the special case of incidence matrices over the integers mod 2, where a set of edges is independent exactly when it contains no cycle. A natural combinatorial question in this setting is the mi…

17 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

Truly Subcubic APSP on a Word RAMResearch Paper

All-pairs shortest paths (APSP) computes the shortest distance between every pair of vertices in a weighted graph. It is a fundamental problem in graph algorithms and a fundamental problem in fine-grained complexity.

61 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 3: On the 3-Dimensional Matching Instances, a Schedule within ρ < 3/2 of Optimal Has Makespan ≤ 2 Iff a Matching ExistsResearch Paper

Minimum makespan scheduling on unrelated parallel machines, written R ∣∣ Cmax⁡R\,||\,C_{\max}R∣∣Cmax​, is one of the basic models of scheduling theory: nnn jobs must each be run on one of mmm machines, and the time a job takes depends arbitrarily on the machine. Lenstra, Shmoys and Tardos (CWI Report OS-R8714, 1987; journal version Math. Programming 46, 1990) gave a polynomial…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 4: With Times in {p, q} and gcd(p, q) = 1, a q-Dimensional Matching Exists Iff a Schedule Has Makespan ≤ pqResearch Paper

Minimum makespan scheduling on unrelated parallel machines asks for an assignment of nnn jobs to mmm machines, where job jjj takes pijp_{ij}pij​ time units on machine iii, so that the largest machine load is as small as possible. In the three-field notation of Graham, Lawler, Lenstra and Rinnooy Kan (1979) it is R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​. It models load balancing across…

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

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments V: Stackelberg Matroid Pricing Is an Assortment Problem Under a Regular Choice ModelResearch Paper

In Stackelberg network pricing a leader sets prices on some resources, and a follower then buys the cheapest structure available to them, paying the leader for the priced resources they use. The Stackelberg Minimum Spanning Tree problem, introduced by Cardinal, Demaine, Fiorini, Joret, Langerman, Newman and Weimann (Algorithmica 2011), is the version in…

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

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments III: The Three Revenue-Ordered Approximation Bounds Are TightResearch Paper

A retailer or an airline chooses which products to offer, and customers choose among what is offered, or buy nothing. Choosing the offer set that maximizes expected revenue is the assortment problem, central to revenue management (Talluri and van Ryzin, 2004). It is NP-hard even for simple mixtures of logit models, so practice relies on heuristics. The most…

15 thms2 active usersReviewed
🏆Completed
Discrete GeometryGraph Theory·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 3: Larman's Bound 2^(d−1)·n Holds in the Base AbstractionResearch Paper

The diameter of a polyhedron is the largest number of edges needed to travel between two vertices of its graph, its 1-skeleton. Whether this number is bounded by a polynomial in the dimension ddd and the number of facets nnn is a long-standing open question in polyhedral combinatorics; edge walks are the moves of vertex-following methods such as the simplex…

2 thms2 active usersReviewed
🏆Completed
Discrete GeometryGraph Theory·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 2: The Kalai–Kleitman Bound n^(1+log d) Holds in the Base AbstractionResearch Paper

The diameter of a polyhedron is the largest number of edges needed to travel between two vertices of its graph. Bounding that number from the dimension and the number of facets is a central question in polyhedral combinatorics because edge walks are the discrete moves available to many vertex-based optimization methods. The Kalai–Kleitman bound gives a…

2 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Solving Large-Scale Zero-One Linear Programming Problems: A Minimal Cover Inequality Cuts Off x̄ iff the Knapsack Problem (2.12) Has Optimal Value Less Than OneResearch Paper

Large zero–one linear programs can contain constraints involving only a small fraction of their variables. Crowder, Johnson and Padberg study how to extract useful inequalities from one such row while solving the larger program. Their computational method identifies a violated inequality at a current linear programming solution, adds it, and resolves the…

8 thms2 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

A Characterization of Multiclass Learnability 1: Classes of Finite DS Dimension Have n → r Sample Compression Schemes with r Polylogarithmic in nResearch Paper

In multiclass classification a learner sees examples (x,y)(x, y)(x,y) with xxx in a domain X\mathcal XX and a label yyy in a set Y\mathcal YY, and must predict labels of new points. When Y\mathcal YY is finite, the Natarajan dimension characterizes PAC learnability, extending the role of the VC dimension in binary classification (Natarajan 1989; Ben-David, Cesa-Bianchi,…

20 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 6: The Optimal Value of S_G Lies Between n² − an²(ln 1/a + 2) and n² − an²Research Paper

The problem 1 ∣ prec ∣ ∑wjCj1\,|\,\mathrm{prec}\,|\,\sum w_jC_j1∣prec∣∑wj​Cj​ asks for a single-machine sequence of jobs, respecting precedence constraints, that minimizes the weighted sum of completion times. It has been known to be strongly NP-hard since Lawler (1978) and Lenstra and Rinnooy Kan (1978), several different 2-approximation algorithms are known, and closing the…

8 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 4: Vertex Cover in Connected Graphs of Degree ≤ 3 Reduces to Weighted Vertex Cover for Interval-Order InstancesResearch Paper

In the single-machine scheduling problem 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_jC_j1∣prec∣∑wj​Cj​, a set NNN of nnn jobs, each with a processing time pj≥0p_j\ge 0pj​≥0 and a weight wj≥0w_j\ge 0wj​≥0, is processed on one machine without interruption, subject to precedence constraints given by a partial order PPP on NNN. The aim is to minimize the weighted sum of completion times ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​. The problem is…

10 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 2: The Rank Postulates and the Circuit Postulates Are EquivalentResearch Paper

Hassler Whitney's 1935 paper On the Abstract Properties of Linear Dependence introduced matroids: finite sets of elements carrying an abstract notion of dependence that captures what linearly dependent columns of a matrix and cycles of a graph have in common. A distinctive feature of the paper is that it gives several independent axiom systems for the same…

12 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 3: Deleting Far-Apart Tree-Like Vertices of a Near-Ramanujan Graph and Matching Their Neighbours Keeps λ ≤ 2√(d−1) + εResearch Paper

Sparse graphs with small nontrivial eigenvalues, expanders, are basic objects in combinatorics and theoretical computer science. They are used in error-correcting codes, derandomization, sorting networks, and the analysis of random walks. The Alon–Boppana bound says that a ddd-regular graph on nnn vertices has a nontrivial eigenvalue of absolute value at least …

13 thms2 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 5: The Seven-Element Fano Matroid Corresponds to No Real MatrixResearch Paper

Whitney's 1935 paper On the Abstract Properties of Linear Dependence introduced matroids: finite sets equipped with a rank function, or equivalently a family of independent sets, obeying a few postulates abstracted from the linear dependence of the columns of a matrix. The obvious first question about such an abstraction is whether it is genuinely more…

13 thms2 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 6: Every Matroid Satisfying (C*) Is Represented by a Matrix of Integers Mod 2Research Paper

Whitney's 1935 paper introduced matroids as an abstraction of linear dependence among the columns of a matrix. Most of the paper works over the real numbers; its appendix asks which matroids arise from matrices of integers mod 2, that is, matrices with entries 0 and 1 in which rank and dependence are computed over the two-element field. These are today's bin…

11 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

On the Abstract Properties of Linear Dependence 3: Two Elements Share a Component Iff Some Circuit Contains BothResearch Paper

Hassler Whitney's 1935 paper On the Abstract Properties of Linear Dependence introduced matroids: finite sets of elements carrying an abstract rank function that behaves like the rank of a set of vectors. Part II of the paper opens with the decomposition of a matroid into components. The question it answers is basic to every later use of matroids: when does…

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

On the Abstract Properties of Linear Dependence 1: The Rank Postulates and the Independence Postulates Are EquivalentResearch Paper

In 1935 Hassler Whitney asked which properties of linear dependence among the columns of a matrix can be stated without reference to the matrix at all. His answer, On the Abstract Properties of Linear Dependence (American Journal of Mathematics 57, 1935), introduced the matroid: a finite set together with a rank function obeying three short postulates. The…

8 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability+1·Captain: mikedeng1

Reversibility and Stochastic Networks VI: The Ewens Sampling Distribution Is Consistent Under Sampling Without ReplacementTextbook

The neutral theory of molecular evolution holds that much of the genetic variation observed at the molecular level is caused by selectively neutral mutations rather than by selection. To test it against data one needs the distribution of allele frequencies that a neutral model predicts, and in practice that distribution has to be compared with a sample from…

9 thms2 active usersReviewed
🏆Completed
Functional AnalysisMachine Learning·Captain: mikedeng1

The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network II: Fat-Shattering Bound for Bounded-Weight NetworksResearch Paper

In the mid-1990s, neural networks trained by gradient descent were observed to generalize well even when the number of weights far exceeded the number of training examples. The classical theory could not explain this: VC-dimension bounds for networks grow with the number of parameters, so for large networks they are vacuous. Bartlett's paper (IEEE Trans.…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

The Online Set Cover Problem 2: Given α ≥ c(C_OPT), the Weighted Potential-Function Algorithm Never Fails and Pays at Most (6+o(1)) α log m log nResearch Paper

Set cover is one of the basic covering problems of combinatorial optimization: given a ground set and a family of subsets with costs, choose a cheapest subfamily whose union contains every element. In many applications the elements to be covered are not known in advance but appear over time: requests for a service that must be served by opening facilities,…

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

The Online Set Cover Problem 3: Every Deterministic Online Algorithm Has Competitive Ratio at Least kr on the Block FamilyResearch Paper

In the online set cover problem of Alon, Awerbuch, Azar, Buchbinder and Naor (SIAM J. Comput. 2009; preliminary version STOC 2003), a ground set and a family of subsets are known in advance, but the elements that actually need covering arrive one at a time, and each must be covered on arrival by sets chosen irrevocably. The paper's motivating example is a…

6 thms2 active usersReviewed
PreviousPage 24 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