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

Incremental Approximate Vertex Connectivity via Almost-Linear Time Local Cut AlgorithmsResearch Paper

The vertex connectivity κ(G)\kappa(G)κ(G) of a graph is the least number of vertices whose removal disconnects it. It measures how robust a network is against node failures, and it is one of the most basic quantities in graph algorithms. For directed graphs the notion is strong connectivity: κ(G)\kappa(G)κ(G) is the least size of a set whose deletion leaves a graph that is…

23 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Structural Complexity of Matching with IndifferencesResearch Paper

Centralized school choice and other two-sided assignment systems are run by clearinghouses that announce a single outcome. When preferences contain ties (a student may be indifferent between several schools), the classical notion of stability splits into weak, strong and super stability (Irving 1994), and a deterministic rule must also say which stable…

19 thms3 active usersReviewed
Graph TheoryProbability·Captain: Shuze Chen

Hitting time for loose Hamilton cycles in the random hypergraph processResearch Paper

Hitting-time theorems are among the sharpest statements in the theory of random graphs. Instead of asking at which edge density a property appears, they ask whether it appears at the exact moment the obvious local obstruction disappears. For graphs, Ajtai, Komlós and Szemerédi and, independently, Bollobás proved in 1984–85 that the random graph process…

21 thms3 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: Shuze Chen

Fast Almost-Uniform Sampling of Random kkk-SAT SolutionsResearch Paper

A random kkk-SAT formula with nnn variables and m=⌊αn⌋m=\lfloor\alpha n\rfloorm=⌊αn⌋ clauses is the standard model of a typical constraint satisfaction instance. Below the satisfiability threshold, which is near 2kln⁡22^k\ln 22kln2 clauses per variable, such a formula has exponentially many solutions. Sampling one of them almost uniformly is a basic algorithmic task: it gives…

27 thms3 active usersReviewed
Algebraic TopologyComplexity TheoryGroup Theory+1·Captain: Shuze Chen

Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPsResearch Paper

Agreement tests, locally testable codes and probabilistically checkable proofs share one step: local functions that agree on most overlaps must be stitched into one global function. On high-dimensional expanders this step is controlled by swap coboundary expansion. That notion asks the faces complex of a simplicial complex to be a coboundary expander with…

29 thms3 active usersReviewed
Graph TheoryLinear algebraOperations Research+1·Captain: Shuze Chen

Breaking the Quadratic Time Barrier for Flow Sparsifiers via Schur Complement LocalizationResearch Paper

Many multicommodity flow and cut problems only concern a small set of terminals inside a large network. Vertex sparsification replaces the network by a graph on the terminals alone that preserves, up to a factor called the quality, how well every pattern of terminal traffic can be routed. Such a graph is a preprocessing step for approximation algorithms…

19 thms3 active usersReviewed
Theoretical Computer Science·Captain: Shuze Chen

Pattern Matching with Edits in O~(n+k3⋅n/m)\tilde{O}(n+k^3 \cdot n/m)O~(n+k3⋅n/m) TimeResearch Paper

Finding the positions where a pattern occurs in a text with a few typos is one of the basic tasks on strings, used for example in read mapping in computational biology. With the edit distance ed(X,Y)\mathrm{ed}(X,Y)ed(X,Y) (the minimum number of single-character insertions, deletions and substitutions turning XXX into YYY) the task is pattern matching with edits: given a…

25 thms3 active usersReviewed
Information Theory·Captain: mikedeng1

Massively Parallel Algorithms for Huffman CodingResearch Paper

Huffman coding assigns binary codewords to the characters of a text so that no codeword is a prefix of another and the encoded text is as short as possible. Huffman's greedy algorithm (Huffman 1952) solves it in linear time once the character frequencies are sorted. It is a basic step of practical compression.

27 thms3 active usersReviewed
Markov ChainProbability·Captain: mikedeng1

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness ThresholdResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph is a basic problem in approximate counting and statistical physics: it is the zero-temperature antiferromagnetic Potts model, and an efficient sampler yields an approximation of the number of colourings. The standard sampler is the single-site Glauber dynamics: pick a uniformly random vertex and…

