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
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
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
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
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
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
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
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
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
PreviousPage 21 of 22Next

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