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 Research·Captain: naimengye

Fundamentals of Supply Chain Theory XI: The Traveling Salesman ProblemTextbook

A salesman must visit nnn cities and return home by the shortest route. The traveling salesman problem is the prototype of combinatorial optimization: easy to state, NP-hard (Karp 1972), and solved to optimality on instances with tens of thousands of nodes by branch-and-cut. In a supply chain it is the core of every vehicle routing model and of the…

15 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Complex Scheduling III: Interval Consistency Tests for the RCPSPTextbook

Exact methods for the resource-constrained project scheduling problem — branch-and-bound over activity lists or over start-time assignments, and the lower-bound computations inside them — live or die by how much of the search space can be discarded before it is enumerated. The standard tool is constraint propagation: deducing, from the precedence, resource…

9 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Scheduling Algorithms V: Preemptive Scheduling on Uniform MachinesTextbook

When several processors share a workload, the first question is how long the workload takes if it is spread out as well as possible. If a job may be interrupted and resumed later, possibly on another processor — preemption, the setting of operating systems, of communication links and of any resource that can be time-shared — the answer is a closed formula,…

6 thms2 active usersReviewed
🏆Completed
Mathematical Physics·Captain: LG

NRL Plasma Formulary I: Rothe–Hagen IdentityTextbook

The NRL Plasma Formulary is a standard desk reference of the plasma-physics community: a compilation of the formulas, constants and unit conversions used in daily practice. Its opening section, "Numerical and Algebraic" (p. 3 of the 2013 edition), collects the few purely mathematical identities the rest of the handbook leans on. Two of them are exact…

7 thms2 active usersReviewed
🏆Completed
Mathematical Physics·Captain: LG

Nuclear Shell Model I: Harmonic-Oscillator Magic NumbersTextbook

A nucleus whose proton number or neutron number equals one of 2,8,20,28,50,82,1262, 8, 20, 28, 50, 82, 1262,8,20,28,50,82,126 — the magic numbers — is markedly more tightly bound than the semi-empirical mass formula predicts, and markedly more stable against decay. The empirical evidence for closed nuclear shells at 505050 and 828282 protons and at 50,82,12650, 82, 12650,82,126 neutrons was assembled by Maria Goeppert…

7 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Convex Polytopes V.5: Effective enumeration of combinatorial typesTextbook

A convex polytope has both geometric coordinates and a finite pattern of faces. Moving its vertices can change distances and angles while preserving which vertices belong to which faces. Enumeration by combinatorial type asks for those incidence patterns, with geometrically different realizations of the same pattern counted together. Grünbaum’s enumeration…

7 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Convex Polytopes IV: Facet growth of binary polytopes (GRU-M04-BINARY-EXTREMA)Textbook

A vector whose coordinates are all zero or one records a collection of yes-or-no choices. Taking the convex hull of a collection of these vectors gives a 0/1-polytope, also called a binary polytope. Such objects connect discrete choices with geometry: points describe feasible combinations, while supporting inequalities describe restrictions that every…

2 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Convex Polytopes II: Finite convex representationsTextbook

A convex combination expresses a point as a weighted average of other points. Such representations connect geometric sets with finite lists of coordinates and coefficients. A point in a convex hull may initially be described using many generators, even when the ambient space has small dimension. Carathéodory's theorem gives a bound depending only on that…

1 thm2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Convex Polytopes V: Simplex sections through prescribed points (GRU-M05-PRESCRIBED-SECTIONS)Textbook

A polytope can be represented by cutting a higher-dimensional simplex with an affine flat. The geometry of the cut determines the resulting polytope. Perles's prescribed-point theorem adds a constraint to this representation: the cutting flat must pass through a point chosen in advance inside the simplex. Theorem 5.1.10 in Branko Grünbaum's Convex Polytopes,…

3 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Grünbaum — Gale data and combinatorial type (5.4.5)Textbook

A convex polytope has geometric coordinates and a combinatorial structure: its faces, ordered by inclusion. Different coordinates can describe the same combinatorial type. Gale transforms connect these viewpoints by encoding affine dependencies among the vertices as another point configuration, often in a smaller-dimensional space.

4 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Convex Polytopes III: Closed convex sets and recession geometryTextbook

A convex set contains the segment joining any two of its points. For a bounded closed convex set in finite-dimensional real space, extreme points describe the set through convex combinations. An extreme point cannot lie strictly between two distinct points of the set. Allowing unbounded sets introduces a second ingredient: directions in which one can move…

2 thms2 active usersReviewed
🏆Completed
Group Theory·Captain: dbenbenn

Cannon-Floyd-Parry: tree diagrams and the normal form for Thompson's group FTextbook

Thompson's group FFF is a finitely presented group of piecewise-linear homeomorphisms of the unit interval that has served since the 1960s as a standard supply of counterexamples in combinatorial group theory: its commutator subgroup is simple, every proper quotient of it is abelian, it contains no free subgroup of rank two, it is not elementary amenable, and…

19 thms2 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: burkh4rt

The Bunkbed Conjecture is FalseResearch Paper

Let G=(V,E)G=(V,E)G=(V,E) be a finite connected graph. In Bernoulli bond percolation each edge is independently retained with probability PPP and deleted otherwise, and one writes PP[u↔v]\mathbb{P}_P[u \leftrightarrow v]PP​[u↔v] for the probability that vertices uuu and vvv lie in the same component of the resulting random subgraph. Comparing such connection probabilities is a basic and…

