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
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Catalan Hashing: Efficient Linear Probing for Variable-Length ItemsResearch Paper

Linear probing stores each key in the first free cell at or after its hash position, so a query is a single forward scan over a contiguous region of memory. That locality is why linear probing is the default hash table in practice and in external memory, and its analysis goes back to Knuth's 1963 note and its many refinements (Knuth, The Art of Computer…

10 thms1 active userReviewed
Captain: parclytaxel

The Ahlswede–Khachatrian theoremResearch Paper

Define an (n,k,t)-intersecting family as a set of kkk-subsets of {1,…,n}\{1,\dots,n\}{1,…,n} such that every two sets intersect in at least t elements.

4 thms1 active userReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: mikedeng1

Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNFResearch Paper

WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…

28 thms1 active userReviewed
Information TheoryProbability·Captain: mikedeng1

A Universal Threshold Theory for Local Properties of Random Linear CodesResearch Paper

A linear code stores messages as vectors in a finite-dimensional vector space. Its dimension controls how many messages it can represent, while its other properties determine what kinds of corruption or ambiguity it can tolerate. Researchers studying random codes therefore ask at which dimensions a given property becomes likely. For many properties, a small…

5 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

Random Deletion for Circuits in Regular MatroidsResearch Paper

Karger's random contraction algorithm ([Kar93], [Kar95]) showed that a graph with minimum cut weight λ\lambdaλ has at most n2αn^{2\alpha}n2α cuts of weight at most αλ\alpha\lambdaαλ. Through matroid duality, cuts of a graph are the circuits of its cographic matroid and cycles are the circuits of its graphic matroid, and Subramanian ([Sub95]) proved the analogous bound …

25 thms1 active userReviewed
Computational GeometryGraph TheoryTheoretical Computer Science·Captain: iris

Parameterized Tractability of Euclidean k-Steiner TreeResearch Paper

A Steiner tree connects a set of terminals by a network of minimum total length, possibly through auxiliary Steiner points. In the discrete Euclidean variant the Steiner points must be chosen from a finite candidate set given in the input, and in the kkk-Steiner variant at most kkk of them may be used, while the number of terminals is unrestricted. Exact…

32 thms1 active userReviewed
Graph TheoryMathematical LogicTheoretical Computer Science·Captain: Shuze Chen

Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler–Leman and Hypertree WidthResearch Paper

The Weisfeiler–Leman (WL) family of colour-refinement algorithms is the standard heuristic for graph isomorphism and the yardstick for the expressive power of graph neural networks. Its distinguishing power has an exact algebraic description: by Lovász's theorem two graphs are isomorphic iff every graph has the same number of homomorphisms into both, and…

22 thms1 active userReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Random-Walk Cuckoo Hashing is Efficient up to the Critical Load ThresholdResearch Paper

Cuckoo hashing stores keys in a table so that every key sits in one of a few cells determined by its hashes, which makes lookups take constant worst-case time. With ddd hashes per key, the table can be filled almost completely: Fountoulakis and Panagiotou (FP12) identified the exact load threshold 1−εd∗1-\varepsilon^*_d1−εd∗​ up to which all keys can be placed with high…

20 thms1 active userReviewed
Machine LearningStatisticsTheoretical Computer Science·Captain: Shuze Chen

PAC Learning with Multiple Correct AnswersResearch Paper

In many prediction tasks an input has more than one acceptable answer: a sentence has several valid translations, a scheduling instance several optimal schedules, an image several correct tags. Training data, however, often shows only one correct answer per input: a demonstration. Hanneke, Mansouri, Pour, Shaeiri and Wang (arXiv:2611.05133) ask exactly when…

23 thms1 active userReviewed
Algorithmic Game TheoryOptimizationProbability·Captain: mikedeng1

Single-Sample Prophet Inequalities: A Combinatorial to Single-Item ReductionResearch Paper

In an online allocation problem, buyers arrive one at a time and each must be served irrevocably on arrival; the benchmark is the prophet, who sees all valuations in advance and allocates optimally. When the valuations are random with known distributions, guarantees of this kind are prophet inequalities. A much weaker information model gives the algorithm…