24 thms3 active usersReviewed
Algorithmic Game TheoryComplexity TheoryOperations Research·Captain: mikedeng1

Learning and Optimisation of Rank Ordered Gain Functions and with Modular CostsResearch Paper

A principal choosing a group of workers must compare the group's collective value with the cost of engaging its members. Individual competencies give useful ordering information, but a ranking alone does not describe how participation costs interact with collective performance. Etesami, Liu and Sahitaj study this distinction through augmented rank-ordered…

26 thms3 active usersReviewed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by TreewidthResearch Paper

For an NP-hard problem, "polynomial or not" says nothing about how hard the hard cases are. On graphs of bounded treewidth the finer question is the base of the exponent: many problems are solvable in time ctw⋅nO(1)c^{\mathrm{tw}}\cdot n^{O(1)}ctw⋅nO(1) by dynamic programming over a tree decomposition of width tw\mathrm{tw}tw, and a line of work started by Lokshtanov, Marx and…

26 thms3 active usersReviewed
Complexity TheoryGraph Theory·Captain: iris

A Polynomial Kernel for Planar Directed Feedback Vertex SetResearch Paper

A directed feedback vertex set of a digraph DDD is a set of vertices whose removal leaves no directed cycle. Directed Feedback Vertex Set (DFVS) asks, for a digraph DDD and an integer kkk, whether such a set of size at most kkk exists. It is a basic problem in deadlock resolution, circuit testing and the analysis of feedback in networks, and it is NP-hard even on…

41 thms3 active usersReviewed
Information TheoryTheoretical Computer Science·Captain: Shuze Chen

Dynamic LZ77: No Space for ImprovementResearch Paper

Lempel–Ziv 77 (LZ77) is the parsing behind most dictionary compressors and the reference measure of repetitiveness in compressed string algorithms. Its size zzz can be exponentially smaller than the length nnn of a highly repetitive text, which is why compressed indexes aim for space proportional to zzz rather than nnn.

22 thms3 active usersReviewed
Complexity TheoryInformation TheoryTheoretical Computer Science·Captain: iris

Asymptotically Optimal Two Source Extractors for Arbitrary Constant Entropy RateResearch Paper

A randomness extractor turns weakly random bits into nearly uniform ones. Cryptographic protocols, derandomization and Ramsey-graph constructions all need such objects, and in cryptographic uses the error must be negligible, not merely small. A single weak source admits no deterministic extractor, so the standard model asks for a function of two independent…

36 thms3 active usersReviewed
AlgebraComplexity TheoryTheoretical Computer Science·Captain: Shuze Chen

From Block Orthogonality to Decidability in Complex-Weighted Counting CSPResearch Paper

