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

Generalized Turán Problems for Even Cycles 5: The Maximum Number of (2l+1)-Cycles in a Graph with No Cycle of Length 3, …, 2l or 2k Is Ω(n^{1+1/(2k+1)}) and O(n^{1+l/(l+1)})Research Paper

An extremal graph question asks how many copies of one pattern can occur when other patterns are forbidden. When the counted pattern is a cycle, the answer depends strongly on which shorter cycles may occur. Excluding only an even cycle and excluding all cycles up to a given length are different constraints. The latter imposes a girth condition, meaning…

9 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 1: A C_{2k}-Free Graph on n Vertices Has at Most (1+o(1))(k−1)(k−2)n²/4 Four-Cycles, and This Is AttainedResearch Paper

The Turán problem asks for ex(n,F)\mathrm{ex}(n,F)ex(n,F), the largest number of edges in an nnn-vertex graph with no copy of a fixed graph FFF. For even cycles the answer is still not known in general: Bondy and Simonovits proved ex(n,C2k)=O(n1+1/k)\mathrm{ex}(n,C_{2k})=O(n^{1+1/k})ex(n,C2k​)=O(n1+1/k) in 1974, and the order of magnitude is known to be sharp only for k=2,3,5k=2,3,5k=2,3,5.

9 thms1 active userReviewed
Graph TheoryGroup Theory·Captain: mikedeng1

Edge-Transitive Bi-Cayley Graphs 3: Every Connected Semisymmetric Bi-Dihedrant Has Valency at Least 6, and Semisymmetric Bi-Dihedrants of Valency 2k Exist for Each Odd k ≥ 3Research Paper

A graph may have enough symmetry for every edge to look the same while its vertices still fall into two distinct classes. Such a graph is semisymmetric when it has constant valency, is edge-transitive, and is not vertex-transitive. Conder, Zhou, Feng and Zhang study this phenomenon among bi-Cayley graphs, graphs equipped with a group acting freely on two…

9 thms1 active userReviewed
Graph TheoryGroup Theory·Captain: mikedeng1

Edge-Transitive Bi-Cayley Graphs 1: For Connected BiCay(H, ∅, ∅, S), the Normaliser of R(H) Is 2-Arc-Transitive Iff Three Conditions on Aut(H) Hold, and Never 3-Arc-TransitiveResearch Paper

A graph is symmetric when its automorphism group moves any vertex, edge or arc to any other, and sss-arc-transitive when it moves any walk of length sss without immediate backtracking to any other. Tutte's work on cubic graphs made sss-arc-transitivity a central measure of symmetry in algebraic graph theory, and most constructions of highly symmetric graphs start…

6 thms1 active userReviewed
Graph TheoryGroup Theory·Captain: mikedeng1

Edge-Transitive Bi-Cayley Graphs 2: Edge-Transitive Bi-Cayley Graphs over Abelian Groups Are Vertex-Transitive, and Half-Arc-Transitive Ones Have Valency at Least 6Research Paper

A Cayley graph turns multiplication in a group into adjacency between vertices. Every Cayley graph is vertex transitive: multiplying every vertex by the same group element moves any chosen vertex to any other. A bi-Cayley graph starts with two copies of a group and permits edges both within and between the copies. Its built-in group action is transitive on…

7 thms1 active userReviewed
Discrete Geometry·Captain: mikedeng1

Many Non-Equivalent Realizations of the Associahedron 2: Two Hohlweg–Lange Associahedra Are Normally Isomorphic iff Their Sign Sequences Agree up to Reflection and ReversalResearch Paper

The associahedron Assn\mathrm{Ass}_nAssn​ is the nnn-dimensional simple polytope whose faces correspond to the sets of pairwise non-crossing diagonals of a convex (n+3)(n+3)(n+3)-gon, ordered by reverse inclusion: its vertices are the triangulations of the polygon and its facets are the diagonals. It appears in homotopy theory (Stasheff), in the theory of cluster algebras of…

11 thms1 active userReviewed
🏆Completed
Graph Theory·Captain: wurtle

A counterexample to Ryser's covering conjectureResearch Paper

A vertex cover of a hypergraph HHH is a set of vertices meeting every edge; the covering number τ(H)\tau(H)τ(H) is the minimum size of a cover, and the matching number ν(H)\nu(H)ν(H) is the maximum number of pairwise disjoint edges. In an rrr-partite rrr-uniform hypergraph the vertices are split into rrr parts and every edge contains exactly one vertex from each part. Ryser's…

6 thms1 active userReviewed
Graph TheoryStatistics·Captain: mikedeng1

