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
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Algorithms for Max-Min Share Fair Allocation of Indivisible Chores: Greedy Round-Robin Gives Every Agent at Least (2 − 1/N) Times Her Max-Min Share, and the Factor Cannot Be ImprovedResearch Paper

Many allocation problems distribute work rather than benefits: household and office tasks, teaching loads, shifts, maintenance duties, or jobs assigned to parallel machines. Each item is a chore, which every agent would rather not receive, and chores cannot be split. Under indivisibility an exactly fair split usually does not exist, so the fair-division…

11 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear OptimizationOperations Research·Captain: mikedeng1

New Combinatorial Insights for Monotone Apportionment: House-Monotone and Quota-Compliant Apportionments Are the Seat Counts of Extreme Points of a Network Flow LP with Lookahead Φ(p, H)Research Paper

An apportionment method distributes the HHH seats of a house among nnn states in proportion to their populations. Exact proportionality is impossible with integer seats, so methods are judged by axioms. Two axioms date back to the debates over the seats of the US House of Representatives. Quota compliance asks that each state receive its exact proportional…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

The Power of Adaptivity for Stochastic Submodular Cover: With Independent Items, r Rounds of Adaptivity Achieve Expected Cost O(Q^{1/r} log Q) Times the Optimal Fully Adaptive CostResearch Paper

In many sequential decision problems an unknown quantity is revealed only when paid for: a medical test, a sensor reading, a database query. Stochastic submodular cover is the common abstraction: items are probed one at a time at a cost, each probe reveals a random outcome, and probing stops once the revealed outcomes jointly reach a coverage target. It…

14 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

Semidefinite Approximations for Bicliques and Bi-Independent Pairs: For Every Bipartite Graph, h(G) ≤ ½√g(G) ≤ h₁(G) ≤ ½√g₁(G) ≤ ¼α(G)Research Paper

A biclique in a graph is a pair of disjoint vertex sets (A,B)(A,B)(A,B) in which every vertex of AAA is adjacent to every vertex of BBB. Maximum-edge bicliques model problems in product manufacturing lines and formal concept analysis; balanced bicliques arise in VLSI design and in the analysis of biological data; and the maximum product ∣A∣⋅∣B∣|A|\cdot|B|∣A∣⋅∣B∣ over…

11 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

How to Design a Stable Serial Knockout Competition: Scaling a Degree-Ordered Knockout Seeding on GF(2^k) by Each Nonzero Field Element Yields a Stable SKC on 2^k PlayersResearch Paper

A knockout tournament for n=2kn = 2^kn=2k players is played in kkk rounds: players are placed at the leaves of a complete binary tree, adjacent players meet in round 1, winners of adjacent matches meet in round 2, and the winner of round kkk, the final, wins the tournament. Who can meet whom, and in which round, is fixed entirely by the seeding, the order in which the…

6 thms2 active usersReviewed
🏆Completed
Linear algebraMachine Learning·Captain: mikedeng1

Geometric Deep Learning II: Every Linear Permutation-Equivariant Map on ℝⁿ Is a Linear Combination of the Identity and the Averaging Map (1/n)𝟙𝟙ᵀTextbook

Many learning problems take an unordered collection as input: the points of a point cloud, the particles of a physical system, the atoms of a molecule, the nodes of a graph. Storing such data in memory fixes an order of the elements, but the order carries no information, and a model whose output changes when the rows of its input are shuffled is answering a…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Feasible Bases for a Polytope Related to the Hamilton Cycle Problem: Every Ultimate Feasible Basis Is a Good Augmented Spanning Tree Whose Thick Arcs Form the Unique Perfect MatchingResearch Paper

A Hamilton cycle visits every vertex of a directed graph once and returns to its start. Finding one is a standard combinatorial optimization problem, and linear programming provides a way to study it through extreme points. Kalinowski and Mohammadian examine a polytope introduced for this purpose and ask what its feasible bases look like when a discount…

9 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

