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
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Strong Algorithms for the Ordinal Matroid Secretary Problem: Every Algorithm with Forbidden Sets of Size k Is α(k) Probability-CompetitiveResearch Paper

The secretary problem asks an online decision maker to pick the best of nnn candidates who arrive in uniformly random order, deciding irrevocably on each one at arrival. Its matroid generalization, the matroid secretary problem (MSP) of Babaioff, Immorlica and Kleinberg (SODA 2007), asks the algorithm to select an independent set of a matroid whose elements…

8 thms3 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

Private Sequential Learning: The Query Complexity of an (ϵ, δ, L)-Private Learner Lies Between max{log(1/ϵ), log(δ/ϵ) + 2L − 4} and log(1/(Lϵ)) + 2LResearch Paper

A learner wants to locate an unknown number, the true value v∗∈[0,1)v^* \in [0,1)v∗∈[0,1), by asking threshold questions of a database: each query qqq is answered by the single bit I(v∗≥q)\mathbb I(v^* \ge q)I(v∗≥q). Bisection finds v∗v^*v∗ to within ϵ/2\epsilon/2ϵ/2 with ⌈log⁡2(1/ϵ)⌉\lceil \log_2(1/\epsilon) \rceil⌈log2​(1/ϵ)⌉ queries, and no strategy does better (Waeber, Frazier and Henderson, 2013). Bisection, however,…

15 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: marwahaha

Sands–Sauer–Woodrow: monochromatic paths in two-coloured tournamentsResearch Paper

A tournament is a directed graph in which every two distinct vertices are joined by exactly one arc — the model of a round-robin competition, and the setting of Ramsey theory's oldest questions.

6 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: Abhishek Anand

Block Sensitivity vs. Sensitivity: Reach 2.0635Open Problem

Establish a separation exponent of at least 2.06352.06352.0635 between block sensitivity and sensitivity of total Boolean functions.

5 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: @bwdaugherty

Block Sensitivity vs. Sensitivity: α ≥ 2.0391Open Problem

Improve the separation exponent between block sensitivity and sensitivity of total Boolean functions. This mission targets α≥2.0391\alpha\ge2.0391α≥2.0391; higher is better.

5 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: Leo Shaposhnik

Block Sensitivity vs. Sensitivity: Reach 2.0205Open Problem

For every ε>0\varepsilon>0ε>0 and every integer S≥2S\ge2S≥2, there exists a total Boolean function fff with s(f)≥Ss(f)\ge Ss(f)≥S and bs(f)≥s(f)2.0205−εbs(f)\ge s(f)^{2.0205-\varepsilon}bs(f)≥s(f)2.0205−ε.

15 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: marwahaha

Block Sensitivity vs. Sensitivity: OpenAI BaselineResearch Paper

Certify the separation exponent α≥2.000252407\alpha\ge2.000252407α≥2.000252407 using OpenAI's construction. Sensitivity s(f)s(f)s(f) counts individual bit flips that change the output; block sensitivity bs(f)bs(f)bs(f) counts disjoint sensitive blocks. Both are maximized over inputs. The notation bs(f,x)bs(f,x)bs(f,x) fixes one input, and 000 denotes the all-zero input.

40 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+2·Captain: mikedeng1

Linear Programming and Community Detection 5: The LP Relaxation Recovers the Planted Bisection w.h.p. in the Very Dense SBM When p − q > 1/2Research Paper

The stochastic block model (SBM), introduced by Holland, Laskey and Leinhardt (1983), is the standard random model for networks with community structure, and the basic benchmark for community-detection algorithms (Abbe 2018). In its two-community form the nodes are split into two equal halves, edges inside a half appear with probability ppp, and edges across…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue 1: Random Sampling Vickrey Is Ex-Post IC-IR and a 2(d+1)-Approximation to Welfare for d-SOS ValuationsResearch Paper

In an auction with interdependent values, a bidder's value can depend on information held by other bidders. An estimate of a shared resource's usefulness, for example, may improve when another participant reports a stronger signal. The auctioneer must decide whom to serve using reported signals, while each participant has an incentive to report a signal…

7 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Scaling Blockchains: Can Committee-Based Consensus Help? II: With a Single Voter, Voting for the k Candidates Most Likely to Be Honest Is OptimalResearch Paper

