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

Recognizing Label-Connected GraphsResearch Paper

In the classical gossiping problem every participant holds one piece of information, and whenever two participants call each other they exchange everything they know. With all pairs allowed to call, 2n−42n - 42n−4 calls are necessary and sufficient for n≥4n \ge 4n≥4 participants (Baker–Shostak 1972; Hajnal–Milner–Szemerédi 1972). When the available calls are prescribed…

19 thms2 active usersReviewed
OptimizationTheoretical Computer Science·Captain: Shuze Chen

Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation SchemesResearch Paper

Weighted edit distance and other string alignment problems are computed by combining boundary-to-boundary distance matrices of planar alignment graphs. These matrices are Monge: Mij+Mi+1,j+1≤Mi,j+1+Mi+1,jM_{ij}+M_{i+1,j+1}\le M_{i,j+1}+M_{i+1,j}Mij​+Mi+1,j+1​≤Mi,j+1​+Mi+1,j​. For unweighted alignment, Tiskin showed that the matrices have a compact structure: O(n)O(n)O(n) space and O(nlog⁡n)O(n\log n)O(nlogn)-time min-plus products. That…

15 thms2 active usersReviewed
Computational ComplexityGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Constrained Directed Separation: Algorithms and ClassificationsResearch Paper

Directed Multicut asks to delete at most kkk nonterminal vertices of a digraph so that no directed path remains from the first to the second terminal of any demand. Olkowski and Ramanujan study what happens when the deleted vertices must also satisfy a structural condition: the subdigraph they induce must belong to a fixed hereditary class H\mathcal HH.…

27 thms2 active usersReviewed
Computational ComplexityGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Once-Paid Subsequences and the Cost of Min-Plus ApproximationResearch Paper

Many sequence problems are solved by a prefix recurrence that uses only minimum and addition, and such a recurrence, once its structure is fixed before the costs are known, is a min-plus circuit. Lower bounds on min-plus circuits therefore say which recurrences cannot exist, independently of how clever the choice of states is (Jukna–Seiwert 2020).

18 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Online Graph Exploration under T-Interval ConnectivityResearch Paper

A mobile agent that discovers a network one hop at a time cannot plan from a complete map. If links change while it moves, connectivity at each instant does not by itself let the agent reach every vertex. This matters for the mathematical foundations of exploration in changing networks: the assumption must constrain how connectivity persists, rather than…

22 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Streaming Weighted Set Cover Requires (Nearly) Linear SpaceResearch Paper

In streaming set cover, mmm sets over an nnn-element universe arrive one at a time; an algorithm makes a few passes with limited memory and must approximate the minimum total weight of a cover. Storing the input costs Θ(mn)\Theta(mn)Θ(mn) bits, the incidence matrix. Running time is unrestricted, so the question is purely about information: how much memory a given number…

12 thms2 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: iris

Subset Sum in Almost-Linear TimeResearch Paper

Subset Sum asks, for integers 1≤a1,…,an≤Δ1\le a_1,\dots,a_n\le\Delta1≤a1​,…,an​≤Δ and a target ttt, whether some sub-collection sums to ttt. It is NP-hard, but solvable in pseudopolynomial time: Bellman's dynamic program takes O(n2Δ)O(n^2\Delta)O(n2Δ) time. The fine-grained question is how fast it can be solved in terms of nnn and Δ\DeltaΔ. Under the Strong Exponential Time Hypothesis no …

31 thms2 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

An O~(n3)\widetilde{O}(n^3)O(n3)-time FPRAS for the PermanentResearch Paper

The permanent of an n×nn\times nn×n matrix A=(aij)A=(a_{ij})A=(aij​) is per(A)=∑σ∈Sn∏i=1nai,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​ai,σ(i)​. For a 0/1 matrix it counts the perfect matchings of the bipartite graph G=(V1∪V2,E)G=(V_1\cup V_2,E)G=(V1​∪V2​,E) whose adjacency matrix is AAA. Valiant showed in 1979 that computing it exactly is #P-complete even for 0/1 matrices, so the question became how fast it…

