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
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Optimum Branchings: The Vertices of the Branching Polyhedron Are Exactly the BranchingsResearch Paper

A branching in a directed graph is a set of edges that contains no cycle (even ignoring directions) and in which no two edges point to the same node; a connected branching is an arborescence, a tree rooted at one node with all edges directed away from the root. The optimum branching problem asks, for real weights on the edges, for a branching of maximum…

9 thms4 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

On Certain Polytopes Associated with Graphs V: Zero-One Optima of the Odd-Cycle Relaxation on Series-Parallel GraphsResearch Paper

The stable set problem asks for a largest set of pairwise non-adjacent vertices in a graph; its size is the stability number α(G)\alpha(G)α(G). It is NP-hard in general, and a standard way to attack it in integer programming is to write down linear inequalities valid for all stable sets and solve the resulting linear program. The weakest such relaxation uses only…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling I: Best-α on One Machine with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is one of the basic objectives of machine scheduling: it measures how long, on average, a job waits in the system. On a single machine with release dates and no preemption (written 1∣rj∣∑Cj1|r_j|\sum C_j1∣rj​∣∑Cj​), the problem is strongly NP-hard, so research has focused on approximation algorithms whose…

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

Local Search Heuristics for k-Median and Facility Location Problems III: Add-Drop-Swap Local Search for Uncapacitated Facility Location Has Locality Gap 3Research Paper

The uncapacitated facility location (UFL) problem is one of the basic models of location theory and operations research: a firm chooses which warehouses, plants or servers to open, paying a fixed cost for each open site and a service cost for every client according to its distance to the nearest open site. It is also a standard test case for approximation…

10 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: naimengye

Understanding Machine Learning XV: Neural NetworksTextbook

A feedforward neural network is a directed acyclic graph of neurons, each computing a fixed scalar activation of a weighted sum of its inputs; fixing the graph and the activation and letting the weights vary gives a hypothesis class. Chapter 20 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO97811072…

8 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

An Introduction to Computational Learning Theory III: The Vapnik-Chervonenkis Dimension, ε-Nets and Sample ComplexityTextbook

Chapter 3 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks how many random examples suffice to learn a concept from an infinite class. The cardinality bound of Occam's Razor is useless there, yet the rectangle game of Chapter 1 shows that some infinite classes are learnable…

8 thms4 active usersReviewed
🏆Completed
Captain: Yuxuan Xu

Magic Squares V: The Counting Function of Semi-Magic Squares of Every OrderResearch Paper

The magic-square programme already on this platform works at fixed small orders: MacMahon's enumeration of the 3×33\times33×3 squares, both the magic count M3(3e)=2e2+2e+1M_{3}(3e)=2e^{2}+2e+1M3​(3e)=2e2+2e+1 and the semi-magic count H3(t)=3(t+34)+(t+22)H_{3}(t)=3\binom{t+3}{4}+\binom{t+2}{2}H3​(t)=3(4t+3​)+(2t+2​); the classification of the normal 3×33\times33×3 squares; and the counts of the panmagic and symmetric order-three classes. Each…

31 thms4 active usersReviewed
🏆Completed
Number Theory·Captain: aarontcao

Shao's three units theorem: density 5/8 forces a three-fold additive basisResearch Paper

Let mmm be an odd squarefree positive integer and let AAA be a set of units modulo mmm with ∣A∣>58φ(m)|A| > \frac{5}{8}\varphi(m)∣A∣>85​φ(m). Then A+A+A=Z/mZA + A + A = \mathbb{Z}/m\mathbb{Z}A+A+A=Z/mZ: every residue class, unit or not, is a sum of three elements of AAA.

10 thms4 active usersReviewed
🏆Completed
Graph Theory·Captain: LG

Counterexamples to Hadwiger's conjectureResearch Paper

Hadwiger's conjecture (Hadwiger, 1943) asserts that every finite nonempty simple graph GGG satisfies h(G)≥χ(G)h(G)\ge\chi(G)h(G)≥χ(G): the largest order of a complete minor is at least the chromatic number. It places planar coloring in a minor-theoretic setting. The K4K_4K4​-minor-free case was proved by Hadwiger and Dirac; Wagner's structure theorem makes the K5K_5K5​-minor-free case…

8 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper LearningResearch Paper

In binary classification, every PAC learnable class can be learned by a proper learner, one that always outputs a member of the class: empirical risk minimization does it, and learnability is characterized by the VC dimension. With many labels the picture changes. Daniely and Shalev-Shwartz introduced the DS dimension and conjectured that it characterizes…

11 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: Shuze Chen

A Sharp Rigidity Law for Effective ResistanceResearch Paper

Effective resistances summarize a weighted graph as an electrical network: the resistance RuvR_{uv}Ruv​ between two vertices is the voltage needed to send one unit of current from uuu to vvv. They govern commute times and are the sampling probabilities of spectral sparsification (Spielman–Srivastava 2011), and they form a metric on the vertices.

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

