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
Mathematical PhysicsProbability·Captain: wurtle

Critical strip-crossing mass on the honeycomb latticeResearch Paper

At its critical weight, a self-avoiding path on the honeycomb lattice can make long excursions without paying an exponential cost. A basic quantitative question is how much of its total weight reaches the far side of a strip of height NNN. Physics heuristics (Nienhuis's Coulomb gas and the conjectured SLE8/3\mathrm{SLE}_{8/3}SLE8/3​ scaling limit with boundary exponent 5/85/85/8…

14 thms2 active usersReviewed
🏆Completed
Mathematical LogicProbability·Captain: wurtle

Computing the Random 3-SAT ThresholdResearch Paper

Random 3-SAT, a conjunction of random three-literal clauses on nnn variables, is the classic test case for the typical behavior of satisfiability. Experiments placed the hardest instances near the density where half the formulas are satisfiable, and statistical physics predicts a sharp satisfiability threshold near 4.2674.2674.267. Once a limiting threshold α3\alpha_3α3​ is…

20 thms2 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: wurtle

Variance of the Random k-SAT Hitting TimeResearch Paper

Add random clauses one at a time to a Boolean formula on nnn variables until it first becomes unsatisfiable. The index HnH_nHn​ of that first failure is the satisfiability hitting time of random kkk-SAT. Its mean, divided by nnn, converges to the satisfiability threshold; its variance measures the width of the transition window. Friedgut's sharp-threshold theorem…

32 thms2 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: wurtle

A Limiting Satisfiability Threshold for Every Fixed Clause SizeResearch Paper

A random kkk-SAT formula on nnn Boolean variables is a conjunction of mmm independent random clauses, each an OR of kkk literals on distinct variables. As the clause density m/nm/nm/n grows, the formula changes from almost surely satisfiable to almost surely unsatisfiable. Random kkk-SAT is a central model in probabilistic combinatorics, the theory of algorithms and…

20 thms2 active usersReviewed
🏆Completed
Mathematical PhysicsProbability·Captain: wurtle

Brownian continuum random tree limits of finite Fortuin–Kasteleyn maps above fourResearch Paper

Random planar maps are graphs embedded in the sphere, chosen at random; they are the discrete models of two-dimensional quantum gravity. Decorating a map with a Fortuin–Kasteleyn (FK) random-cluster configuration with parameter qqq couples the geometry of the map to a statistical-mechanics model (percolation, Ising, Potts), and the coupling changes the…

4 thms2 active usersReviewed
🏆Completed
Group TheoryRepresentation Theory·Captain: wurtle

Universal Tensor Squares for Symmetric GroupsResearch Paper

The irreducible complex representations of the symmetric group SnS_nSn​ are indexed by partitions λ⊢n\lambda\vdash nλ⊢n and written SλS^\lambdaSλ (Specht modules). Decomposing a tensor product Sλ⊗SμS^\lambda\otimes S^\muSλ⊗Sμ (with the diagonal action) into irreducibles is governed by the Kronecker coefficients

53 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

Polynomial removal fails for ordered binary matricesResearch Paper

A removal lemma says that an object far from having a forbidden substructure must contain many copies of it. Such statements are the combinatorial backbone of property testing: if every matrix that is ϵ\epsilonϵ-far from avoiding a pattern HHH contains at least cHϵCHn2kc_H\epsilon^{C_H}n^{2k}cH​ϵCH​n2k copies of HHH, then sampling a number of rows and columns polynomial in …

2 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: wurtle

Cycle--clique Ramsey numbersResearch Paper

The Ramsey number R(H,J)R(H,J)R(H,J) is the least NNN such that every red–blue colouring of the edges of KNK_NKN​ contains a red copy of HHH or a blue copy of JJJ. For a cycle CmC_mCm​ against a clique KnK_nKn​ there is a simple lower-bound construction: take n−1n-1n−1 disjoint red cliques of order m−1m-1m−1 with all edges between them blue. It has (m−1)(n−1)(m-1)(n-1)(m−1)(n−1) vertices, no red CmC_mCm​ (each red component…

32 thms2 active usersReviewed
🏆Completed
Computational GeometryDiscrete Geometry·Captain: wurtle

A power saving for planar halving linesResearch Paper

Given nnn points in the plane with no three on a line, a halving line is a line through two of the points that leaves exactly half of the remaining points on each side. How many halving lines can an nnn-point set have? The question is the middle case of the kkk-set problem: count the kkk-element subsets that a line can cut off. It controls the complexity of levels…

4 thms2 active usersReviewed
🏆Completed
Harmonic AnalysisNumber Theory·Captain: wurtle

A power saving for square-difference-free setsResearch Paper

A set A⊆{1,…,N}A\subseteq\{1,\dots,N\}A⊆{1,…,N} is square-difference-free if no two of its elements differ by a perfect square m2m^2m2 with m≥1m\ge1m≥1. The Furstenberg–Sárközy theorem says such sets have density tending to zero; the question is how fast. Writing s(N)s(N)s(N) for the largest size of a square-difference-free subset of {1,…,N}\{1,\dots,N\}{1,…,N}, the problem is a prototype for polynomial…

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

A linear cycle-and-edge decomposition of every graphResearch Paper

How efficiently can the edges of a graph be split into cycles? Some single edges must be allowed, since a forest has no cycles at all, and a tree on nnn vertices already needs n−1n-1n−1 single-edge parts. The Erdős–Gallai cycle decomposition conjecture asserts that this is essentially the only obstruction: every graph on nnn vertices can have its edge set partitioned…

8 thms2 active usersReviewed
🏆Completed
Algebraic TopologyGroup Theory·Captain: wurtle

Bounded-degree coboundary expanders in every dimensionResearch Paper

An expander graph is a sparse graph in which every set of vertices has a large edge boundary relative to its size. Expanders with bounded degree are a basic tool across combinatorics, computer science and group theory. High-dimensional expanders are simplicial complexes that extend this behavior to faces of every dimension, and coboundary expansion over …

6 thms2 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: wurtle

The second Kahn–Kalai conjectureResearch Paper

When does the Erdős–Rényi random graph G(n,p)G(n,p)G(n,p) contain a copy of a prescribed graph HHH? A necessary condition is visible from first moments: if some subgraph F⊆HF\subseteq HF⊆H has expected copy count below a constant, then HHH is unlikely to appear. Kahn and Kalai conjectured in 2007 that this elementary obstruction determines the containment threshold up to a…

47 thms2 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: wurtle

A polynomial-time construction of strong thin treesResearch Paper

A thin spanning tree of a graph is a spanning tree that uses only a small fraction of the edges of every cut. Thin trees were introduced for the asymmetric traveling salesman problem: Asadpour, Goemans, Mądry, Oveis Gharan and Saberi showed that a thin tree of low cost can be augmented into a cheap tour, giving an O(log⁡n/log⁡log⁡n)O(\log n/\log\log n)O(logn/loglogn)-approximation (doi:10.1…

5 thms2 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: wurtle

The strong thin tree conjectureResearch Paper

A spanning tree keeps a graph connected with as few edges as possible. A spanning tree is thin if, in addition, it uses only a small fraction of the edges of every cut. Thin trees were introduced as a tool for the asymmetric traveling salesman problem (ATSP): Asadpour, Goemans, Mądry, Oveis Gharan and Saberi showed that thin trees, together with cost…

5 thms2 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: wurtle

Sharp logarithmic exponents for fixed off-diagonal Ramsey numbersResearch Paper

For integers s,t≥2s,t\ge2s,t≥2 the Ramsey number r(s,t)r(s,t)r(s,t) is the least NNN such that every simple graph on NNN vertices contains a clique of order sss or an independent set of order ttt. Ramsey's theorem guarantees these numbers are finite. In the off-diagonal regime, sss is fixed and t→∞t\to\inftyt→∞; the classical upper bounds give r(s,t)=Os ⁣(ts−1/(log⁡t)s−2)r(s,t)=O_s\!\left(t^{s-1}/(\log t)^{s-2}\right)r(s,t)=Os​(ts−1/(logt)s−2),…

8 thms2 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: wurtle

The sharp logarithmic exponent of r(5,t)Research Paper

For integers s,t≥2s,t\ge 2s,t≥2 the Ramsey number r(s,t)r(s,t)r(s,t) is the least nnn such that every simple graph on nnn vertices contains either a complete subgraph KsK_sKs​ or an independent set of ttt vertices. Determining how r(s,t)r(s,t)r(s,t) grows when sss is fixed and t→∞t\to\inftyt→∞ is one of the central problems of extremal and probabilistic combinatorics: upper bounds come from counting and local…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryRepresentation Theory·Captain: wurtle

Elementary positivity of chromatic quasisymmetric functionsResearch Paper

The chromatic symmetric function of a graph, introduced by Stanley, records all proper colorings of the graph with infinitely many colors as a symmetric function; it refines the chromatic polynomial. Whether it expands with nonnegative coefficients in the basis of elementary symmetric functions ("eee-positivity") is a central question in algebraic…

3 thms2 active usersReviewed
🏆Completed
AlgebraRepresentation Theory·Captain: wurtle

Combinatorial invariance of Kazhdan–Lusztig polynomialsResearch Paper

Kazhdan–Lusztig polynomials Pu,b(q)P_{u,b}(q)Pu,b​(q) are integer polynomials attached to pairs u≤bu\le bu≤b of elements of a Coxeter group. They were introduced through the canonical basis of the Hecke algebra (Kazhdan–Lusztig, 1979). For Weyl groups they compute local intersection cohomology of Schubert varieties, and they enter the Kazhdan–Lusztig conjectures on characters…

15 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: wurtle

A power saving for planar unit distancesResearch Paper

The unit-distance problem of Erdős asks how many pairs among nnn points in the plane can be at distance exactly one. By rescaling, this is the same as asking how often a single distance can repeat. It is one of the central extremal questions of combinatorial geometry and a benchmark for incidence methods. The bound u(n)=O(n4/3)u(n)=O(n^{4/3})u(n)=O(n4/3) of Spencer, Szemerédi and…

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

The weak pinned planar distance theoremResearch Paper

Erdős's distinct-distance problems ask how few different distances nnn points in the plane can determine. The global version, which counts all distances between all pairs, was essentially settled by Guth and Katz, who proved that every nnn-point planar set determines at least cn/log⁡ncn/\log ncn/logn distinct distances (Annals 2015), matching the square lattice up to a …

7 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: wurtle

Balanced counterexamples to Ryser's conjecture at prime ordersResearch Paper

A vertex cover of a hypergraph 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. An rrr-partite rrr-uniform hypergraph has rrr disjoint vertex parts, and every edge takes exactly one vertex from each part. Ryser's covering conjecture…

7 thms2 active usersReviewed
🏆Completed
Number Theory·Captain: wurtle

Quantitative Superexponential Bounds for van der Waerden NumbersResearch Paper

Van der Waerden's theorem (1927) says that for every number of colours rrr and every length kkk, every rrr-colouring of a long enough interval of integers contains a monochromatic arithmetic progression of length kkk. The van der Waerden number Wr(k)W_r(k)Wr​(k) is the least such interval length. Its upper bounds were for a long time not even primitive recursive (Shelah 1988…

2 thms2 active usersReviewed
🏆Completed
Algebraic TopologyDiscrete Geometry·Captain: wurtle

A nine-dimensional counterexample to Borsuk's covering assertionResearch Paper

In 1933 Borsuk asked whether every bounded set of positive diameter in Rd\mathbb R^dRd can be split into d+1d+1d+1 pieces of strictly smaller diameter. The answer is yes in dimensions d≤3d\le3d≤3 and for smooth convex bodies, and a regular simplex shows that d+1d+1d+1 pieces may be necessary. Kahn and Kalai showed in 1993 that the answer is no in high dimensions, and since then…

8 thms2 active usersReviewed
🏆Completed
Complexity Theory·Captain: wurtle

A superquadratic separation between sensitivity and block sensitivityResearch Paper

Sensitivity and block sensitivity are two of the basic complexity measures of a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1}. Sensitivity counts how many single-bit flips change the value; block sensitivity allows disjoint groups of bits to be flipped together. Block sensitivity is polynomially related to decision-tree complexity, certificate complexity, degree…

34 thms2 active usersReviewed
PreviousPage 21 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