Counting constraint satisfaction problems (#CSP) express partition functions, weighted graph homomorphisms and many other counting problems. In 2017 Cai and Chen proved a complete complexity dichotomy for #CSP over any finite domain with algebraic complex weights (CC17, Gödel Prize 2021): for every fixed finite set F\mathcal FF of constraint functions, …

26 thms3 active usersReviewed
Graph TheoryTheoretical Computer ScienceTopology·Captain: Shuze Chen

A unifying framework for Graph Minor Structure Theorems with polynomial boundsResearch Paper

The Graph Minor Structure Theorem of Robertson and Seymour describes every graph that excludes a fixed graph HHH as a minor: around any large grid-like piece, after deleting a bounded number of apex vertices, the graph is drawn in a surface in which HHH does not embed, up to a bounded number of vortices of bounded depth. Its local form, the Local Structure…

20 thms3 active usersReviewed
Complexity TheoryInformation TheoryProbability+1·Captain: Shuze Chen

Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand InequalityResearch Paper

Succinct data structures store a combinatorial object in space close to the information-theoretic minimum while still answering queries quickly. Balanced parentheses are the basic case: an ordered tree with nnn nodes, or a forest, is written as a word of 2n2n2n brackets, and tree navigation reduces to bracket queries such as findclose (the position of the bracket…

18 thms3 active usersReviewed
Computational ComplexityGraph Theory·Captain: Shuze Chen

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable DecompositionResearch Paper

Minimum Bisection asks whether the vertex set of a graph can be split into two halves, up to one vertex, with at most kkk edges between them. It is the unweighted two-part case of the graph-partitioning problem of Kernighan and Lin (1970) and is NP-complete (Garey, Johnson and Stockmeyer, 1976). Parameterized by the cut size kkk, it became a test case for the…

29 thms3 active usersReviewed
Complexity TheoryGroup TheoryLinear algebra+1·Captain: Shuze Chen

Group Isomorphism: Depth-2122\frac{1}{2}221​ Circuits and Lower BoundsResearch Paper

Group Isomorphism (GpI) asks whether two finite groups, each given by its full multiplication table (its Cayley table), are isomorphic. With n=∣G∣n=|G|n=∣G∣, Miller's generator-enumeration algorithm decides it in time nlog⁡2n+O(1)n^{\log_2 n+O(1)}nlog2​n+O(1), because every group of order nnn is generated by at most log⁡2n\log_2 nlog2​n elements. Whether GpI is in polynomial time is open, and so is the…

17 thms3 active usersReviewed
Theoretical Computer Science·Captain: mikedeng1

3SUM Made Simpler (Without Matrix Multiplication), kkk-SUM Hypothesis Refuted for Odd kkk, and Real 3SUM/APSP DerandomizedResearch Paper

The 3SUM problem asks whether numbers from given collections satisfy an additive relation. Its running time matters in fine-grained complexity, where reductions compare the computational costs of different problems. A batch version asks which of many query numbers belong to a sumset. It retains information that a single yes-or-no decision discards, and…

12 thms3 active usersReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: iris

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold RateResearch Paper

Shamir secret sharing (Shamir 1979) encodes a secret as the values of a random polynomial at nnn points: any kkk of these shares determine the secret, and any k−1k-1k−1 of them reveal nothing. It is a basic building block of secure multiparty computation, where reconstruction thresholds near n/2n/2n/2 and n/3n/3n/3 are standard.

35 thms3 active usersReviewed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: Shuze Chen

A Counting Lemma for Somewhat Restricted 3-APsResearch Paper

Roth's theorem says that dense sets of integers contain three-term arithmetic progressions (x,x+a,x+2a)(x, x+a, x+2a)(x,x+a,x+2a) with a≠0a \neq 0a=0. Meshulam proved the analogue in the finite field model Fpn\mathbb F_p^nFpn​ (Meshulam, 1995). In that model a dense set contains not only one progression but a positive fraction of all of them. This counting statement follows from the existence…

27 thms3 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Algorithms for Min-Color Path with Bounded Color-DegreeResearch Paper

A robot that must move from sss to ttt through a field of obstacles, or a signal that must cross a sensor field, wants to cross as few obstacles as possible. Discretized, this is Min-Color Path: the obstacles become colors on the vertices of an arrangement graph and one asks for an sss–ttt path touching the fewest colors. The problem appears as Minimum Constraint…

26 thms3 active usersReviewed
Discrete GeometryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

An Almost-Linear Time Algorithm for Multidimensional Subset SumResearch Paper

Subset Sum asks whether some sub-multiset of given integers sums to a target. It is one of Karp's 21 NP-complete problems, and its pseudo-polynomial complexity is a long-standing benchmark: Bellman's dynamic program runs in O(nt)O(nt)O(nt) time, Pisinger's algorithm in O(nN)O(nN)O(nN) for items bounded by NNN, and a line of work brought the bound down to O~(n+N5/3)\tilde O(n+N^{5/3})O~(n+N5/3) (Pola…

21 thms3 active usersReviewed
Graph Theory·Captain: mikedeng1

Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized LeaderResearch Paper

A balanced vertex separator removes a small set of vertices so that no remaining connected component contains most of the original graph. Such separators allow a graph problem to be divided into smaller instances. Their usefulness depends on both the number of removed vertices and the time spent finding them: a small separator with expensive construction…

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