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
Complexity TheoryTheoretical Computer Science·Captain: iris

Randomness-Efficient Robust Locally Testable Codes in the Low-Acceptance Regime from HDXsResearch Paper

A locally testable code (LTC) is an error-correcting code C⊆ΣnC\subseteq\Sigma^nC⊆Σn with a randomized test that reads few coordinates of a word fff and rejects with probability that grows with the distance of fff from CCC. LTCs are a core ingredient of probabilistically checkable proofs and of property testing. The usual guarantee is in the high-acceptance regime: if…

31 thms1 active userReviewed
Machine LearningTheoretical Computer Science·Captain: iris

Characterizing Local Breadth in Language GenerationResearch Paper

An algorithm sees an unknown language one string at a time and must produce new strings of that language. Language generation in the limit, introduced by Kleinberg and Mullainathan (2024), models this as a game. The target is any member of a countable candidate family, an adversary enumerates it, and the algorithm must eventually output only unseen strings…

37 thms1 active userReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Weighted Set Cover with Constant Worst-Case Recourse: From Exponential to Best-Known Update TimeResearch Paper

In fully dynamic weighted set cover, a fixed family of sets with positive costs is given once, and elements of the universe are then inserted into and deleted from an active set. After every update an algorithm must hold a subfamily that covers the active elements at nearly minimum cost. Besides the approximation ratio, two resources are measured per…

24 thms1 active userReviewed
ProbabilityStatistical Mechanics·Captain: iris

Spatial sorting and the geometry of lattice spin systems at fixed magnetizationResearch Paper

Programmable matter and self-organizing particle systems ask a population of simple agents with a fixed inventory to sort itself into regions by type. A standard way to analyse such algorithms is to model the configurations with a spin system and to run a Markov chain whose stationary law is its Gibbs distribution. Conservation of particles then becomes a…

104 thms1 active userReviewed
Captain: utkuokur

Ten Challenges 02: Excluded minors for GF(pm)\mathrm{GF}(p^m)GF(pm)-representable matroidsOpen Problem

A matroid records which subsets of a finite set are independent, in the way that sets of columns of a matrix are linearly independent or sets of edges of a graph are acyclic. The matroids that come from matrices over a field F\mathbb FF are the F\mathbb FF-representable matroids, and deciding which matroids are representable over a given finite field is one of…

6 thms1 active userReviewed
🏆Completed
Group Theory·Captain: chaos-ghost

Exact directed L/XL/XL/X diameter of the symmetric groupResearch Paper

A generating set determines more than which permutations can be expressed: it also determines the cost of expressing them. For a finite group, the largest shortest word length measures how far a generating set is from giving uniformly short representations. This question connects permutation groups with the distances of Cayley graphs. Here the generating…

8 thms1 active userReviewed
Discrete GeometryOperations Research·Captain: iris

Resistant Sets in the Unit Hypercube: Up to Isomorphism, Rk,1R_{k,1}Rk,1​ (k≥1k \ge 1k≥1) and R5R_5R5​ Are the Only Half-Dense Strictly Non-Polar Resistant SetsResearch Paper

A clutter is a family of subsets of a finite ground set none of which contains another. A clutter is ideal if its set covering polyhedron {x≥0:∑i∈Cxi≥1 for every member C}\{x\ge 0 : \sum_{i\in C}x_i\ge 1 \text{ for every member } C\}{x≥0:∑i∈C​xi​≥1 for every member C} has only integral vertices. It packs if the largest number of pairwise disjoint members equals the smallest number of elements meeting every member. Ideal…

35 thms1 active userReviewed
Discrete GeometryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) X: Every Rational Polytope Has Finite Chvátal RankTextbook

Integer programming asks for the best integral point of a polyhedron, and the standard way to attack it is to describe the convex hull of those integral points by linear inequalities. A simple rule produces such inequalities: if ccc is an integral vector and cTx≤dc^Tx\le dcTx≤d holds on a polyhedron PPP, then cTxc^TxcTx is an integer at every integral point of PPP, so …

21 thms1 active userReviewed
🏆Completed
Captain: FormallyCorrect

Analytic CombinatoricsTextbook

Philippe Flajolet and Robert Sedgewick's Analytic Combinatorics is the standard reference for counting discrete structures exactly and asymptotically. Its methods are used throughout the analysis of algorithms, random structures and enumerative combinatorics. This mission collects formally verified versions of the book's chapter-level results in one…

375 thms1 active userReviewed
Captain: Ethan Cheung Wang

Erdos 624Open Problem