Random Graphs with a Given Degree Sequence 2: The Closure of the β-Model Expected Degree Sequences Equals the Convex Hull of All Degree SequencesResearch Paper

A degree sequence records how many neighbours each vertex of a graph has. In network statistics it is often the only summary of a graph that is observed or trusted, and the natural probability models for graphs in which "the degree sequence captures the information" are exponential families whose sufficient statistic is the degree sequence. Chatterjee,…

10 thms1 active userReviewed
🏆Completed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: sattath

A Quantum Lovász Local Lemma (Ambainis, Kempe, Sattath)Research Paper

Status: complete. This mission records a finished formalization rather than an open call for work. Every statement below, including the goal, was uploaded together with a proof that the platform has verified, so there is nothing left to prove.

1 thm1 active userReviewed
Graph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition IV: Mutually Distinguishable Tangles Have a Tree-Decomposition Separating Them by Their DistinctionsResearch Paper

Robertson and Seymour introduced tangles in Graph Minors. X (J. Combin. Theory Ser. B 52 (1991) 153–190) as the precise obstruction to tree-decompositions of small width: a graph has a tangle of large order exactly when it has no tree-decomposition of small width. A tangle points to a highly connected region of a graph without naming its vertices, by…

13 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition III: In the θ-Grid, the Separations of Order < θ With Small E(A) Form a Tangle of Order θResearch Paper

Robertson and Seymour introduced tangles as a way to describe a region of a graph that cannot be isolated by a separation of low order. A separation divides the edges into two sides, and its order counts the vertices shared by those sides. A tangle makes a consistent choice of the side regarded as small at every order below a threshold. This turns an…

9 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition V: A θ-Pervasive Class of Designs Gives a Tree-Decomposition over 𝒮^{3θ−2} ∪ ℛ_{4θ−3}Research Paper

Tangles were introduced by Robertson and Seymour in Graph Minors. X (JCTB 1991) to make precise the idea of a "highly connected region" of a graph. A tangle orients every low-order separation of the graph towards one side, consistently. They are the organising notion of the later papers of the Graph Minors series, which culminate in the graph structure…

7 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition II: Branch-Width and Tree-Width Satisfy max(β, γ) ≤ ω + 1 ≤ max(⌊3β/2⌋, γ, 1)Research Paper

Tree-width measures how closely a graph resembles a tree. It is the central width parameter of the Graph Minors series of N. Robertson and P. D. Seymour, which proves that finite graphs are well-quasi-ordered by the minor relation, and it governs the complexity of many algorithms: problems that are NP-hard in general become solvable in linear time on graphs…

10 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

APSP in O(n^2.9983) via All-Edges Exact TriangleResearch Paper

All-pairs shortest paths (APSP) computes the shortest distance between every pair of vertices in a weighted graph.

49 thms1 active userReviewed
Discrete GeometryGraph Theory·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 1: The Base Abstraction in Dimension n/4 with n Facets Has Diameter Ω(n²/log n)Research Paper

Whether the diameter of a polyhedron is bounded by a polynomial in its number of facets is one of the central open questions of convex geometry, and it bears directly on linear programming: the diameter of the graph of a polyhedron is a lower bound on the number of pivots of any simplex method that moves along edges. Write △u(d,n)\triangle_u(d,n)△u​(d,n) for the largest…

2 thms1 active userReviewed
🏆Completed
Information Theory·Captain: shivm

Periodic Multidimensional Costas Arrays (Rubio–Torres Conjecture 1)Open Problem

A Costas array is a permutation matrix in which the difference vectors between distinct dots are pairwise distinct; such arrays are frequency-hopping patterns for sonar and radar (Costas, 1984). Rubio and Torres ask whether their mmm-dimensional version can stay Costas in every window of its periodic extension, and conjecture that this happens only in the…

2 thms1 active userReviewed
🏆Completed
Captain: mysticflounder

Six-colour Schur colourings of [1, 1801] under R₄(3) ≤ 61: balanced classes, nested saturation and forced reflectionResearch Paper

The Schur number S(n)S(n)S(n) is the largest NNN such that [1,N]={1,…,N}[1, N] = \{1, \dots, N\}[1,N]={1,…,N} can be partitioned into nnn sumfree sets, sets with no x,y,zx, y, zx,y,z such that x+y=zx + y = zx+y=z (x=yx = yx=y allowed). Schur's argument gives S(n)≤Rn(3)−2S(n) \le R_n(3) - 2S(n)≤Rn​(3)−2, where the triangle Ramsey number Rn(3)R_n(3)Rn​(3) is the least NNN such that every colouring of the edges of KNK_NKN​ with nnn colours has a monochromatic…

15 thms1 active userReviewed
Graph Theory·Captain: Minghui

