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
Complexity Theory·Captain: Abhishek Anand

Block Sensitivity vs. Sensitivity: Reach 2.127294Open Problem

Prove a separation exponent of 2.127294, building on Robin Kothari’s 2.075 construction and yousofy’s 2.105 proof with twelve nested predicates and sharper joint boundary bounds.

6 thms4 active usersReviewed
🏆Completed
Complexity Theory·Captain: Robin Kothari

Block Sensitivity vs. Sensitivity: Reach 2.10Open Problem

Sensitivity and block sensitivity measure two ways that a Boolean function can react to changes in its input. Both are basic measures in query complexity, where the input is accessed one coordinate at a time. Their relationship asks how much a function's response to changes involving several coordinates can exceed its response to individual coordinate…

5 thms4 active usersReviewed
🏆Completed
Complexity Theory·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Reach 2.007Open Problem

Establish the separation exponent α≥2.007\alpha\ge2.007α≥2.007 for total Boolean functions, improving on the depth-20 specialization of OpenAI's construction.

38 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Secretary Problems with Biased Evaluations Using Partial Ordinal Information I: ProxyLabel with a Width Estimate ω′ ≥ ω/c Is e^c(ω′+1)/(1−1/k)^{k−1}-CompetitiveResearch Paper

In the classical secretary problem, candidates arrive one at a time in uniformly random order, and a decision maker must accept or reject each one irrevocably. The decision maker sees exact scores, or at least a total ranking of the candidates seen so far. In hiring, admissions and procurement the observed scores are often biased: evaluations of candidates…

9 thms4 active usersReviewed
🏆Completed
Group TheoryNumber Theory·Captain: LG

Landau's Function: Growth of the Maximal Order of a PermutationResearch Paper

How large can the order of a single permutation of nnn objects be? The answer, Landau's function g(n)g(n)g(n), is a basic invariant of the symmetric group SnS_nSn​: it is the maximum number of times a permutation can be iterated before it returns to the identity. Because the order of a permutation is the least common multiple of its cycle lengths, g(n)g(n)g(n) is also the largest…

17 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature I: Swap-Local Optima of the Non-Oblivious Potential Are (1 − c/e)-Approximate for Submodular MaximizationResearch Paper

Maximizing a monotone submodular function over the bases of a matroid is the standard model for coverage, facility location, sensor placement and welfare maximization. The best possible approximation factor in the value-oracle model is 1−1/e1 - 1/e1−1/e (Nemhauser–Wolsey 1978; Călinescu–Chekuri–Pál–Vondrák 2011). Many functions met in practice are far from the worst…

9 thms4 active usersReviewed
🏆Completed
Algebraic TopologyLinear algebra·Captain: mikedeng1

Isoperimetric Inequalities in Simplicial Complexes 2: The Mixing Lemma — for Disjoint A_0,…,A_d in a Complex with a Complete Skeleton, ||F(A_0,…,A_d)| − α|A_0|⋯|A_d|/n| ≤ ρ_α(|A_0|⋯|A_d|)^(d/(d+1))Research Paper

For a kkk-regular graph G=(V,E)G=(V,E)G=(V,E) on nnn vertices, the Expander Mixing Lemma (Alon–Chung 1988; see the survey of Hoory, Linial and Wigderson 2006) says that for any vertex sets A,BA,BA,B, the number of edges between them is close to its expected value: ∣∣E(A,B)∣−k∣A∣∣B∣/n∣≤ρ∣A∣∣B∣\bigl||E(A,B)|-k|A||B|/n\bigr|\le\rho\sqrt{|A||B|}​∣E(A,B)∣−k∣A∣∣B∣/n​≤ρ∣A∣∣B∣​, where ρ\rhoρ is the largest absolute value of a nontrivial…

16 thms4 active usersReviewed
🏆Completed
Linear algebraMarkov ChainTheoretical Computer Science·Captain: mikedeng1

High Order Random Walks: Beyond Spectral Gap 2: On a Two-Sided λ-Local Spectral Expander, Spec(M⁺_k) ⊆ {1} ∪ ⋃_j [(k+1−j)/(k+2) ± √(k+1)·ε_k/(k+2)] and Eigenvectors Lie Near U^j_kResearch Paper

High-dimensional expanders are simplicial complexes whose local structure forces global mixing. Random walks on their kkk-dimensional faces, the high order random walks, are used to analyse sampling algorithms: the bases-exchange walk on the bases of a matroid is such a walk, and its spectral analysis by Anari, Liu, Oveis Gharan and Vinzant (arXiv:1811.01816)…

15 thms4 active usersReviewed
🏆Completed
Linear algebraMarkov ChainTheoretical Computer Science·Captain: mikedeng1