Erdős Problem 624 (erdosproblems.com/624) is a problem of Erdős and Hajnal about how few elements of a set can be enough to "see" the whole set through a function on its subsets. For a finite set XXX with ∣X∣=n|X| = n∣X∣=n, let H(n)H(n)H(n) be the least mmm for which some map f:P(X)→Xf : \mathcal P(X) \to Xf:P(X)→X has the following property: for every Y⊆XY \subseteq XY⊆X with ∣Y∣≥m|Y| \ge m∣Y∣≥m,

120 thms1 active userReviewed
🏆Completed
Number Theory·Captain: FormallyCorrect

An Invitation to qqq-Series: Ramanujan's Partition IdentityTextbook

A partition of a nonnegative integer is a way to express it as a sum of positive integers, with the order of the summands ignored. For example, the partitions of 4 are 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. If p(n)p(n)p(n) denotes their number, then p(4)=5p(4)=5p(4)=5 and p(0)=1p(0)=1p(0)=1, with the empty partition counted once. Although this definition is elementary, the values of p(n)p(n)p(n) obey…

753 thms1 active userReviewed
Number Theory·Captain: Ethan Cheung Wang

Erdős #195: monotone 444-term APs in permutations of Z\mathbb{Z}ZOpen Problem

A permutation of Z\mathbb{Z}Z in the sense of Erdős and Graham is a one-sided arrangement a0,a1,a2,…a_0, a_1, a_2, \ldotsa0​,a1​,a2​,… in which every integer appears exactly once. Erdős Problem 195 (erdosproblems.com/195) asks for the largest kkk such that every such arrangement contains a monotone kkk-term arithmetic progression: indices i1<⋯<iki_1 < \cdots < i_ki1​<⋯<ik​ for which …

149 thms1 active userReviewed
AlgebraRepresentation Theory·Captain: mikedeng1

Rational Semistandard Tableaux and Character Formula for the Lie Superalgebra ĝl∞|∞: A Jacobi–Trudi Determinant Formula for the Characters of A/B-Semistandard TableauxResearch Paper

The Lie superalgebra gl^∞∣∞\widehat{\mathfrak{gl}}_{\infty|\infty}gl​∞∣∞​, a central extension of the Lie superalgebra of infinite matrices of finite support, appears in the representation theory of the W1+∞W_{1+\infty}W1+∞​ vertex algebra and in Howe-type dualities with gln\mathfrak{gl}_ngln​ (Kac–Radul; Cheng–Lam). Its irreducible quasi-finite highest weight modules of positive…

12 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Conditional Uniformity and Hawkes Processes: Given Its Size, a Hawkes Cluster's Compensator Points Are ρ Times the Order Statistics of a Uniform Random Parking Function Minus i.i.d. UniformsResearch Paper

Hawkes processes are point processes in which every event raises the rate of future events. They are used to model contagion in financial markets, earthquake aftershocks, the spread of posts on social networks and arrivals to service systems (Hawkes 1971; Hawkes and Oakes 1974). Hawkes and Oakes showed that a stationary Hawkes process is a Poisson stream of…

10 thms1 active userReviewed
Captain: @bwdaugherty

Zero-Core Theorem for Ramsey R(5,5)Research Paper

The Zero-Core Theorem establishes a fundamental structural property of Ramsey graph colorings: the obstruction preventing extension of the champion R(5,5) coloring from n=43 to n=44 is fully distributed across all constraints, with no individual bottleneck.

1 thm1 active userReviewed
🏆Completed
Captain: Yuxuan Xu

Angel-Devil: Complete Integer-Power ClassificationResearch Paper

The Angel problem asks whether bounded movement can overcome an adversary that destroys one square per turn on an infinite chessboard. It is a question about strategies for arbitrarily long play, rather than about finding a path through one fixed configuration. The Devil may act anywhere on the board, including far ahead of the Angel. The movement range…

6 thms1 active user
🏆Completed
Topology·Captain: username

Continuous graph homomorphisms for Zd\mathbb Z^dZd-actions: Theorem 1.4 and Proposition 7.1Research Paper

A graph homomorphism sends vertices of one graph to another while preserving adjacency. Requiring this map to be continuous makes graph coloring sensitive to topology: each color must occupy an open and closed region. For integer lattice actions, the resulting questions connect finite graph structure with continuous dynamics. The results considered here…

17 thms1 active userReviewed
Captain: @bwdaugherty

R(5,5) ≥ 43 via GF(p) Polynomial SeedingResearch Paper

