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
Discrete GeometryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) XIV: Edmonds' Matroid Intersection Polytope TheoremTextbook

Many combinatorial optimization problems ask for a maximum-weight set that is "independent" in two different senses at once: a bipartite matching is a set of edges that uses each left node at most once and each right node at most once; a branching in a digraph is a forest that enters each node at most once. Each of these is a common independent set of two…

27 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) XI: The Subtour Bound Equals the Optimal Held–Karp Bound (corrected: loopless)Textbook

The traveling salesman problem (TSP) asks for a cheapest circuit through every node of a graph with edge costs. No polynomial-time algorithm is known, and exact codes for large instances depend on strong lower bounds to prune their search. Two lower bounds dominate the classical literature. The first is the subtour bound, the optimal value of the linear…

27 thms3 active usersReviewed
🏆Completed
Graph TheoryOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) VI: The Tutte–Berge Formula for the Maximum Size of a MatchingTextbook

A matching pairs up nodes of a graph along its edges, each node being used at most once. Finding a largest matching is the model problem of combinatorial optimization: the obvious linear relaxation is not integral on non-bipartite graphs, and the methods developed for it (augmenting paths, odd-circuit shrinking, polyhedral descriptions) became standard…

37 thms3 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) XII: Edmonds' Matroid Polytope TheoremTextbook

The Greedy Algorithm builds a set one element at a time, always adding the heaviest element that keeps the set feasible. For the forests of a graph it finds a maximum-weight forest (Kruskal's algorithm), but for the matchings of a graph it can fail: on a 4-cycle with edge weights 9, 7, 8, 3 it picks the edges of weight 9 and 3 when the edges of weight 7 and…

21 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) I: The Characteristic Vector of a Minimum Spanning Tree Is an Optimal Solution of the Spanning-Tree Linear ProgramTextbook

A minimum spanning tree (MST) of a connected graph with edge costs is a cheapest set of edges that connects all nodes and contains no circuit. It is the prototype of a combinatorial optimization problem solved exactly by a greedy rule, and it opens Chapter 2 of Cook, Cunningham, Pulleyblank and Schrijver's Combinatorial Optimization (Wiley, 1998). The…

21 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) VII: For Arbitrary Costs the Minimum Cost of a T-Join Equals the Optimal Value of Its Linear ProgramTextbook

A mail carrier must walk every street of a district and return to the post office, and wants to walk as little as possible. Kwan Mei-Ko posed this Chinese postman problem in 1962. Edmonds observed that the extra streets to be walked a second time form a set of edges whose odd-degree nodes are exactly the odd-degree nodes of the street graph, and generalized…

25 thms3 active usersReviewed
🏆Completed
Linear algebraLinear Optimization·Captain: iris

Combinatorial Optimization (Cook et al.) IX: The Hoffman–Kruskal Theorem: {x≥0:Ax≤b}\{x \ge 0 : Ax \le b\}{x≥0:Ax≤b} Is Integral for All Integral bbb Iff AAA Is Totally UnimodularTextbook

Many combinatorial optimization problems (bipartite matching, maximum flow, shortest paths, transportation and assignment problems) can be written as integer programs

10 thms3 active usersReviewed
🏆Completed
Graph TheoryOptimization·Captain: iris

Combinatorial Optimization (Cook et al.) IV: In a Legal Ordering the Last Node's Star Is a Minimum Cut Separating the Last Two NodesTextbook

The global minimum cut problem asks, for a finite undirected graph with nonnegative edge capacities, for a partition of the nodes into two nonempty sides that is crossed by edges of least total capacity. With unit capacities the optimal value is the edge-connectivity of the graph, a basic measure of network reliability; with general capacities the problem…

14 thms3 active usersReviewed
Algorithmic Game TheoryLinear Optimization·Captain: iris

Popularity, Mixed Matchings, and Self-duality: every bipartite instance with strict preferences has a max-utility popular mixed matching {(M0,1/2),(M1,1/2)}, pure if a stable matching is perfectResearch Paper