High Order Random Walks: Beyond Spectral Gap 1: On a One-Sided λ-Local Spectral Expander, ‖M⁺_k φ‖ ≤ ((k+1)/(k+2) + (k+1)λ/2)‖φ‖ for Every k-Cochain φ Orthogonal to the ConstantsResearch Paper

A high dimensional expander is a simplicial complex whose local structure forces global expansion. The high order random walks on such a complex move from a kkk-face to a kkk-face through a common (k+1)(k+1)(k+1)-face. They were studied for their connection to agreement tests in probabilistically checkable proofs (Dinur–Kaufman 2017; Kaufman–Mass 2017), and they later…

14 thms4 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Finding Cliques in Social Networks: A New Distribution-Free Model 1: Every Weakly c-Closed Graph on n Vertices Has at Most 3^((c−1)/3)·n² Maximal CliquesResearch Paper

Social networks exhibit triadic closure: two people with a common friend are more likely to be friends themselves than two people chosen at random, and the more common friends they have, the more likely they are to be connected. The principle goes back to sociology (Granovetter 1973) and is documented on large network data sets (see the Enron e-mail graph…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness III: With Additive Valuations, Donating the Pool to an Unenvied Agent Yields a 4/7-Groupwise-Maximin-Share AllocationResearch Paper

When indivisible goods are shared among people, comparing each person's bundle with another person's bundle is only one way to judge fairness. A second test asks whether a group could repartition the goods it collectively received so that one of its members would reliably obtain more. Groupwise maximin share (GMMS) makes this test for every subgroup. It…

9 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

A Little Charity Guarantees Almost Envy-Freeness I: Under Monotone Valuations an EFX Allocation Exists Whose Unenvied Pool Has Fewer Goods Than There Are Unenvied AgentsResearch Paper

Allocating indivisible goods fairly is difficult because a single good can change how an agent compares two bundles. Exact envy-freeness can be impossible (one good, two agents), so the field works with relaxations. Envy-freeness up to any good (EFX) requires each agent to prefer her own bundle to every other agent's bundle after any one good of that other…

8 thms4 active usersReviewed
🏆Completed
Discrete GeometryGraph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 2: Every Subgraph of a Unit d-Dimensional Ball Graph with Clique Number k Has Twin-width at Most (3⌈√d⌉)^d·kResearch Paper

Twin-width is a graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant in Twin-width I: Tractable FO Model Checking (J. ACM 69(1), Article 3, 2021; arXiv:2004.14789). Its main theorem says that first-order model checking is fixed-parameter tractable on every class of graphs of bounded twin-width, provided a witnessing contraction sequence is…

10 thms4 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 1: Every Graph with Boolean-width k Has Twin-width at Most 2^(k+1) − 1Research Paper

Twin-width was introduced by Bonnet, Kim, Thomassé and Watrigant (J. ACM 69(1), Article 3, 2021) as a graph parameter under which first-order model checking is fixed-parameter tractable when a contraction sequence is given. Its interest lies in the classes it covers at once: planar and, more generally, KtK_tKt​-minor-free graphs, bounded-degree grids, unit ball…

6 thms4 active usersReviewed
🏆Completed
Linear OptimizationOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport V: A Feasible Pair of Kantorovich Potentials Is Optimal or Strictly Improves Along a Direction (1_S, −1_S′)Textbook

The discrete optimal transport problem between two histograms is a linear program, and much of the algorithmic theory of optimal transport is the theory of solving that linear program well. Chapter 3 of Peyré and Cuturi's Computational Optimal Transport (Foundations and Trends in Machine Learning, 2019) surveys the classical combinatorial solvers: the…

9 thms4 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Turán Graphs with Bounded Matching Number 1: An n-Vertex Graph with Clique Number at Most k and Matching Number at Most s Has at Most max{t(2s+1,k), g(n,k,s)} Edges, and This Is AttainedResearch Paper

Two of the oldest results in extremal graph theory bound the number of edges of a graph under a single structural restriction. Turán's theorem (Turán 1941) determines the maximum number of edges t(n,k)t(n,k)t(n,k) of an nnn-vertex graph with no complete subgraph on k+1k+1k+1 vertices. The Erdős–Gallai theorem (Erdős and Gallai 1959) determines the maximum number of edges of an …

12 thms4 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 1: Folded Symmetric PCSPs Avoiding Parity, Majority and Alternating-Threshold Have Only C-Fixing PolymorphismsResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint, drawn from a fixed finite set of relations, holds. The algebraic approach to CSPs explains their complexity through polymorphisms, the operations that preserve all constraint relations; this programme culminated in the CSP dichotomy theorem of…

35 thms4 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 3: Pol(Γ) ⊆ Pol(Γ′) Implies Γ′ Is ppp-Definable from ΓResearch Paper

A constraint satisfaction problem (CSP) asks for an assignment of values from a finite domain DDD to variables so that every constraint, a tuple of variables required to lie in a fixed relation, is satisfied. The algebraic theory of CSPs rests on a Galois correspondence: the complexity of CSP(Γ)\mathrm{CSP}(\Gamma)CSP(Γ) is determined by the set Pol(Γ)\mathrm{Pol}(\Gamma)Pol(Γ) of…

8 thms4 active usersReviewed
🏆Completed
AlgebraDiscrete GeometryLinear algebra·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 1: An h-Scattered 𝔽_q-Subspace of V(r, qⁿ) Either Defines a Subgeometry or Has Dimension at Most rn/(h + 1)Research Paper

Let VVV be an rrr-dimensional vector space over the finite field Fqn\mathbb F_{q^n}Fqn​. Viewed over the subfield Fq\mathbb F_qFq​, VVV has dimension rnrnrn, and its one-dimensional Fqn\mathbb F_{q^n}Fqn​-subspaces form the Desarguesian spread. An Fq\mathbb F_qFq​-subspace UUU of VVV is scattered if it meets every element of this spread in an Fq\mathbb F_qFq​-subspace of dimension at most one.…

6 thms4 active usersReviewed
🏆Completed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 1: A Minion Homomorphism Pol(A₁, B₁) → Pol(A₂, B₂) Exists iff (A₂, B₂) Is pp-Constructible from (A₁, B₁)Research Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) is given by two finite relational structures with a homomorphism A→B\mathbf A\to\mathbf BA→B. An instance is a third structure I\mathbf II, and the task is to answer yes if I→A\mathbf I\to\mathbf AI→A and no if I↛B\mathbf I\not\to\mathbf BI→B; the promise is that one of the two holds. Approximate…

