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
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman I: The Convex Hull of Nonnegative Integer Parity Solutions Is the Polyhedron of Odd-Set InequalitiesResearch Paper

The Chinese postman problem, posed by Meigu Guan (Kwan Mei-Ko) in 1962, asks for a shortest closed walk in a graph that traverses every edge at least once: the route of a postman who must cover every street and return to the post office. It is the basic model of arc routing (street sweeping, snow ploughing, meter reading, inspection of networks), and it is…

11 thms5 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Online Stochastic Matching: Beating 1-1/e 1: When OPT = Ω(n), the Two Suggested Matchings Algorithm Achieves ALG/OPT ≥ (1 − 2/e²)/(4/3 − 2/(3e)) − ε ≈ 0.670 with Probability 1 − e^(−Ω(n))Research Paper

Online bipartite matching models a platform that must commit each arriving request to a resource immediately. The motivating application of Feldman, Mehta, Mirrokni and Muthukrishnan is display advertising: an ad server knows from past traffic how many impressions of each type (web page, audience segment) to expect, sells them to advertisers in advance, and…

28 thms5 active users
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Eigenvalues and Expanders: A Regular Bipartite Graph Is a Strong Expander If and Only If λ(G) Is Bounded Away from 0Research Paper

Expander graphs are sparse graphs in which every set of vertices has many neighbours. Families of them with bounded degree and expansion bounded away from zero are a basic tool of theoretical computer science: they are the main component of the sorting network of Ajtai, Komlós and Szemerédi (AKS 1983), the building block of superconcentrators and other…

16 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem II: Geometric Grouping with Residual LP RoundingResearch Paper

One-dimensional bin packing asks for the fewest unit-capacity bins that hold a given list of items with sizes in (0,1)(0,1)(0,1). Deciding whether two bins suffice is NP-hard (it contains the partition problem), so no polynomial-time algorithm guarantees a ratio below 3/23/23/2 unless P = NP. The natural question is therefore asymptotic: how small can the additive error …

21 thms5 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Applied Combinatorics I: Graph Theory and Dirac's Hamiltonicity TheoremTextbook

Graphs are the most basic combinatorial model of pairwise relations: road networks, frequency interference between radio stations, schedules, circuit layouts. Chapter 5 of Keller and Trotter's Applied Combinatorics (appliedcombinatorics.org, CC BY-SA 4.0) introduces the vocabulary of graph theory and proves its first structural theorems: when a graph can be…

12 thms5 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Limits of Permutation Sequences II: Convergence Is Equivalent to Being Cauchy in the Rectangular DistanceResearch Paper

For dense graphs, convergence of subgraph densities was shown by Lovász and Szegedy (2006) to have graphons as limit objects, and Borgs, Chayes, Lovász, Sós and Vesztergombi (2008) proved that the same convergence is metric: a graph sequence converges exactly when it is Cauchy in the cut distance. The metric view is what makes the space of graphons compact…

23 thms5 active usersReviewed
🏆Completed
Probability·Captain: mikedeng1

Limits of Permutation Sequences I: Every Convergent Permutation Sequence Has a Limit Permutation, and Every Limit Permutation Is a LimitResearch Paper

Large combinatorial structures are often best understood through their limits. For dense graphs, Lovász and Szegedy (2006) showed that every sequence of graphs whose subgraph densities converge has a limit object, a graphon, and that every graphon arises this way. Borgs, Chayes, Lovász, Sós and Vesztergombi (2008) related this convergence to the cut…

18 thms5 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Competitive Paging Algorithms IV: An Algorithm Competitive against Several Others Exists iff the Reciprocal Ratios Sum to at Most 1Research Paper

Paging is the problem of managing a fast memory that holds kkk pages out of nnn: when a requested page is not in fast memory (a page fault), some resident page must be evicted, and the cost of an algorithm is its number of faults. Practitioners have many eviction rules. Least-recently-used (LRU) performs well on real workloads but can be kkk times worse than the…

9 thms5 active usersReviewed
Number Theory·Captain: LG

Erdős Problem 30: Sidon sets in {1,…,N} have size √N + O(N^ε)Open Problem