30 thms2 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: Shuze Chen

Discrete Isoperimetric Inequalities via CurvatureResearch Paper

Isoperimetric inequalities on the Boolean hypercube relate the variance of a Boolean function f:{±1}n→{±1}f:\{\pm1\}^n\to\{\pm1\}f:{±1}n→{±1} to how often flipping one coordinate changes its value. They drive sharp-threshold theorems, junta approximation, noise sensitivity, percolation, social choice and hardness of approximation (O'Donnell, Analysis of Boolean Functions, 2014).…

23 thms2 active usersReviewed
Computational ComplexityGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Deterministic Connectivity Sketches Under Edge DeletionsResearch Paper

A graph is to be compressed so that, after any set of its edges is deleted, one can still tell whether the remaining graph is connected. The question links one-way communication, fault-tolerant connectivity oracles, and single-pass dynamic graph streaming. With randomness it is well understood: the linear sketches of Ahn, Guha and McGregor (AGM12) use …

25 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Monotone Local Search with Sample-Dependent Running TimesResearch Paper

Many exact exponential-time algorithms solve a subset problem: the solutions of an instance are subsets of a universe of nnn elements, and the task is to decide whether a solution of a given size kkk exists. Monotone Local Search (Fomin, Gaspers, Lokshtanov, Saurabh, J. ACM 2019) turns an extension algorithm into a subset algorithm. The extension algorithm is…

11 thms2 active usersReviewed
Group TheoryProbability·Captain: Shuze Chen

Sharp Second-Order Thresholds for Random Algebraic CoverageResearch Paper

From kkk elements of an abelian group one obtains 2k2^k2k indexed subset sums; in a noncommutative group the analogous objects are products taken in the original input order. A basic all-target question is when these representations reach every element of the group. Erdős and Rényi studied this model for arbitrary finite groups, including noncommutative ones, and…

22 thms2 active usersReviewed
Computational ComplexityGraph TheoryLinear algebra+1·Captain: Shuze Chen

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph HomomorphismsResearch Paper

A graph homomorphism partition function assigns to a symmetric weight matrix M∈Rn×nM\in\mathbb R^{n\times n}M∈Rn×n and a graph G=(V,E)G=(V,E)G=(V,E) the number

23 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic WeightsResearch Paper

Counting complexity asks which weighted sums over exponentially many assignments can be evaluated exactly in polynomial time. The Holant framework expresses such sums by placing a local function on every vertex of a graph and a Boolean variable on every edge. One then multiplies the local values and sums over all edge assignments (Valiant 2008; Cai–Lu–Xia…

22 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: Shuze Chen

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid ProphetResearch Paper

In the classical secretary problem (Dynkin 1963; Lindley 1961) nnn distinct values arrive in uniformly random order and the decision maker must accept or reject each one immediately and irrevocably. The aim is to select the largest. Rejecting about the first n/en/en/e values and then taking the first value larger than all earlier ones succeeds with probability…

11 thms2 active usersReviewed
Computational ComplexityLinear algebra·Captain: mikedeng1

Kadison–Singer in Deterministic Polynomial TimeResearch Paper

Matrix discrepancy asks how to assign plus and minus signs to a collection of matrices so their signed sum is small. A bound independent of the matrix dimension is useful when the matrices represent many simultaneous quadratic measurements: cancellation must hold in every direction, rather than for a single scalar sum. The Kadison–Singer problem, in its…

20 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Even Coarse Matching Estimates Require Nearly Linear Streaming SpaceResearch Paper

A streaming algorithm reads graph updates in sequence while retaining a limited memory state. For matching, there is a practical distinction between storing an actual set of disjoint edges and reporting only how many edges an optimal such set contains. A large matching itself takes substantial space to write down, whereas its size is a single number. This…

17 thms2 active usersReviewed
Computational GeometryTheoretical Computer Science·Captain: Shuze Chen

Dynamic Optimality to within O(log log log n)Research Paper

A binary search tree (BST) that restructures itself while serving lookups can adapt to the access pattern: frequently or recently accessed keys can be kept near the root. The dynamic optimality conjecture of Sleator and Tarjan (1985) asks whether a single online algorithm, splay trees in their formulation, is within a constant factor of the best offline…

23 thms2 active usersReviewed
Computational GeometryOperations ResearchOptimization·Captain: Shuze Chen

Stacking Stars: Minimum-Area Packing with and without RotationResearch Paper

Packing irregular shapes without overlap so as to use little material is a core problem of the cutting and nesting industries (sheet metal, textiles, wood). It has a large experimental and operations-research literature and several commercial and open-source systems. The CG:SHOP 2024 challenge (Fekete et al.) was a packing problem with nonconvex objects.…

25 thms2 active usersReviewed
Complexity TheoryMachine LearningProbability·Captain: Shuze Chen

Learning DNF from Satisfying Assignments with Membership QueriesResearch Paper

Learning from satisfying assignments was introduced by De, Diakonikolas and Servedio (DDS15, SODA 2015). An unknown Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} from a known class is given only through independent uniform samples from its satisfying set F=f−1(1)F = f^{-1}(1)F=f−1(1), and the learner must output a sampler whose output law is close to the uniform law UFU_FUF​ in total…

24 thms2 active usersReviewed
Graph TheoryProbability·Captain: iris

Universality in random graphs via optimal linking systems: trees and beyondResearch Paper

A graph GGG is universal for a family F\mathcal FF if it contains a copy of every member of F\mathcal FF as a subgraph. Sparse universal graphs for bounded-degree trees were first studied for circuit design (Friedman–Pippenger 1987; Bhatt, Chung, Leighton and Rosenberg 1989). The probabilistic question is how large ppp must be for the binomial random graph G(n,p)G(n,p)G(n,p) to…

40 thms2 active usersReviewed
Graph Theory·Captain: Shuze Chen

Sharp Spectral Bounds for Kikuchi Matrices: The Hypergraph Moore Bound and Optimal Trade-offs for kkkXORResearch Paper

A collection of parity constraints can contain a small dependency: a nonempty collection of constraints in which every variable appears an even number of times. Such dependencies are combinatorial certificates, and their size measures how far a hypergraph resembles an acyclic object. For ordinary graphs, the smallest such collection is a shortest cycle. The…

23 thms2 active usersReviewed
Number TheoryTheoretical Computer Science·Captain: iris

A Complete Characterization of Eventually Evasive Binary PatternsResearch Paper

Deciding whether a fixed word occurs in a text is the most basic string-matching task. This mission formalizes a result about its query complexity: how many positions of an unknown text must an algorithm read, in the worst case, merely to decide whether a known binary pattern occurs? Computation is free and only reads are counted, so the question isolates…

29 thms2 active usersReviewed
Information TheoryRepresentation TheoryTheoretical Computer Science·Captain: iris

The Honeycomb Framework for Code BoundsResearch Paper

A binary code of length nnn is a set C⊆{±1}nC\subseteq\{\pm1\}^nC⊆{±1}n; it has minimum distance at least ddd if any two distinct codewords differ in at least ddd coordinates. The rate–distance tradeoff asks for the largest size A2(n,d)A_2(n,d)A2​(n,d) of such a code, and asymptotically for

45 thms2 active usersReviewed
Theoretical Computer Science·Captain: Shuze Chen

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update TimeResearch Paper

Correlation clustering asks for a partition of the vertices of a complete graph whose edges are labelled (+)(+)(+) (similar) or (−)(-)(−) (dissimilar), minimizing the number of disagreements: (+)(+)(+) edges between clusters plus (−)(-)(−) edges inside clusters. Introduced by Bansal, Blum and Chawla (DOI 10.1023/B:MACH.0000033116.57574.95), it is a standard model for…

22 thms2 active usersReviewed
PreviousPage 11 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