The Nature of Statistical Learning Theory III: The Growth Function Is Linear or LogarithmicTextbook

Statistical learning theory asks when minimizing the error on a finite sample also controls the error on unseen data. For a set of classifiers, the answer given by Vapnik and Chervonenkis is governed by a single combinatorial quantity: how many different ways the set can label ℓ\ellℓ points. Bounds on the generalization error of empirical risk minimization…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: Shuze Chen

A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach: Binary Search over all-pack Is a (1 + ε)-Approximation for Makespan on Uniform MachinesResearch Paper

Scheduling independent jobs on machines that run at different speeds, so that the last job finishes as early as possible, is one of the basic problems of scheduling theory. In the classification of Graham, Lawler, Lenstra and Rinnooy Kan it is denoted Q∥Cmax⁡Q\|C_{\max}Q∥Cmax​, the minimum makespan problem on uniform parallel machines. It is strongly NP-hard, so the…

15 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: Shuze Chen

Flows in Networks VII: Maximal Dynamic Flows from Temporally Repeated FlowsTextbook

Many transportation and evacuation questions ask how much can be shipped from a source to a sink within a time horizon, when every arc has both a capacity per period and a traversal time. Ford and Fulkerson posed this maximal dynamic flow problem in 1958 and solved it by a reduction that is now standard in network optimization: instead of solving a linear…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: Shuze Chen

Flows in Networks VIII: Flow Functions Realizable by TreesTextbook

In a communication or transportation network, a planner often needs not one maximal flow value but all of them: the largest amount that can be sent between every pair of locations. For an undirected network with nnn nodes there are n(n−1)/2n(n-1)/2n(n−1)/2 such values. In 1961, R. E. Gomory and T. C. Hu (Multi-terminal network flows, J. SIAM 9 (1961)) answered two questions…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: Shuze Chen

Flows in Networks VI: Zero-One Matrices with Zero TraceTextbook

An m×nm \times nm×n matrix of 000's and 111's is the incidence matrix of mmm sets against nnn elements, or the adjacency matrix of a bipartite graph, or, when m=nm = nm=n, the adjacency matrix of a directed graph on nnn nodes. The first question about such matrices is when one exists with prescribed row and column sums. Gale (1957) and Ryser (1957) answered it independently with…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: Shuze Chen

Flows in Networks II: Maximal Flow Value as a Function of Two Arc CapacitiesTextbook

The value of a maximal flow is the basic output of network-flow models of transport, communication and supply systems. A planner who can enlarge the capacity of a link wants to know what the enlargement buys. For a single link the answer is simple. For two links it is a question about interaction: does enlarging one make enlarging the other more valuable…

9 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: Shuze Chen

Flows in Networks I: The Max Flow Min Cut TheoremTextbook

The maximal flow problem asks how much of a commodity can be sent from one node of a network to another when every arc has a capacity. It was posed in the 1950s in the study of rail networks, and its answer, the max flow min cut theorem of L. R. Ford, Jr. and D. R. Fulkerson, became the organizing result of combinatorial optimization: the bottleneck of a…

11 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: Shuze Chen

Flows in Networks III: The Circulation TheoremTextbook

Many questions in operations research and combinatorics ask whether a system of linear inequalities on a network has a solution: can the demands at a set of warehouses be met from the supplies at a set of factories through roads of limited capacity; is there a nonnegative matrix with bounded entries whose row and column sums lie between given limits; can a…

8 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

A Class of Dissimilarity Semimetrics for Preference Relations: Axiomatic Characterization of the µ-Top-Difference Semimetrics on Acyclic OrdersResearch Paper

How far apart are two preferences? Distance functions on preference relations are used to deduce a consensus ranking from a collection of individual preferences. The classical answer is the Kemeny–Snell metric (Kemeny and Snell 1962), proposed axiomatically for linear orders and extended by Bogart (1973) to partial orders. It counts rank reversals between…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Queueing with Negative Network Effects: Closed-Form Joint Law of the Later Arrivals Met and the Queue-Filling Arrivals for a Customer Joining an M/M/c/n Queue at Position jResearch Paper