A set of integers is a Sidon set if all of its pairwise sums a+ba+ba+b (a≤ba\le ba≤b) are different. Sidon, in connection with Fourier analysis, asked how dense such sets can be, and the question became one of the standard problems of additive combinatorics. Let

9 thms5 active usersReviewed
Captain: LG

Erdős Problem 20: The Sunflower ConjectureOpen Problem

A sunflower (also called a Δ\DeltaΔ-system) with kkk petals is a family of kkk sets whose pairwise intersections are all equal to one common set, the kernel. In 1960 Erdős and Rado proved the sunflower lemma: every sufficiently large family of nnn-element sets contains a sunflower with kkk petals, and they asked how large "sufficiently large" must be (Erdős–Rado 1960)…

16 thms5 active usersReviewed
Number Theory·Captain: Zexuan Liu

Erdős Problem 142: Asymptotics for Sets Free of k-Term Arithmetic ProgressionsOpen Problem

Erdős asked, repeatedly and with a rising price tag, for an asymptotic formula for the largest subset of {1,…,N}\{1,\dots,N\}{1,…,N} that contains no arithmetic progression of a given length. He offered 1000 dollars for it in [Er97c] and 10000 dollars in [Er81, p.4], where he called the question "probably enormously difficult"; elsewhere he described it as "probably…

47 thms5 active usersReviewed
Graph Theory·Captain: hao jia

P3-Partitions of Cubic 3-Connected Graphs (OPG-46613)Open Problem

A P3P_3P3​-packing in a graph is a collection of pairwise vertex-disjoint paths on three vertices. Determining the largest such packing is NP-hard even in restricted graph classes, so structural hypotheses that force an optimal packing are of independent interest in graph factor theory. The present question asks whether 3-vertex-connectivity and cubicity force…

16 thms5 active usersReviewed
Linear Optimization·Captain: Shuze Chen

The Polynomial Hirsch ConjectureOpen Problem

The simplex method walks along edges of a polytope from vertex to vertex. Whether any pivot rule could ever make that walk short in the worst case is governed by a prior, purely geometric question: how far apart, in the edge graph, can two vertices of a polytope be? Warren Hirsch conjectured in 1957 that the diameter of a ddd-dimensional polytope with nnn facets…

82 thms5 active usersReviewed
🏆Completed
Information TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Dictators are most informativeResearch Paper

How much information about a noisy vector can one bit retain? Let XXX be uniform on {−1,1}n\{-1,1\}^n{−1,1}n and let YρY_\rhoYρ​ be obtained from XXX by flipping each coordinate independently with probability (1−ρ)/2(1-\rho)/2(1−ρ)/2, so that ρ∈[0,1]\rho\in[0,1]ρ∈[0,1] is the correlation. A one-bit summary is f(X)f(X)f(X) for a Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}f:{−1,1}n→{−1,1}, and the question is which fff maximizes the mutua…

22 thms4 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Faster Dynamic Maximal Independent Set against Adaptive AdversariesResearch Paper

A maximal independent set (MIS) of a graph is a set MMM of vertices, no two adjacent, such that every vertex outside MMM has a neighbour in MMM. It is the basic symmetry-breaking object of parallel and distributed computing. In the fully dynamic setting the graph changes by edge insertions and deletions, and an algorithm must keep an MIS of the current graph…

12 thms4 active usersReviewed
Computational ComplexityGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Finding full immersions is fixed-parameter tractable in labeled tour graphsResearch Paper

Testing whether a small graph HHH is contained in a large nnn-vertex graph GGG is a central algorithmic question for every notion of containment. For graph minors the answer has been fixed-parameter tractable since Robertson and Seymour's disjoint-paths algorithm (Graph Minors XIII), and for topological minors and immersions since Grohe, Kawarabayashi, Marx and…

22 thms4 active usersReviewed
Algorithmic Game TheoryComputational Complexity·Captain: Shuze Chen

Necklace Splitting with Ten Beads per Colour is PPAD-HardResearch Paper

A necklace is a sequence of beads, each of one of nnn colours, where colour ccc occurs 2bc2b_c2bc​ times. Two thieves want to share it fairly: cut it at some positions, hand the pieces out alternately, and each thief must receive exactly bcb_cbc​ beads of every colour. Goldberg–West and Alon–West proved that nnn cuts always suffice, by a topological argument, and the search…