Many proof-of-stake blockchains do not let every token holder take part in consensus. Instead, token holders elect a small committee of block producers, and the committee runs a Byzantine agreement protocol. EOS, for instance, elects 21 producers by an up-to-30-vote approval ballot (paper, p. 9, citing EOS voting guide 2018). Byzantine agreement protocols…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Dynamic Matching: Characterizing and Achieving Constant Regret II: In (SPP)-Acyclic Networks the Static Planning Solution Is Given by Surplus Vectors in {−1, 0, 1}ⁿResearch Paper

Centralized markets such as kidney exchanges, ride-sharing platforms and online labor markets match agents who arrive over time. Kerimov, Ashlagi and Gurvich (SSRN 3824407; Management Science, 2023, doi:10.1287/mnsc.2021.01215) study such a market with nnn agent types and ddd feasible multi-way matches. Their main result is that, when a fluid linear program…

10 thms3 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

Offline Multi-Action Policy Learning: Generalization and Optimization 2: Depth-L Decision Trees Satisfy log N_H(ε,Π_L) ≤ (2^L−1)log p + 2^L log d + (2^L−1)log(L/ε+1)Research Paper

Offline policy learning chooses a treatment rule from logged data: given nnn observations of features XiX_iXi​, the action AiA_iAi​ taken and the reward obtained, pick a policy π:X→{1,…,d}\pi:\mathcal X\to\{1,\dots,d\}π:X→{1,…,d} from a class Π\PiΠ whose expected reward is close to the best in the class. Zhou, Athey and Wager (arXiv:1810.04778v2) bound the regret of their cross-fitted…

6 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Secretaries with Advice 3: A Closed Form for the Backward-Induction Dual Solution of the Secretary-with-Samples LPResearch Paper

