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
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
Discrete Geometry·Captain: mysticflounder

Superlinear or exact bounds for planar distinct distancesOpen Problem

This mission asks how restrictions on collinear and cocircular points limit the reuse of distances in the plane. Its central question is Erdős Problem 98: must the minimum number of distances grow faster than the number of points?

141 thms2 active users
🏆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
Graph Theory·Captain: hao jia

Weak Pentagon Colorings of Triangle-Free Cubic Graphs (OPG-434)Open Problem

The weak pentagon problem asks for a five-label structure on the edges of every triangle-free cubic graph. Although its wording resembles proper edge coloring, properness is not part of the conjecture. Instead, each individual color class must meet enough odd cycles that deleting that class leaves a bipartite spanning graph. The problem connects odd-cycle…

4 thms2 active usersReviewed
Graph Theory·Captain: hao jia

Two Acyclic Colors for Planar Orientations (OPG-169)Open Problem

The dichromatic number of a digraph is the directed analogue of chromatic number: vertices of one color may be adjacent, but each color class must induce an acyclic digraph. The Two Color Conjecture asks whether every orientation of a planar graph has dichromatic number at most two. It is a natural directed-coloring counterpart to planar graph coloring,…

4 thms2 active usersReviewed
Graph Theory·Captain: hao jia

Monochromatic Reachability in Three-Colored Tournaments (OPG-1808)Open Problem

Edge-colored tournaments combine a complete orientation with a finite palette. They are a natural setting for comparing local multicolor obstructions with global directed reachability. The question attributed to Sands, Sauer, and Woodrow asks whether three colors force one of two outcomes: a directed triangle whose three arcs all have different colors, or a…

6 thms2 active usersReviewed
Graph Theory·Captain: hao jia

Circular (20,7)-Coloring of Triangle-Free Subcubic Planar Graphs (OPG-401)Open Problem

Circular coloring refines ordinary vertex coloring by placing colors on a cycle and measuring separation modulo the palette size. It records information that an ordinary chromatic-number bound can lose, and it interacts sharply with planarity, forbidden short cycles, and degree constraints. OPG-401 asks for a specific bound at the intersection of those…

3 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
🏆Completed
Algebra·Captain: marwahaha

Lisoněk–Salt conic lemmasResearch Paper

This mission collects the complete Lean development accompanying Vijaykumar Singh's work on the Lisoněk–Salt conjecture. Its goal is the finite-field conic nonvanishing used in Theorem 6.1. If ppp is prime, nnn is a nonsquare in Fp\mathbb{F}_pFp​, and (w2,w4)≠(0,0)(w_2,w_4)\ne (0,0)(w2​,w4​)=(0,0), then w42n−1−w22≠0w_4^2 n^{-1}-w_2^2\ne 0w42​n−1−w22​=0.

4 thms1 active userReviewed
🏆Completed
Captain: marwahaha

Forbidden Matrix Theory: Marcus–Tardos boundTextbook

The Marcus–Tardos theorem gives a linear upper bound on the number of ones in an n×nn\times nn×n binary matrix that avoids a fixed permutation pattern. In Yaël Dillies's Lean development, the goal ex_permPattern_le proves that for a permutation σ\sigmaσ on kkk symbols,

2 thms1 active userReviewed
Graph Theory·Captain: tiago duque marques

Diestel Graph Theory I: The Five Colour TheoremTextbook

Colouring the countries of a map so that neighbouring countries receive different colours is the oldest problem of graph theory that is still taught in every introductory course. Replacing each country by a point and each common border by an edge turns a map into a planar graph, and the question becomes how many colours a proper vertex colouring of a planar…

8 thms1 active userReviewed
Captain: parclytaxel

Existence of mutually orthogonal Latin squaresResearch Paper

A pair of Latin squares over the same nnn-symbol set are mutually orthogonal if, when superimposed, the pairs of symbols in each cell are distinct.

2 thms1 active userReviewed
🏆Completed
Group Theory·Captain: burkh4rt

Odd-ordered Cayley graphs satisfy Erdős–GyárfásResearch Paper

A finite simple graph has minimum degree at least three when every vertex has at least three neighbours. Erdős and Gyárfás asked whether every such graph contains a cycle whose length is a power of two, that is, a cycle of length 444, 888, 161616, and so on (Erdős Problem #64; Erdős recorded it in Discrete Math. (1997)). The affirmative statement, the Erdős–Gyárfás…

14 thms1 active userReviewed
PreviousPage 44 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