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
Operations ResearchOptimization·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 8: When Both Agents Minimize a Maximum of Regular Costs, There Are at Most n_A·n_B + 1 Nondominated PairsResearch Paper

In many production and service settings a single resource is shared by several parties, each judging the outcome only by how its own work is treated. Multi-agent scheduling studies this situation. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced the two-agent single-machine model in which two agents, A and B, each own a set…

7 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

A c^k n 5-Approximation Algorithm for Treewidth 3: A Rooted Tree with a Measure μ ≥ 1, Superadditive over Children and Shrinking by C < 1 Along Each Edge, Has at Most (1+1/(1−C))μ(r)−1 NodesResearch Paper

Treewidth measures how closely a graph resembles a tree. Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk (SIAM J. Comput. 45(2), 2016) study an algorithm for producing tree decompositions. Its headline result is algorithmic; this mission formalizes one combinatorial lemma used in its analysis.

8 thms2 active usersReviewed
🏆Completed
Mathematical Physics·Captain: LG

't Hooft 1993: Dimensional Reduction in Quantum GravityResearch Paper

In the 1993 essay Dimensional Reduction in Quantum Gravity (arXiv:gr-qc/9310026), G. 't Hooft argued that, once gravitational collapse is taken into account, the number of quantum states available to a region of space grows with the area of its boundary rather than with its volume. The essay is the origin of what is now called the holographic principle (deve…

7 thms2 active usersReviewed
🏆Completed
AlgebraDiscrete GeometryLinear algebra·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 3: A Maximum h-Scattered Subspace of Dimension rn/(h + 1) Meets Every Hyperplane in Dimension Between rn/(h + 1) − n and rn/(h + 1) − n + hResearch Paper

Scattered subspaces are a central object of finite geometry. An Fq\mathbb F_qFq​-subspace UUU of an rrr-dimensional vector space over Fqn\mathbb F_{q^n}Fqn​ defines an Fq\mathbb F_qFq​-linear set of the projective space PG(r−1,qn)\mathrm{PG}(r-1,q^n)PG(r−1,qn), and when UUU is scattered this linear set has the largest possible number of points for its rank. Maximum scattered subspaces give rise to…

18 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOptimal Transport·Captain: mikedeng1

Computational Optimal Transport IV: The Support Graph of an Extreme Point of the Transportation Polytope U(a, b) Has No Cycle, Hence at Most n + m − 1 Nonzero EntriesTextbook

Discrete optimal transport between two histograms is a linear program. Its feasible set, the transportation polytope, has been studied since Hitchcock (1941) and Kantorovich, and the structure of its vertices underlies the classical algorithms for the problem: the north-west corner rule produces a vertex, and the network simplex moves from vertex to vertex.…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport I: For Uniform Marginals 1/n Some Permutation Matrix Solves the Kantorovich Problem, so the Relaxation of Optimal Assignment Is TightTextbook

An assignment problem pairs each of nnn sources with exactly one of nnn destinations while minimizing a specified cost. A permutation records those pairings. The number of permutations grows as n!n!n!, so a direct search quickly becomes impractical. In discrete optimal transport, the same data can be placed in a linear optimization problem over nonnegative…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport VI: On Termination the Auction Algorithm Returns an Assignment Whose Cost Is Within nε of the OptimumTextbook

