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
Graph Theory·Captain: Shuze Chen

An approximate cactus-decomposition for vertex-connectivityResearch Paper

The cactus theorem of Dinitz, Karzanov and Lomonosov (1976) states that the minimum edge-cuts of a connected graph are represented by a cactus: a connected graph in which any two cycles share at most one vertex. That representation underlies algorithms for enumerating minimum cuts, connectivity augmentation and dynamic minimum cuts. For vertex-connectivity…

21 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Asymptotically Optimal Weighted Edge Colorings via Local Bin PackingResearch Paper

In weighted edge coloring each edge of a graph carries a weight in (0,1](0,1](0,1], and a coloring is feasible when, at every vertex, the edges of each color have total weight at most one. The problem generalizes ordinary edge coloring (all weights one) and bin packing (a star). Its principal application is multirate routing in three-stage Clos networks, where…

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

Polynomial Time Algorithms for the Kadison-Singer ProblemResearch Paper

The Kadison–Singer problem (Kadison and Singer, 1959) asks whether every pure state on the algebra of bounded diagonal operators on ℓ2\ell_2ℓ2​ extends uniquely to a pure state on all bounded operators. It has many equivalent forms; the one used here is Weaver's conjecture KS2 (Weaver, 2004): there are absolute constants α>0\alpha>0α>0 and c<1c<1c<1 such that every family …

55 thms1 active userReviewed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: iris

Private PCPs from Product ExpansionResearch Paper

The PCP theorem says that the witness of an NP problem can be written as a proof that a verifier checks by reading a few random positions. Its quantum analogue for QMA is open. A main obstacle is local indistinguishability: a witness stored in a quantum code of distance ddd cannot be read from any d−1d-1d−1 positions, so local tests cannot tell a YES witness from a…

36 thms1 active userReviewed
Number TheoryProbability·Captain: mikedeng1

Quadratic Probing Insertions Are ϵ−(1+o(1))\epsilon^{-(1+o(1))}ϵ−(1+o(1)) TimeResearch Paper

A hash table stores keys in an array and uses a hash value to choose where to begin searching for a free slot. Its insertion cost matters when memory use is high: a small vacant fraction can turn a short search into many memory accesses. Quadratic probing searches at square offsets from the hash. Introduced by Maurer in 1968, it has a long history of use,…

26 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

The Quantumly Fast and the Classically ForriousResearch Paper

The Forrelation problem was introduced by Aaronson (STOC 2010) as a query problem that separates quantum from classical computation as strongly as possible. Two Boolean functions χf,χg:F2n→{−1,1}\chi_f,\chi_g:\mathbb F_2^n\to\{-1,1\}χf​,χg​:F2n​→{−1,1} are given as black boxes, and the task is to decide whether χg\chi_gχg​ is correlated or anticorrelated with the Fourier transform of χf\chi_fχf​. A…

19 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

The Online Steinitz ProblemResearch Paper

In the online Steinitz problem, a sequence of real vectors arrives one vector at a time. Each vector must immediately receive an unused position in a fixed output array. The final order should distribute cancellation across the array, keeping every prefix close to its proportional share of the total. This differs from choosing a permutation after seeing the…

17 thms1 active userReviewed
Operations ResearchOptimization·Captain: mikedeng1

Breaking the √3 Barrier for Maximum Weighted 3-Set PackingResearch Paper

A weighted 3-set packing instance describes requests that each use at most three resources. Two requests can be accepted together exactly when their resource sets are disjoint. Their values need not be equal or comparable in magnitude. The objective is to choose compatible requests with maximum total value. This setting includes weighted three-dimensional…

18 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence PatternsResearch Paper

A hypergraph records a finite collection of constraints by assigning each constraint the set of variables it involves. In database query evaluation and constraint satisfaction, the shape of these overlaps can determine which decomposition methods are available. Different notions of width measure different freedoms in choosing a decomposition. Fractional…

22 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

A Tight Space Lower Bound for Pivot-Based Distance OraclesResearch Paper

A distance oracle stores information about a graph so that later queries can estimate the distance between two vertices. Storing a separate answer for every pair can require quadratic space, even when the input graph itself has only linearly many edges. Allowing a multiplicative error creates a space–accuracy trade-off. The question addressed here concerns…

17 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Testing Implies Distance Estimation with Polynomial LossResearch Paper

An adjacency query reveals one bit of a graph: whether two specified vertices share an edge. When the graph is large, even reading its entire adjacency matrix can be prohibitive. Property testing asks whether a graph satisfies a specified condition or requires a substantial fraction of its adjacencies to be changed. Distance estimation asks for that…

16 thms1 active userReviewed
Probability·Captain: mikedeng1

Fluid Limits and Upper Bounds for Randomized Greedy MatchingResearch Paper

A matching is a set of graph edges with no shared endpoint. Matching algorithms assign disjoint pairs when each participant can receive at most one partner. A local algorithm can build a matching without inspecting the whole graph, but its decisions can prevent later pairs from forming. The Modified Randomized Greedy algorithm, abbreviated MRG, introduces…

8 thms1 active userReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

Maximum Matching and Related Problems in Catalytic LogspaceResearch Paper