The Ramsey number R(5,5) has remained open since the 1960s. The best known bounds are 43 ≤ R(5,5) ≤ 48, where the lower bound was first established by Exoo (1989) via computational search. This mission formalizes an independent verification using novel GF(p) polynomial seeding.

2 thms1 active userReviewed
Linear OptimizationOptimization·Captain: mikedeng1

The Running Intersection Relaxation of the Multilinear Polytope 3: Running Intersection Inequalities Meeting Three Support Conditions Define Facets of the Multilinear PolytopeResearch Paper

Binary polynomial optimization asks for the maximum of a polynomial over {0,1}n\{0,1\}^n{0,1}n. Linearizing each monomial ∏v∈ezv\prod_{v\in e}z_v∏v∈e​zv​ by a new variable zez_eze​ turns the problem into a linear program over the convex hull of a set of 0/1 points, the multilinear polytope of the hypergraph whose edges are the monomials. Global solvers such as BARON build polyhedral…

6 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Stability Results on the Circumference of a Graph 1: A 2-Connected Graph with More Than (⌊c/2⌋−1)(n−c) Edges Off a Longest Cycle of Length c ≥ 10 Lies in W_{n,⌊c/2⌋,c} or (c Odd) in X_{n,c} ∪ Y_{n,c}Research Paper

The circumference c(G)c(G)c(G) of a graph GGG is the length of a longest cycle. Extremal graph theory asks how many edges force a long cycle. The Erdős–Gallai theorem (1959) states that every nnn-vertex graph has at most c(G)(n−1)/2c(G)(n-1)/2c(G)(n−1)/2 edges. Bondy (1971) strengthened it by counting only the edges near a longest cycle: if CCC is a longest cycle of length ccc, the number of…

8 thms1 active userReviewed
Graph TheoryMathematical Physics·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 2: On Bipartite α-Expanders, the High-Fugacity Hard-Core Partition Function Reduces to Two Kotecký–Preiss Polymer ModelsResearch Paper

The hard-core model on a finite graph GGG at fugacity λ>0\lambda > 0λ>0 weights each independent set III of GGG by λ∣I∣\lambda^{|I|}λ∣I∣. Its normalizing constant, the independence polynomial ZG(λ)Z_G(\lambda)ZG​(λ), is a basic object of statistical physics (a lattice gas with hard-core exclusion) and of combinatorics (ZG(1)Z_G(1)ZG​(1) counts independent sets).

10 thms1 active userReviewed
Graph TheoryMathematical Physics·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 1: On α-Expanders of Maximum Degree Δ, the Low-Temperature Potts Partition Function Reduces to a Kotecký–Preiss Polymer ModelResearch Paper

The ferromagnetic Potts model assigns a larger weight to a coloring when more adjacent vertices have the same color. Computing its partition function is an approximate counting problem with connections to statistical physics and counting complexity. For three or more colors, Goldberg and Jerrum established #BIS-hardness of approximation on general graphs,…

7 thms1 active userReviewed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem: The Asymmetric Held–Karp Relaxation Has Integrality Gap at Most 319Research Paper

The asymmetric traveling salesman problem (ATSP) asks for a shortest closed walk through every vertex of a directed graph whose edge weights need not be symmetric. It models routing with one-way streets, scheduling with sequence-dependent setup times, and many other problems in which the cost of going from uuu to vvv differs from the cost of going back. Its…

13 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 3: The Maximum Number of Six-Cycles in a Bipartite C_8-Free Graph on n Vertices Is n³ + O(n^{5/2})Research Paper

The generalized Turán number ex(n,H,F)\mathrm{ex}(n,H,\mathcal F)ex(n,H,F) is the largest number of copies of a graph HHH in an nnn-vertex graph containing no member of a family F\mathcal FF. With H=K2H=K_2H=K2​ it is the classical Turán number; the systematic study of general HHH began with Alon and Shikhelman (2016), and cycles are its most studied case: Bollobás and Győri bounded …

16 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 4: For k > l and 2k ≠ ml, the Maximum Number of ml-Cycles in a Graph with No Cycle of Length 3, …, 2l−1 or 2k Is Θ(n^m)Research Paper

The Turán number ex(n,F)\mathrm{ex}(n,F)ex(n,F) is the largest number of edges in an nnn-vertex graph with no copy of FFF. Its generalized version, introduced systematically by Alon and Shikhelman (JCTB 2016), replaces edges by copies of a second graph HHH: ex(n,H,F)\mathrm{ex}(n,H,\mathcal F)ex(n,H,F) is the largest number of copies of HHH in an nnn-vertex graph containing no member of the family …

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