In the secretary problem nnn candidates arrive one at a time in uniformly random order; at each arrival the decision maker sees only how the current candidate compares with the earlier ones and must accept or reject irrevocably, aiming to accept the best candidate overall. Dütting, Lattanzi, Paes Leme and Vassilvitskii, Secretaries with Advice (arXiv:2011.0672…

10 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Stall Economy: The Value of Mobility in Retail on Wheels I: The Magnet Rule Makes the Rendezvous Chain Doubly Stochastic, and Its Stationary Distribution Is Uniform on the Inner DiamondResearch Paper

A mobile retail stall can travel toward its next customer while that customer walks toward the stall. The customer's walking allowance changes where the stall stops, so it also changes the location from which the next trip begins. A useful trip-length calculation therefore needs a distribution for successive meeting points, not just a rule for one meeting.…

11 thms3 active usersReviewed
🏆Completed
Information Theory·Captain: chaikon

Essential Coding Theory I: Generalized Hamming BoundTextbook

An error-correcting code stores or transmits messages as words over a finite alphabet, adding redundancy so that the original word can be recovered after some symbols are corrupted. The basic question of coding theory is the trade-off between the amount of redundancy and the number of errors that can be corrected. The Hamming bound (also called the sphere-pa…

2 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes III: Bipartite, Unit-Patience Side: Rounding Then Probing by Weight Earns ≥ (1 − 1/e)·Σ w_e p_e y_eResearch Paper

Stochastic matching with patience models kidney exchange, online dating and labour platforms: every edge of a graph is present only with some probability, the only way to learn whether it is present is to probe it, and a probed edge that turns out to be present must be added to the matching. Each vertex vvv also has a patience tvt_vtv​, a limit on how many of its…

16 thms3 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

The Continuous-Time Joint Replenishment Problem: ϵ-Optimal Policies via Pairwise Alignment: Ψ-Pairwise Alignment Yields a Replenishment Policy Within Factor 1 + 5ϵ of Any PolicyResearch Paper

The joint replenishment problem is a basic model of coordinated inventory control. A firm stocks nnn commodities, each of which follows its own Economic Order Quantity (EOQ) model, but every order also incurs a joint ordering cost K0K_0K0​, regardless of which commodities it contains. Ordering commodities together therefore saves money, and the question is how to…

19 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Online Stochastic Matching: New Algorithms with Better Bounds 1: Every Random-Lists Algorithm Has ALG/OPT ≥ E[ALG]/E[OPT] − 2ε/(c+ε) with Probability at Least 1 − 2exp(−2nε²)Research Paper

Online bipartite matching with stochastic arrivals models the assignment of display-advertising impressions to advertisers: requests arrive one at a time, each must be assigned irrevocably on arrival or dropped, and the arrival sequence is random rather than adversarial. Since Feldman, Mehta, Mirrokni and Muthukrishnan beat the 1−1/e1 - 1/e1−1/e barrier in the i.i.d.…

5 thms3 active usersReviewed
AlgebraDiscrete Geometry·Captain: mikedeng1

A Large Family of Maximum Scattered Linear Sets of PG(1, q^n) and Their Associated MRD Codes 1: For q Odd, t ≥ 3, h ∉ 𝔽_{q^t} and h^(q^t+1) = −1, ψ_{h,t} Is Scattered over 𝔽_{q^{2t}}Research Paper

A linear set of a projective space over a finite field is the set of points spanned by the nonzero vectors of a subspace over a subfield. They have been used to construct and characterize semifields, rank-metric codes, translation spreads, translation ovoids, two-intersection sets and the blocking sets for which Lunardon introduced them (Polverino 2010;…

13 thms3 active usersReviewed
🏆Completed
Linear algebraOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature II: Column-Subset Selection Has Total Curvature at Most 1 − 1/κ(A)²Research Paper

The column-subset selection problem (CSSP) asks for kkk columns of a real matrix AAA whose span approximates all of AAA as well as possible in squared Frobenius norm. It is a basic primitive of low-rank approximation, feature selection and numerical linear algebra, studied both for its exact complexity and for approximation algorithms (see Boutsidis, Drineas and…

11 thms3 active usersReviewed
🏆Completed
Algebraic TopologyLinear algebra·Captain: mikedeng1

Isoperimetric Inequalities in Simplicial Complexes 1: For a Finite d-Complex with a Complete Skeleton, the Spectral Gap Is at Most the Cheeger Constant, λ(X) ≤ h(X)Research Paper

For a finite graph, the Cheeger constant measures how hard it is to cut the vertex set into two pieces, and the spectral gap of the graph Laplacian measures how fast random walks mix. The two Cheeger inequalities (Dodziuk 1984; Alon and Milman 1985; Alon 1986) bound each quantity by a function of the other, and they underlie the theory of expander graphs,…

10 thms3 active usersReviewed
🏆Completed
Discrete GeometryGraph Theory·Captain: mikedeng1

Triangle-Free Intersection Graphs of Line Segments with Large Chromatic Number: For Every k ≥ 1 There Is a Triangle-Free Family of Plane Line Segments with Chromatic Number Greater than kResearch Paper

A proper coloring of a graph assigns colors to its vertices so that adjacent vertices get different colors; the least number of colors that suffices is the chromatic number χ(G)\chi(G)χ(G). The clique number ω(G)\omega(G)ω(G) is the size of a largest set of pairwise adjacent vertices, and χ(G)≥ω(G)\chi(G)\ge\omega(G)χ(G)≥ω(G) always. A class of graphs is χ\chiχ-bounded if χ\chiχ is bounded by a…

8 thms3 active usersReviewed
🏆Completed
Linear algebraProbabilityRandom Matrix Theory·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities I: A Matrix Gaussian Series Satisfies v(Z) ≤ E‖Z‖² ≤ 2v(Z)(1 + log(d₁ + d₂))Textbook

Random matrices arise when observations, signs, or model coefficients fluctuate. Their spectral norm measures the largest amplification they can cause to a vector. A bound on that norm can turn entrywise randomness into a statement about the behavior of an entire linear operator. Tropp's chapter develops a common framework for Gaussian and Rademacher sums…

8 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 2: Positive Combinations Preserve the Balance Condition When Production and Consumption Sets Are DisjointResearch Paper

Stochastic models of chemical reaction networks in cell biology routinely combine species present in a handful of copies with species present in thousands, and rate constants that differ by orders of magnitude. Simulating such a system exactly is expensive, and model reduction replaces it with a lower-dimensional limit. A systematic approach, developed by Ba…

8 thms3 active usersReviewed
🏆Completed
ProbabilityStochastic Systems·Captain: mikedeng1

Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 3: The Second Time-Scale r₂ Is Strictly Slower than the First Time-Scale r₁Research Paper

Chemical reaction networks can contain reactions whose rates differ by powers of a large scaling parameter. A species may then change on one time scale while other combinations of species remain nearly fixed until a later one. This matters when replacing a detailed network by a smaller model: the quantities retained at the first scale need not be the…

5 thms3 active usersReviewed
PreviousPage 18 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