A matching in a graph is a collection of edges that share no vertices. A maximum matching has as many edges as any such collection. Matching is a basic problem in combinatorial optimization, but the computational resources needed to construct one depend on the machine model. A polynomial-time procedure can retain intermediate data that do not fit in…

28 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise IntractabilityResearch Paper

Distributed systems can need to know how many participants they contain even when communication links change from round to round. Counting asks every participant to determine this number exactly and then stop. Without identifiers, equal messages need not originate from the same participant. Receiving a correct estimate is also different from having enough…

28 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL ModelResearch Paper

A maximal independent set selects pairwise nonadjacent vertices so that every unselected vertex has a selected neighbor. Distributed algorithms use such sets to break symmetry and organize neighboring processors. The classical algorithms of Luby (1986) and Alon, Babai and Itai (1986) achieve logarithmic randomized round bounds. The pinned submission asks…

21 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

An Ω~(log⁡nlog⁡m)\tilde \Omega(\log n \log m)Ω~(lognlogm) Information-Theoretic Lower Bound for Randomized Online Set CoverResearch Paper

A set cover selects sets whose union contains every required element, while minimizing the number selected. In its online version, requirements arrive over time and each must be covered immediately. A choice that looks economical on one prefix may prove unnecessary once more requirements arrive, but purchases cannot be reversed. The problem therefore…

10 thms1 active userReviewed
Complexity TheoryProbability·Captain: mikedeng1

Metric Testing: A Characterization of One-Sided TestabilityResearch Paper

A matrix can be too large to inspect completely even when the property being tested is defined on small collections of its labels. A one-sided tester must accept every valid matrix with probability one while finding a violation with probability at least two thirds whenever repairing the matrix requires a fixed positive fraction of its entries to change. The…

25 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Distributed Lower Bounds via Automatic Self-ReductionResearch Paper

Round elimination is the main technique for proving lower bounds on the number of communication rounds that distributed algorithms need to solve local graph problems. Its core is a lifting theorem: from a TTT-round algorithm for a problem Π\PiΠ it builds a (T−1)(T-1)(T−1)-round algorithm for a derived problem R(Π)R(\Pi)R(Π). When R(Π)R(\Pi)R(Π) is Π\PiΠ again (a fixed point), iterating…

10 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Thinning and Sprinkling: Robust Vertex Sampling and Almost HamiltonicityResearch Paper

A Hamilton cycle visits every vertex of a graph exactly once before returning to its starting vertex. Determining when a graph must contain such a cycle is a basic structural question. One necessary feature is resistance to fragmentation: deleting a small set of vertices cannot leave too many disconnected pieces. The parameter that quantifies this…

25 thms1 active userReviewed
Complexity TheoryOptimization·Captain: mikedeng1

Randomized Query Lower Bounds for Submodular Function MinimizationResearch Paper

Submodular function minimization asks for a least-value subset when the only access to a set function is through queries of its values. It provides a common optimization framework for functions with diminishing marginal returns. Even after restricting attention to this structured class, the number of oracle calls needed to solve the problem remains a…

21 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Polylogarithmic Collective Tree ExplorationResearch Paper

A team exploring an unknown tree must decide how to divide its work while paying for travel between branches. Collective tree exploration models this coordination problem with mobile agents, unrestricted communication, and edges revealed when an agent visits an endpoint. Fraigniaud, Gąsieniec, Kowalski and Pelc introduced the synchronous problem and an…

22 thms1 active userReviewed
Graph TheoryProbabilityRandom Matrix Theory·Captain: mikedeng1

Hamiltonicity of mildly pseudorandom regular graphsResearch Paper

An (n,d,λ)(n,d,\lambda)(n,d,λ)-graph is an nnn-vertex ddd-regular graph whose adjacency matrix has all non-trivial eigenvalues of absolute value at most λ\lambdaλ. The smaller λ\lambdaλ is compared to ddd, the more the graph resembles a random one. Whether such a graph has a Hamilton cycle, a cycle through every vertex, is a central question on pseudorandom graphs. Krivelevich and…

22 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

A Full Complexity Dichotomy for Complex-Valued Boolean Holant ProblemsResearch Paper

A counting problem asks for the weighted number of global configurations satisfying local constraints; a complexity dichotomy decides, for every choice of local rules, whether the problem is computable in polynomial time or #P-hard. Boolean Holant problems are the most general Boolean framework in which such classifications are pursued: they contain…

48 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Approximation Algorithms for Satisfiable Phylogenetic CSPsResearch Paper

A phylogenetic constraint satisfaction problem asks for a rooted binary tree whose leaves are given variables and which satisfies as many local constraints as possible, each constraint prescribing the shape of the subtree induced on a few leaves. Such problems formalize the reconstruction of an evolutionary tree from information about small groups of…

43 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: iris

A Nearly Linear-Time FPRAS for Counting KnapsackResearch Paper

Given nonnegative integer weights w1,…,wnw_1,\dots,w_nw1​,…,wn​ and a capacity TTT, the counting knapsack problem (#Knapsack) asks how many subsets of the items fit: the size of the family of feasible subsets Ω\OmegaΩ. The problem is the counting version of 0/1 knapsack and, equivalently, counts the points of the Boolean cube below a halfspace, an object studied in learning…

16 thms1 active userReviewed
PreviousPage 19 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