12 thms4 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Generation and Properties of Snarks 3: A Snark on 26 Vertices All of Whose 2-Factors Consist of Odd Cycles Refutes the Abreu–Labbate–Sheehan ConjectureResearch Paper

A cubic graph has chromatic index 3 or 4 (Vizing). Cubic graphs of chromatic index 4 — the uncolourable ones — are where most of the open problems on cubic graphs live: a minimal counterexample to the cycle double cover conjecture or to Tutte's 5-flow conjecture would be among them. Uncolourable graphs with small edge cuts or short cycles reduce to smaller…

12 thms4 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Generation and Properties of Snarks 2: A Cyclically 5-Edge-Connected Permutation Snark on 34 Vertices Refutes Zhang's Conjecture That Only the Petersen Graph Is OneResearch Paper

A snark is a cubic graph that cannot be properly edge-coloured with three colours and that does not reduce to a smaller such graph. Snarks are the smallest possible counterexamples to several central conjectures about cubic graphs, among them the cycle double cover conjecture, Tutte's 5-flow conjecture and the Berge–Fulkerson conjecture, so structural…

15 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Matroid Prophet Inequalities 1: Against Any Online Weight-Adaptive Adversary, the 2-Balanced Threshold Algorithm Earns at Least Half the Expected Max-Weight BasisResearch Paper

The prophet inequality of optimal stopping compares a gambler, who sees independent non-negative random values X1,…,XnX_1, \dots, X_nX1​,…,Xn​ one at a time and must accept or reject each on arrival, with a prophet who sees them all in advance. Krengel, Sucheston and Garling showed that the gambler can secure E[Xτ]≥12 E[max⁡iXi]\mathbb E[X_\tau] \ge \tfrac12\,\mathbb E[\max_i X_i]E[Xτ​]≥21​E[maxi​Xi​], and…

16 thms4 active usersReviewed
🏆Completed
Probability·Captain: marwahaha

A strict four-row permanent inequality and permutation momentsOpen Problem

An inequality involving only four rows can feed into a recursion for a much larger permutation shuffle. The source seeks an exponent strictly below two that survives a small perturbation of the uniform permutation law. The source is OpenAI's September 2026 manuscript.

14 thms4 active usersReviewed
🏆Completed
Discrete Geometry·Captain: marwahaha

A classification of finite Euclidean Ramsey configurationsOpen Problem

Euclidean Ramsey theory asks which finite shapes must occur monochromatically in a sufficiently high dimension. The scale is fixed, so an algebraic criterion must capture exact distances rather than approximate similarity. The source manuscript presents the surrounding research claim.

150 thms4 active usersReviewed
PreviousPage 4 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