Robust Shattering ArgumentsResearch Paper

Many fast randomized distributed algorithms, for the Lovász Local Lemma, maximal independent set, matching and coloring, follow the shattering paradigm (Barenboim, Elkin, Pettie, Schneider, JACM 2016). A randomized pre-shattering phase solves the problem on most of the graph. It leaves a residual set BBB of unresolved nodes, and the analysis has to show that…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: Shuze Chen

Fatness and FlatnessResearch Paper

The theory of sparsity of Nešetřil and Ossona de Mendez describes the algorithmically useful structure of sparse graph classes. Its central notion, nowhere denseness, has many equivalent definitions. Two of them matter here. The first says that, for every radius rrr, contracting disjoint connected subgraphs of radius at most rrr cannot produce arbitrarily large…

20 thms3 active usersReviewed
🏆Completed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
Algebraic Geometry·Captain: mikedeng1

Toward Algebraic Geometry of Fixed-Parameter Tractability: Case StudiesResearch Paper

A hitting set selects vertices so that every input hyperedge contains a selected vertex. In the parameterized problem, the question is whether a hitting set of size at most a given number kkk exists. Even when a small solution exists, the collection of feasible solutions can be large. For algorithms that retain possible certificates, the relevant question is…

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

Improved Bounds for Online Matching with Random Edge ArrivalsResearch Paper

An online matching algorithm receives edges sequentially and immediately decides whether to accept each one. Accepted edges must have disjoint endpoints, and decisions are irrevocable. This captures a basic allocation constraint: an accepted pair consumes both of its participants, while future opportunities remain unknown. The order in which opportunities…

32 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

The Local Query Complexity of Greedy Coloring and Other Extendable Labeling ProblemsResearch Paper

A graph may be too large for an application to construct and store a complete solution before answering its first question. A local computation algorithm instead answers questions about individual vertices through queries to the underlying graph. Its answers must remain consistent with one solution of the whole graph. The relevant resource here is the…

23 thms3 active usersReviewed
🏆Completed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert–Varshamov BoundResearch Paper

An insertion or deletion changes the positions of later symbols. A receiver therefore faces uncertainty about alignment as well as about the values of damaged bits. Edit-correcting codes address this problem by restricting the transmitted words so that nearby received sequences identify a unique original message. File synchronization is one concrete…

33 thms3 active usersReviewed
🏆Completed
cryptographyInformation Theory·Captain: mikedeng1

Expanding Codes with Polynomial StretchResearch Paper

A collection of sparse parity equations can involve almost as many variables as its total number of variable occurrences. This expansion property excludes small linear dependencies and is relevant to the complexity of recognizing noisy planted equations. It is therefore useful to distinguish what expansion guarantees from what it leaves possible. Hair and…

23 thms3 active usersReviewed
🏆Completed
Information TheoryTheoretical Computer Science·Captain: mikedeng1

Explicit Edit Codes via MulticoloringResearch Paper

An edit channel can insert a symbol, delete a symbol, or substitute one symbol for another. Insertions and deletions change the positions of subsequent symbols, so a decoder must recover information without knowing which received positions correspond to transmitted positions. A code restricts transmitted words so that these changes can be corrected. The…

53 thms3 active usersReviewed
🏆Completed
Algebra·Captain: mikedeng1

Optimal partition rank bounds for the determinant and other multilinear polynomialsResearch Paper

A polynomial can be represented as a sum of products in many ways. When its variables are divided into rows and every monomial uses exactly one variable from each row, a product can separate some rows from the others. The least number of such products is its partition rank. This measure studies a restricted form of algebraic computation: the factors in one…

52 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCsResearch Paper

In an edge-colored graph, a rainbow cycle is a cycle on which no color occurs twice. Extremal graph theory asks how much average degree forces such a cycle. The properly colored case already connects this question to bounds for locally correctable codes. Lin's submission extends the graph theorem to nonnegative edge weights and edges bearing several colors…

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

Stability Dichotomies for Boolean Constraint Satisfaction ProblemsResearch Paper

A solver can return a correct answer and still react sharply to a small change in its input. For a constraint satisfaction problem, deleting a requirement leaves every old solution valid, but a solver may nevertheless change many variable values. Understanding when that disruption is unavoidable is useful for distinguishing a property of the problem from a…

18 thms3 active usersReviewed
🏆Completed
Captain: mikedeng1

The Greedy Superstring Conjecture Is FalseResearch Paper

The shortest common superstring problem asks for a shortest word containing every member of a finite input set as a contiguous block. It models the compression of overlapping records and an idealized version of sequence assembly. A natural algorithm repeatedly joins the two current words with the longest suffix-prefix overlap. Understanding how much length…

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