In a two-sided matching market, applicants and jobs rank their acceptable partners, and a planner wants an assignment that is both acceptable to the participants and good for some external objective, such as total value. Stability (no applicant–job pair prefers each other to their assignments) is the classical acceptability notion, but it is restrictive:…

24 thms3 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Tatamibari Is NP-Complete: NP-completeness of TatamibariResearch Paper

Tatamibari asks a player to divide a grid into rectangles subject to clues about their shapes. Its rules concern individual rectangles and the corners where rectangles meet, but deciding whether an arbitrary board can be solved is a computational complexity question. Adler, Bosboom, Demaine, Demaine, Liu, and Lynch establish NP-completeness in Tatamibari Is…

23 thms3 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Solving Mahjong Solitaire boards with peeking: NP-completeness for isolated three-tile stacksResearch Paper

Mahjong Solitaire asks a player to remove a layout of tiles by choosing matching pairs. The visible choices depend on which tiles have already been removed. Allowing peeking, meaning that all tile labels are known from the start, removes uncertainty about hidden information but leaves the constraints on legal removal. This distinction matters when studying…

7 thms3 active usersReviewed
🏆Completed
Captain: Yuxuan Xu

Finite Balanced Allocations: the Power of D Choices for Equal Numbers of Balls and BinsTextbook

Randomized load balancing assigns arriving jobs to servers without inspecting every server. Uniformly choosing one destination is inexpensive, but a small number of servers can accumulate substantially more work than the average. Sampling a fixed number of destinations and choosing a least-loaded one provides an alternative with little additional…

4 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.139812.139812.13981Open Problem

For a Boolean function, sensitivity is the largest number of individual input-bit flips that change its output at one input. Block sensitivity allows disjoint groups of bits to be flipped instead, and counts how many such groups can each change the output. The aim of this campaign is to construct families with a large separation between these two measures…

9 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.135192.135192.13519Open Problem

For a Boolean function, sensitivity is the largest number of individual input-bit flips that change its output at one input. Block sensitivity allows disjoint groups of bits to be flipped instead, and counts how many such groups can each change the output. The aim of this campaign is to construct families with a large separation between these two measures…

9 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.133032.133032.13303Open Problem

For a Boolean function, sensitivity is the largest number of individual input-bit flips that change its output at one input. Block sensitivity allows disjoint groups of bits to be flipped instead, and counts how many such groups can each change the output. The aim of this campaign is to construct families with a large separation between these two measures…

9 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

On the Closest String and Substring Problems: A Random-Sampling PTAS for Closest Substring, Within Factor 1 + 1/(2r−1) + 3εr of Optimal with Probability 1 − 2(nm)^(−1/3)Research Paper

Many tasks in computational biology ask for a short pattern that occurs, with few errors, in each of a family of DNA or protein sequences: locating binding sites, finding conserved regions in unaligned sequences, designing PCR primers and genetic probes, and searching for a drug sequence that binds to a set of pathogen genomes. With Hamming distance as the…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Reset Sequences for Monotonic Automata: Breadth-First Search over Cyclic Intervals Finds a Minimum-Length Reset Sequence in O(kn²) TimeResearch Paper

A parts orienter takes a mechanical part in an unknown orientation and delivers it in a known one. In the pan handler studied by Natarajan, the part slides on a tray; each tilt of the tray moves it to a new resting orientation, determined by the tilt and the current orientation. Choosing a sequence of tilts that brings the part to the same final orientation…

12 thms3 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

The Minimum Latency Problem: A Polynomial-Time 144-Approximation Algorithm for the Minimum Latency Tour in Metric SpacesResearch Paper