25 thms4 active usersReviewed
cryptographyHarmonic AnalysisInformation Theory+1·Captain: Shuze Chen

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial IntersectionResearch Paper

In Shamir secret sharing over a prime field Fp\mathbb F_pFp​, a secret sss is shared among nnn parties by a uniformly random polynomial PPP of degree at most kkk with P(0)=sP(0)=sP(0)=s; party iii receives P(αi)P(\alpha_i)P(αi​) for distinct nonzero evaluation points αi\alpha_iαi​. Any k+1k+1k+1 parties recover the secret and any kkk learn nothing about it. Local leakage resilience (LLR) asks for more: if…

24 thms4 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

(1+ϵ)(1+\epsilon)(1+ϵ)-Distortion Spanning Tree Covers of Minor-Free Graphs with Size O(log⁡log⁡n)O(\log \log n)O(loglogn)Research Paper

A tree cover of a weighted graph approximates all of its shortest-path distances by a small number of trees: for every pair of vertices, some tree in the collection keeps their distance within a factor α\alphaα, the distortion, and no tree shortens any distance. Tree covers are a standard device for transferring tree algorithms to general graphs, with…

25 thms4 active usersReviewed
Optimization·Captain: mikedeng1

Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and MoreResearch Paper

Many problems on graphs ask for a linear arrangement of the vertices that keeps some "frontier" small. In Cutwidth, the frontier of a prefix of the arrangement is the set of edges leaving it; in Pathwidth (equivalently, vertex separation, by Kinnersley 1992), it is the set of prefix vertices that still have a neighbour outside the prefix. Both are classical…

48 thms4 active usersReviewed
ProbabilityStatistical MechanicsTheoretical Computer Science·Captain: Shuze Chen

Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking ThresholdResearch Paper

The hardcore model weights the independent sets of a graph: a set III of pairwise non-adjacent vertices gets weight λ∣I∣\lambda^{|I|}λ∣I∣, and the partition function ZG,fug(λ)=∑Iλ∣I∣Z_{G,\mathrm{fug}}(\lambda)=\sum_I\lambda^{|I|}ZG,fug​(λ)=∑I​λ∣I∣ is the independence polynomial of GGG. Since Lee and Yang (1952), phase transitions of a spin system are located through the complex zeros of its partition…

93 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering ProblemsResearch Paper

Correlation clustering asks for a partition of the vertices of a graph whose edges are labelled "similar" or "dissimilar", agreeing with as many labels as possible. In its maximization form, MaxAgree, one maximizes the total weight of positive edges inside clusters plus negative edges between clusters. The problem was introduced by Bansal, Blum and Chawla (M…

26 thms4 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: Shuze Chen

The Complexity of UnpredictabilityResearch Paper

Catalytic logspace (CL) was introduced by Buhrman, Cleve, Koucký, Loff and Speelman (BCK+14): a logarithmic-space machine is given, in addition, a polynomially long read-write catalytic tape that starts with an arbitrary string chosen by an adversary and must hold exactly that string again when the machine halts. They showed that CL contains TC1\mathsf{TC}^1TC1,…

23 thms4 active usersReviewed
Algorithmic Game TheoryInformation Theory·Captain: mikedeng1

Switching and Entropy Bounds for Stable MatchingsResearch Paper

A market can have several stable outcomes even when every participant has a strict preference list. Finding one outcome answers a different question from counting all of them. The extremal stable-matching count asks how many stable outcomes one market can admit in the worst case. It measures the possible size of the entire solution set, without selecting an…

34 thms4 active usersReviewed
Complexity TheoryDynamic Programming·Captain: mikedeng1

Get Permanent Results Faster by Counting StarsResearch Paper

The permanent combines the entries of a square matrix by summing one product for each permutation of its columns. For a matrix containing only zeros and ones, it counts perfect matchings in the corresponding bipartite graph. Over other commutative rings, the same expression is an algebraic computation problem. Its arithmetic cost measures how many additions…

22 thms4 active usersReviewed
PreviousPage 4 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