The optimal assignment problem asks for a one-to-one matching of nnn points to nnn objects of least total cost. It is the discrete optimal transport problem between two uniform measures with the same number of atoms, and by the Birkhoff–von Neumann theorem it coincides with the Kantorovich linear program on that instance (Peyré and Cuturi, Computational Optimal…

5 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Generation and Properties of Snarks 4: Every 3-Edge-Colourable Cubic Graph with m Edges Has a Cycle Cover of Total Length at Most 4m/3Research Paper

A cycle cover of a graph is a collection of cycles that together use every edge at least once. Covering the edges of a network by closed tours appears in routing and inspection problems (the Chinese postman problem is the closed-walk version), and the minimum total length of a cycle cover is a classical extremal parameter of bridgeless graphs. Alon and…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Generation and Properties of Snarks 1: Inserting an Edge Between Two Edges of One Bicoloured Cycle of a 3-Edge-Coloured Cubic Graph Yields a 3-Edge-Colourable GraphResearch Paper

A snark is an uncolourable, cyclically 4-edge-connected cubic graph of girth at least 5: a cubic graph whose edges cannot be properly coloured with three colours, and which is not reducible to a smaller such graph by an elementary operation. Snarks are the critical cases for several of the central conjectures of graph theory, among them the cycle double…

8 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: xuanji

Deterministic APSP in O(n^2.995561) time on a Word RAMResearch Paper

All-pairs shortest paths (APSP) asks for the exact distance between every ordered pair of vertices in an nnn-vertex weighted directed graph. Floyd–Warshall solves it in O(n3)O(n^3)O(n3) time, and for decades no algorithm beat n3−δn^{3-\delta}n3−δ for any constant δ>0\delta>0δ>0 on graphs with polynomially bounded integer weights. In 2026, Alman and Vassilevska Williams (arXiv:2610.06…

5 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems: Biased-Fitness Survivor Selection Never Removes an Elite Individual Outside XResearch Paper

Genetic algorithms with local search ("memetic" or hybrid genetic algorithms) are among the most effective heuristics for vehicle routing. Their recurring weakness is premature convergence: selection and local improvement both favour good individuals, so the population fills with near-copies of a few solutions and the search stalls. Vidal, Crainic,…

5 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Hardness of Approximating Flow and Job Shop Scheduling Problems 2: Coloring Reduction Gap: Makespan 2L·lb if G Is L-Colorable, Independent Set of Size n/(8L) if Half the Jobs Finish by L·lbResearch Paper

In the job shop problem, jobs are sequences of operations, each to be processed on a given machine for a given time, and the goal is a schedule of minimum makespan (the time at which the last job finishes). Two numbers bound the optimum from below: the longest job and the most loaded machine. Their maximum is written lb\mathrm{lb}lb. The best approximation…

12 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

A Branch-and-Cut Algorithm for the Dial-a-Ride Problem: The Generalized Order-Matching Inequality x(H) + Σ x(T_h) ≤ |H| + Σ|T_h| − 2m Is Valid for Every Feasible Route PlanResearch Paper

The dial-a-ride problem (DARP) asks for minimum-cost vehicle routes that carry users from individual pick-up points to individual drop-off points, subject to vehicle capacities, time windows, route durations and a bound on each user's ride time. It models door-to-door transport for elderly and disabled people, shared taxis and on-demand microtransit.…

7 thms2 active usersReviewed
🏆Completed
Probability·Captain: marwahaha

Renewal and changes of law for critical honeycomb walksOpen Problem

An external force rewards self-avoiding walks whose endpoints move in a chosen direction. The source studies critical honeycomb scaling; the available formal goal supplies existence of the forced free-energy limit. The source is OpenAI's September 2026 manuscript.

4 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: marwahaha

A power improvement in the Heilbronn triangle lower boundOpen Problem

The Heilbronn triangle problem asks how large the smallest triangle in an nnn-point set can be. A positive improvement in the exponent would contradict bounds at every scale arbitrarily close to n−2n^{-2}n−2. The source is OpenAI's September 2026 manuscript.

5 thms2 active usersReviewed
🏆Completed
Probability·Captain: marwahaha

The sharp terminal leave in random triangle removalOpen Problem

Random triangle deletion constructs a partial triangle packing. Its terminal uncovered edges measure how efficiently this process covers pairs, and the source seeks the leading constant rather than only the growth exponent. The source is OpenAI's September 2026 manuscript.

5 thms2 active usersReviewed
🏆Completed
Captain: marwahaha

A Counterexample to the Infinite Matroid Packing/Covering ConjectureOpen Problem

Finite matroid packing and covering principles connect disjoint spanning sets with independent covers. The source seeks a concrete obstruction to extending the unrestricted principle to infinite ground sets. The source is OpenAI's September 2026 manuscript.

59 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: marwahaha

A logarithmic independence bound for clique-free graphsOpen Problem

Excluding a fixed clique should force independent sets larger than those guaranteed by average degree alone. The source asks for the full logarithmic improvement uniformly across graph sizes. The source is OpenAI's September 2026 manuscript.

25 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: marwahaha

Paired states and Hamiltonian cycles in cubic bipartite planar graphsOpen Problem

A spanning subgraph in which every vertex has degree two may split into several cycles. Barnette’s question asks when planarity, bipartiteness, and connectivity force those vertices onto one cycle. The source is OpenAI's September 2026 manuscript.

53 thms2 active usersReviewed
🏆Completed
Probability·Captain: marwahaha

Talagrand’s discrete-convexity conjectureOpen Problem

High probability under independent coordinate sampling need not give a family any closure under unions. Discrete convexity asks whether a bounded number of its members nevertheless cover most sets in the stronger sense of inexpensive containment certificates. The source is OpenAI's September 2026 manuscript.

20 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: marwahaha

A counterexample to Sidorenko's conjectureOpen Problem

Graph homomorphism inequalities compare the frequency of a fixed pattern with what edge density predicts. The mission asks for one finite host graph violating the proposed bound for a specified bipartite pattern. The source manuscript presents the surrounding research claim.

6 thms2 active usersReviewed
🏆Completed
Graph Theory·Captain: marwahaha

A linear list-coloring bound in terms of the Hadwiger numberOpen Problem

List coloring permits each vertex to have different allowable colors. The mission asks whether the size of the largest clique minor still controls the required list size up to a universal linear factor. The source manuscript presents the surrounding research claim.

9 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: marwahaha

A translational tile with no fully periodic tiling in dimension threeOpen Problem

A tile may admit a translation tiling while forcing every such tiling to lack a full lattice of periods. The mission asks for this phenomenon in dimension three and its persistence under Euclidean thickening. The source manuscript presents the surrounding research claim.

2 thms2 active usersReviewed
🏆Completed
Analysis·Captain: marwahaha

The dyadic case of the Erdős similarity conjectureOpen Problem

Finite patterns fit inside positive-measure sets after a sufficiently small affine change. The dyadic similarity problem asks whether one particular infinite pattern can be excluded even from compact sets of nearly full measure. The source manuscript presents the surrounding research claim.

48 thms2 active usersReviewed
🏆Completed
Analysis·Captain: marwahaha

Asymptotically minimal maxima of real Littlewood polynomialsOpen Problem

Choosing real signs in a polynomial controls how much its values can peak around the unit circle. The target seeks asymptotically optimal maximum modulus at every sufficiently large length. The source manuscript presents the surrounding research claim.

26 thms2 active usersReviewed
PreviousPage 20 of 29Next

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