Formalize the Four Color Theorem in Lean 4Research Paper

The Four Color Theorem links a short mathematical statement to a large collection of finite checks. For contributors to graph theory and proof assistants, it is a concrete test of whether abstract mathematics, executable verification, and a public theorem statement can share one auditable foundation. The proposed result is a complete Lean 4 formalization,…

54 thms1 active userReviewed
Operations ResearchOptimization·Captain: mikedeng1

Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows: Some Optimal Solution Traverses Each Pair of Reverse Customer Arcs at Most OnceResearch Paper

Vehicle routing problems ask for minimum-cost vehicle routes that deliver goods from a depot to a set of customers. In the split-delivery vehicle routing problem with time windows (SDVRPTW) a customer's demand may be served by several vehicles, and each customer must be visited inside a prescribed time window. Allowing split deliveries matters in practice:…

6 thms1 active userReviewed
🏆Completed
Captain: mysticflounder

Eliahou–Revuelta Schur degree: L(4) = 16 and 49 ≤ L(5) ≤ 65Research Paper

A set of integers is sumfree when no two of its elements, equal or distinct, add up to an element of the set. The Schur number S(n)S(n)S(n) is the largest NNN such that {1,…,N}\{1, \dots, N\}{1,…,N} can be partitioned into nnn sumfree sets; only S(1),…,S(5)=1,4,13,44,160S(1), \dots, S(5) = 1, 4, 13, 44, 160S(1),…,S(5)=1,4,13,44,160 are known. For n≥4n \ge 4n≥4 the best theoretical upper bound that Eliahou and Revuelta could cite in 2021…

16 thms1 active userReviewed
🏆Completed
Mathematical Physics·Captain: ShapeZero

Every seven-point Steiner triple system is the Fano plane — so the role postulates force the Fano planeTextbook

The Shape Zero model reaches the Fano plane — the seven-point, seven-line configuration behind the seven imaginary units of the octonions — by a combinatorial route: C1 Formal Proofs, §3, Theorem 3.6 ("Roles Force Fano") states that any Steiner triple system admitting a role colouring is the Fano plane. Its proof derives only that there are 777 points, and…

10 thms1 active userReviewed
Dynamical SystemsFormal Verification·Captain: Rizwan G Mir

Bound L4: 33,070,982 <= R Reversible Binary 2D Moore RulesOpen Problem

This mission formalizes the lower bound 33,070,982≤R33,070,982 \le R33,070,982≤R on the number of reversible binary cellular automata on the 3×33 \times 33×3 Moore neighborhood. Extending the conserved-landscape marker families to both centered and off-centered rules.

1 thm1 active userReviewed
🏆Completed
Formal Verification·Captain: Rizwan G Mir

Reversible Binary 2D Cellular Automata: Disproof of R = 18 and Lower Bound R >= 33,076,358Open Problem

A two-dimensional binary cellular automaton (CA) on the infinite grid Z2\mathbb{Z}^2Z2 with the standard 3×33 \times 33×3 Moore neighborhood M={−1,0,1}2M = \{-1,0,1\}^2M={−1,0,1}2 updates configurations c:Z2→{0,1}c : \mathbb{Z}^2 \to \{0,1\}c:Z2→{0,1} via a local rule f:{0,1}M→{0,1}f : \{0,1\}^M \to \{0,1\}f:{0,1}M→{0,1} according to:

7 thms1 active userReviewed
🏆Completed
Number Theory·Captain: moutei

Erdős #131: the ELRSS bound F(N) < 3·sqrt(N) + 1 (the open problem itself is NOT settled)Open Problem

What this mission proves, and what it does not. The goal theorem is the explicit upper bound F(N)<3N+1F(N)<3\sqrt N+1F(N)<3N​+1 of Erdős, Lev, Rauzy, Sándor and Sárközy (1999) — a published result, now formally verified here. Erdős problem #131 itself is NOT solved by this mission. Erdős asked for the order of growth of F(N)F(N)F(N), which is known only to lie between N1/5N^{1/5}N1/5 and …

16 thms1 active userReviewed
🏆Completed
Number Theory·Captain: mysticflounder

Modular Schur numbers: a uniform closed form in the stable-colour regimeResearch Paper

A set of integers is sum-free when no two of its members add up to a third. Schur's theorem (1916) says that for every kkk there is a largest interval [1,N][1,N][1,N] that can be split into kkk sum-free classes, and the resulting Schur numbers S(k)S(k)S(k) are notoriously hard to compute: S(5)=160S(5) = 160S(5)=160 was settled only in 2018, by a SAT computation with a machine-checked proof…

19 thms1 active userReviewed
PreviousPage 49 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