38 thms2 active usersReviewed
🏆Completed
AlgebraInformation Theory·Captain: Rui Chao

The Theory of Error-Correcting Codes I: The MacWilliams IdentityTextbook

Error-correcting codes protect information against corruption by adding controlled redundancy. For a code, the distribution of Hamming weights records how its words are spread across possible distances from the zero word and determines basic quantities such as its minimum distance. Linear codes also carry an algebraic duality: every linear code CCC over a…

4 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: xbgxjack

Gross–Yellen Graph Theory I: Cayley's Tree FormulaTextbook

Counting the trees on a fixed, labeled vertex set is one of the oldest enumeration problems in graph theory. Cayley stated the count in 1889 while enumerating isomers of saturated hydrocarbons — each tree corresponds to a possible carbon skeleton — and the same number reappears throughout combinatorics as the number of spanning trees of the complete graph …

8 thms2 active usersReviewed
🏆Completed
Captain: wamlart

Discrete Mathematics—Lecture Notes I: Capacitated Hall MatchingTextbook

A finite allocation problem begins with a list of permitted choices. Each recipient may use some resources but not others, and a resource may be assigned at most once. Knowing that every recipient has an available resource is insufficient: several recipients may all depend on the same small pool. A useful theorem must decide whether the compatibility…

6 thms2 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: sr

Erdős (1947): The Probabilistic Ramsey Lower BoundResearch Paper

Ramsey theory asks for the smallest number R(k)R(k)R(k) such that every graph on R(k)R(k)R(k) vertices contains either a clique of size kkk or an independent set of size kkk. Beyond being one of the oldest problems in extremal combinatorics, Ramsey numbers sit at the junction of combinatorics, probability, and computer science: the two-coloring of edges they quantify is…

5 thms2 active usersReviewed
🏆Completed
Captain: ShouqiaoWang

Cubic Congruence for the q-Secant Inversion EnumeratorResearch Paper

Alternating permutations are a classical meeting point of enumerative combinatorics, permutation statistics, and special functions. An up--down permutation alternates between rises and falls, and their ordinary counts are the Euler secant and tangent numbers. Refining this count by the inversion statistic produces the qqq-secant polynomial E2n(q)E_{2n}(q)E2n​(q). Its…

2 thms2 active usersReviewed
🏆Completed
Number Theory·Captain: marwahaha

The exact minimum modulus for unique multiset sumsResearch Paper

For each natural n≥2n\ge2n≥2, the least modulus N≥2N\ge2N≥2 for the source's unique multiset-sum problem is

1 thm1 active userReviewed
🏆Completed
Complexity TheoryQuantum Information·Captain: marwahaha

A Proof of the Aaronson-Ambainis ConjectureResearch Paper

How much can a bounded polynomial depend on its inputs if its degree is small? The Aaronson–Ambainis conjecture asks for a quantitative answer that does not deteriorate when more variables are added. It arose in the study of constraints on quantum query speedups, but its statement is entirely about real polynomials on a finite cube. Aaronson and Ambainis…

550 thms1 active userReviewed
🏆Completed
Captain: marwahaha

Finite posets: compatibility, weak N and X obstructionsResearch Paper

Two elements of a partially ordered set are incomparable when neither is below the other. This symmetric, irreflexive relation forms the incomparability orthoset. The development connects properties of this orthogonality relation with small forbidden order patterns.

3 thms1 active userReviewed
🏆Completed
Captain: marwahaha

Exact Gallai–van der Waerden numbers: GW(r;3,4)=53GW(r;3,4)=53GW(r;3,4)=53 for 3≤r≤53 \le r \le 53≤r≤5Research Paper

An exact rrr-colouring of {1,…,n}\{1,\ldots,n\}{1,…,n} uses all rrr colours. A three-term arithmetic progression is rainbow if its three colours are distinct; a four-term progression is monochromatic if all its colours agree. Common differences are positive.

6 thms1 active userReviewed
🏆Completed
Number Theory·Captain: pitimespi

Behrend sets meeting every mmm-term progression in at most two pointsTextbook

A set of integers with no three terms in arithmetic progression is called a Salem–Spencer set. How large such a subset of {0,…,N−1}\{0,\dots,N-1\}{0,…,N−1} can be is one of the oldest questions in additive combinatorics, and the best lower bounds come from one construction, due to Behrend. This mission formalizes that construction in a stronger form: a single set with at…

12 thms1 active userReviewed
🏆Completed
Number Theory·Captain: marwahaha

Minimum coprime adjacencies in permutationsResearch Paper

Among all permutations of 1 through nnn, let h(n)h(n)h(n) be the smallest possible number of adjacent pairs with greatest common divisor 1. The goal proves the exact value for every n≥4n \ge 4n≥4.

3 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

Chandra–Furst–Lipton: forbidden patterns for zero-sum evaluationResearch Paper

In the number-on-the-forehead communication model, each player sees every input coordinate except their own. The players send bits according to a shared protocol. This Lean library studies what the resulting transcript can distinguish when the function being evaluated tests whether the inputs sum to zero in an additive commutative group.

4 thms1 active userReviewed
PreviousPage 27 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