In many service systems a waiting customer is harmed not only by the time spent in line but also by the other customers met there. Contagion in a clinic, a pharmacy or a government office during an epidemic is the motivating example of Hassin, Meilijson and Perlman, Queueing with Negative Network Effects (SSRN 4097977, 2022; Manufacturing & Service…

7 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Bounding Residence Times for Atomic Dynamic Routings: If No Later Entrant Leaves the Subnetwork First, an Agent Exits by Time r0 plus the Longest Path Length plus the Earlier Agents Still InsideResearch Paper

In atomic dynamic routing, indivisible agents (vehicles, packets, travellers) enter a network over time and travel along fixed routes. Each road admits a limited number of agents per unit of time, so agents queue at its entrance. A basic question for traffic models, packet-switching networks and dynamic routing games is how long an agent can stay in the…

10 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation: Recursive Probabilistic Serial Is Ex-Ante Envy-Free and Ex-Post Envy-Free up to One GoodResearch Paper

Many allocation problems hand out indivisible goods without money: course seats, shifts, donated food, inherited items. An integral allocation of such goods can rarely be envy-free. With one good and two agents, someone always envies. The standard remedies are of two kinds. Randomization restores fairness in expectation: the probabilistic serial rule of…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time: A Maximal Minimum k-Partition's First Part Is the Source-Maximal Minimum (S, T)-Terminal Cut for Some |S| = 2k − 2Research Paper

The hypergraph k-cut problem asks for a least-cost way to split the vertices of a hypergraph into kkk nonempty groups. An edge of a hypergraph may contain more than two vertices, so the graph version does not capture the behavior of every input. For fixed kkk, randomized polynomial-time algorithms for hypergraph k-cut were known before the deterministic result…

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

Maximizing Sequence-Submodular Functions and Its Application to Online Advertising: Any α-Greedy Sequence Achieves 1 − 1/e^α of the Optimum of a Non-Decreasing Sequence-Submodular FunctionResearch Paper

Many allocation problems in online advertising are decisions about order, not only about membership. A search engine that rewrites an incoming query into one of several ad-matching configurations, or a publisher that runs a sequence of ad allocations over a day, extracts revenue that depends on which configurations are used and on the order in which they…

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

Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice: A Dynamic Program Computes the Exact Choice Probabilities of the Mallows ModelResearch Paper

An assortment decision determines which products a customer can buy, but its expected revenue depends on the probability that the customer chooses each offered product. A distribution over complete rankings gives a direct model: sample a customer's ranking, then take the highest-ranked product in the assortment. The resulting choice probabilities are easy…

7 thms2 active usersReviewed
🏆Completed
Quantum Error CorrectionQuantum Information·Captain: Winningatmath

Bivariate-Bicycle Codes: New [[336,20,12]] and [[360,24,12]] Codes and Certified DistancesResearch Paper

A quantum memory stores logical qubits in many physical qubits so that errors can be detected and corrected. The overhead of doing so, measured by how many physical qubits are spent per logical qubit at a given error-correcting power, is one of the main costs of fault-tolerant quantum computation. Bivariate-bicycle (BB) codes are currently the leading…

63 thms2 active usersReviewed
🏆Completed
Complexity Theory·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Classical Quadratic BoundResearch Paper

Certify the classical quadratic separation between sensitivity and block sensitivity: α≥2\alpha\ge2α≥2.

4 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue 4: The k-SS Mechanism Is Ex-Post IC-IR and a (2 log k + 4)-Approximation to Welfare for Strong-SOS ValuationsResearch Paper

In auctions with interdependent values, the value an agent assigns to an outcome depends not only on her own private information but on the information of the others: a bidder for drilling rights values a tract according to every bidder's geological survey, and a buyer of a used asset values it according to every inspector's report. Each agent observes only…

10 thms2 active usersReviewed
PreviousPage 18 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