A repairman, a delivery vehicle or a disk head starts at a depot and must visit nnn locations. The traveling salesman problem (TSP) minimizes the time at which the last visit ends. In many service settings what matters is instead the time each customer waits: the minimum latency problem (MLT), also called the traveling repairman or deliveryman problem,…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System: Steepest Descent from the Center Is Optimal at Every L1 RadiusResearch Paper

Bike-sharing operators periodically move docks between stations: a station that often runs out of bikes or of open docks frustrates users, but every moved dock costs money. Freund, Henderson and Shmoys modelled this dock re-allocation problem as a separable nonlinear integer program with a budget on the number of moved docks (Freund–Henderson–Shmoys, IPCO…

17 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationRepresentation Theory·Captain: mikedeng1

Extendibility of Werner States: Two-Sided Extendibility of Werner States Is Decided by a Minimum over Pairs of Young DiagramsResearch Paper

A bipartite quantum state ρ\rhoρ shared by Alice and Bob is (nA,nB)(n_A,n_B)(nA​,nB​)-extendible if there is a state on nAn_AnA​ copies of Alice's system and nBn_BnB​ copies of Bob's system whose reduced state on every pair (one Alice copy, one Bob copy) is ρ\rhoρ. Extendibility (also called shareability) measures how much the correlations of ρ\rhoρ can be shared among many parties. Only…

17 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchProbability·Captain: mikedeng1

Large Independent Sets in Recursive Markov Random Graphs: For Every r < 1 and ε > 0, With High Probability α(G^r_{n,p}) ≥ ((1 − r)/(2 + ε))·n/log nResearch Paper

The stability number α(G)\alpha(G)α(G) of a graph, the largest number of pairwise non-adjacent vertices, is one of the basic parameters of combinatorial optimization: computing it is NP-hard, and random graphs are the standard test bed for what typical instances look like. For the Erdős–Rényi–Gilbert graph Gn,pG_{n,p}Gn,p​, in which every edge is present independently, the…

17 thms3 active usersReviewed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Improved Guarantees for the A Priori TSP: Random Sampling with Probability 1 − (1 − p)^0.663 and a 3/2-Approximate Master Tour Has Approximation Guarantee Below 3.1 on Instances with a DepotResearch Paper

In the a priori traveling salesman problem with independent activation, a tour through all customers must be fixed before it is known which customers need a visit; each customer is active independently with a known probability, and the fixed tour is afterwards cut short to the active ones. The model, introduced by Jaillet and by Bertsimas as the…

19 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.1311217191902.1311217191902.131121719190Open Problem

The regular theorem's proof has been accepted by Prove2Me.

5 thms3 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

A Discrete Convex Min-Max Formula for Box-TDI Polyhedra: Min-Max Theorem for Separable Discrete Convex Functions over Integral Points of a Box-TDI PolyhedronResearch Paper

Minimizing a separable convex function over the integral points of a polyhedron is a recurring problem in combinatorial optimization: resource allocation, minimum-cost flows with convex costs, and the "fair" or "decreasingly minimal" integral elements studied by Frank and Murota all have this form. When the polyhedron is described by a totally unimodular…

17 thms3 active usersReviewed
🏆Completed
Group TheoryRepresentation Theory·Captain: mikedeng1

Comparison of Gelfand-Tsetlin Bases for Alternating and Symmetric Groups: The Recursively Defined Vectors u_α Form a Gelfand–Tsetlin Basis of Each Irreducible Representation of A_nResearch Paper

A Gelfand–Tsetlin basis of a representation of the last group in a tower G1⊂G2⊂⋯⊂GnG_1 \subset G_2 \subset \cdots \subset G_nG1​⊂G2​⊂⋯⊂Gn​ is a basis adapted to every restriction at once: each basis vector spans a line that is cut out by the isotypic decompositions at all levels k=1,…,nk = 1, \dots, nk=1,…,n. When every restriction Gk↓Gk−1G_k \downarrow G_{k-1}Gk​↓Gk−1​ is multiplicity-free, these lines are…

10 thms3 active usersReviewed
PreviousPage 16 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