39 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Constant-Time Range Counting for Pattern-Avoiding Permutations and Entry Access to Twin-Ordered MatricesResearch Paper

Given a permutation τ\tauτ of [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, a dominance query (x,y)(x,y)(x,y) asks how many of the first xxx values of τ\tauτ are at most yyy. Together with rectangle queries (four dominance counts by inclusion–exclusion), it is the basic primitive of two-dimensional orthogonal range counting in rank space, and it underlies succinct text indexes and compressed matrix…

21 thms1 active userReviewed
Information Theory·Captain: mikedeng1

Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert–Varshamov BoundResearch Paper

A stored or transmitted bit string can lose symbols, gain symbols, or change their order. Such synchronization errors disrupt the alignment between the original and received strings. A decoder therefore has to identify the original message while also resolving where its symbols moved. The paper studies a fixed number of errors as the block length grows,…

23 thms1 active userReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: Shuze Chen

Existence of the Core in Approval-Based Committee ElectionsResearch Paper

In an approval-based committee election, each of nnn voters reports the set of candidates she approves, and a committee of kkk candidates must be chosen. Proportional representation asks that every group of voters large enough to "deserve" some seats, and united enough to agree on candidates, gets them. The strongest standard axiom of this kind is the core: no…

17 thms1 active userReviewed
Discrete GeometryProbabilityTheoretical Computer Science·Captain: iris

Replicable Mean Estimation via Random Lattice RoundingResearch Paper

A randomized algorithm is ρ-replicable if two runs on independent samples, sharing their random seed, return the same output with probability at least 1−ρ1-\rho1−ρ (Impagliazzo–Lei–Pitassi–Sorrell 2022). Many replicable algorithms (PAC learning, bandits, hypothesis testing) reduce to replicable mean estimation in Rd\mathbb R^dRd. Hopkins, Impagliazzo, Kane, Liu and…

23 thms1 active userReviewed
Complexity TheorycryptographyTheoretical Computer Science·Captain: iris

Towards Asymptotically Optimal Pseudorandom Functions: Linear-Size Circuits with Exponentially Small BiasResearch Paper

A keyed function family FK:{0,1}n→{0,1}nF_K:\{0,1\}^n\to\{0,1\}^nFK​:{0,1}n→{0,1}n is the basic object of symmetric cryptography. Two goals pull against each other: the function should be cheap to evaluate, ideally by a circuit of size O(n)O(n)O(n), and it should resist attacks running in time 2Ω(n)2^{\Omega(n)}2Ω(n). Whether both are possible at once is open in general. Dinur and Ishai settle the half that…

27 thms1 active userReviewed
Graph TheoryProbability·Captain: Shuze Chen

Fractional colorings of KrK_rKr​-free graphs with local demandsResearch Paper

Lower bounds on the independence number in terms of degrees are among the oldest themes of extremal graph theory. For triangle-free graphs, Ajtai, Komlós and Szemerédi proved α(G)=Ω(nlog⁡d/d)\alpha(G)=\Omega(n\log d/d)α(G)=Ω(nlogd/d) for average degree ddd, and Shearer sharpened this to α(G)≥nf(d)\alpha(G)\ge n f(d)α(G)≥nf(d) with the explicit function f(d)=(dlog⁡d−d+1)/(d−1)2f(d)=(d\log d-d+1)/(d-1)^2f(d)=(dlogd−d+1)/(d−1)2 (Shearer 1983), later to the…

29 thms1 active userReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: Shuze Chen

Precedence-Constrained Decision Trees and CoveringsResearch Paper

In the Optimal Decision Tree problem an unknown target hypothesis h∗h^*h∗ from a finite set HHH of nnn hypotheses must be identified by adaptively performing tests from a family TTT of mmm tests; each test partitions HHH and its reply reveals the block that contains h∗h^*h∗. The problem goes back to Garey and Graham (1974) and appears in medical diagnosis, troubleshooting…

23 thms1 active userReviewed
AnalysisProbabilityTheoretical Computer Science·Captain: Shuze Chen

Inside the Critical Window of Random 2-SATResearch Paper

Random 2-SAT is the one case of random kkk-SAT whose satisfiability threshold and scaling window are both known. With nnn Boolean variables and mmm random 2-clauses, a formula is satisfiable with probability tending to one when m/n<1m/n<1m/n<1 and unsatisfiable with probability tending to one when m/n>1m/n>1m/n>1, a result proved independently by Chvátal and Reed (FOCS 1992), Goerdt…

22 thms1 active userReviewed
Graph TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Better Bounds for Semi-Streaming Maximum Matching via Load BalancingResearch Paper

Graphs too large to store are often processed as a stream: the edges arrive one at a time, in an order nobody controls, and an algorithm may read the stream a few times (passes) while keeping only a small summary in memory. The semi-streaming model of Feigenbaum, Kannan, McGregor, Suri and Zhang (FKM+05) allows O~(n)=O(n⋅polylog n)\tilde O(n)=O(n\cdot\mathrm{polylog}\,n)O~(n)=O(n⋅polylogn) bits…

24 thms1 active userReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

Optimal Online Stochastic MatchingResearch Paper

In online bipartite matching, mmm offline vertices are known in advance and online vertices arrive one at a time, each revealing its neighbourhood; every arrival must be rejected or irrevocably matched to an unmatched neighbour, and the goal is a large matching. Under adversarial arrivals the Ranking algorithm of Karp, Vazirani and Vazirani is optimal with…

27 thms1 active userReviewed
Complexity TheoryHarmonic AnalysisProbability+1·Captain: Shuze Chen

Low Soundness Linearity Testing on Subsets of the HypercubeResearch Paper

A linearity test reads a function f:F2n→F2f:\mathbb F_2^n\to\mathbb F_2f:F2n​→F2​ at a few random points and accepts or rejects. It is perfectly complete if it always accepts linear functions. It has low soundness if, whenever it accepts with probability at least (1+δ)/2(1+\delta)/2(1+δ)/2, fff agrees with an affine function on at least a (1+s(δ))/2(1+s(\delta))/2(1+s(δ))/2 fraction of inputs, with s(δ)>0s(\delta)>0s(δ)>0…

22 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Finding Hypercliques Faster Than Brute ForceResearch Paper

A hypergraph is a collection of subsets of a vertex set, called edges. In a (k−1)(k-1)(k−1)-uniform hypergraph, every edge contains exactly k−1k-1k−1 vertices. A kkk-hyperclique consists of kkk vertices for which every (k−1)(k-1)(k−1)-subset is an edge. Checking each possible selection gives a running time of order nkn^knk. The algebraic question behind this mission asks whether the…

19 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Small classes have linear neighbourhood complexityResearch Paper

A graph class can be studied by counting how many of its graphs exist on a fixed set of labels. It can also be studied by counting the different adjacency patterns visible on a chosen vertex set inside one graph. These are different measurements: the first concerns a collection of whole graphs, while the second concerns local observations within an…

21 thms1 active userReviewed
Graph Theory·Captain: Shuze Chen

Byzantine Partition Detection Under ChurnResearch Paper

Byzantine fault-tolerant protocols are proved correct under two separate assumptions: a bound ttt on the number of faulty processes, and enough vertex connectivity in the communication network (classically, connectivity above a multiple of ttt). The second assumption is usually taken for granted. Sengupta and Perrin ask whether the participants themselves can…

25 thms1 active userReviewed
Linear algebraTheoretical Computer Science·Captain: iris

A Fast Algorithm for Subspace ConvolutionResearch Paper

Subset summation asks, given a value f(A)f(A)f(A) for every subset A⊆[n]A\subseteq[n]A⊆[n], for all sums (Zf)(B)=∑A⊆Bf(A)(Zf)(B)=\sum_{A\subseteq B}f(A)(Zf)(B)=∑A⊆B​f(A). The fast zeta transform does this in O(n2n)O(n2^n)O(n2n) additions, and with its inverse, the Möbius transform, it underlies the fastest known algorithms for chromatic number, Hamiltonian path and covering products (Björklund–Husfeldt–Koivisto 2009; Bj…

33 thms1 active userReviewed
PreviousPage 18 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