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
AlgebraRepresentation Theory·Captain: mikedeng1

Supersymmetric Polynomials and the Center of the Walled Brauer Algebra: When B_{r,s}(δ) Is Semisimple, Supersymmetric Polynomials in the Jucys–Murphy Elements Generate Its CenterResearch Paper

The walled Brauer algebra Br,s(δ)B_{r,s}(\delta)Br,s​(δ) is the centralizer algebra of mixed Schur–Weyl duality: for δ=n\delta=nδ=n it acts on the mixed tensor space V⊗r⊗(V∗)⊗sV^{\otimes r}\otimes (V^*)^{\otimes s}V⊗r⊗(V∗)⊗s of V=CnV=\mathbb C^nV=Cn and commutes with gln\mathfrak{gl}_ngln​, and for δ=m−n\delta=m-nδ=m−n it plays the same role for the general linear supergroup GL(m∣n)GL(m|n)GL(m∣n). Its representation theory has been…

21 thms2 active usersReviewed
AlgebraRepresentation Theory·Captain: mikedeng1

On Central Idempotents in the Brauer Algebra: The Equation uX = −u Is Uniquely Solvable in Orbit Sums with Coefficients in K, and 1 + X Is the Splitting Idempotent of J_n(ℓ)Research Paper

The Brauer algebra packages pairings of points into an algebra whose multiplication records how pairings join when diagrams are stacked. It was introduced by Brauer as the centralizer algebra of orthogonal and symplectic groups acting on tensor powers of their natural representation (Brauer 1937), and is semisimple for generic δ\deltaδ (Wenzl 1988). It…

8 thms2 active usersReviewed
AlgebraRepresentation Theory·Captain: mikedeng1

On the Blocks of the Walled Brauer Algebra: In Characteristic Zero, Two Simple Modules Lie in the Same Block Exactly When Their Weights Lie in One Orbit of the ρ(δ)-Shifted Dot Action of Σ_{r+s}Research Paper

Let VVV be the natural representation of GLnGL_nGLn​ and V∗V^*V∗ its dual. The walled Brauer algebra Br,s(δ)B_{r,s}(\delta)Br,s​(δ) describes the endomorphisms of mixed tensor space V⊗r⊗V∗⊗sV^{\otimes r}\otimes V^{*\otimes s}V⊗r⊗V∗⊗s that commute with GLnGL_nGLn​, through mixed Schur–Weyl duality. It was introduced in this role independently by Turaev, Koike and…

17 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
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Polyhedral Clinching Auctions for Two-Sided Markets: An Incentive-Compatible, Individually Rational, Budget-Balanced, Pareto-Optimal Mechanism ExistsResearch Paper

Auctions in which bidders face budget constraints do not fit the classical quasi-linear theory: a bidder cannot pay more than a fixed amount, however much the goods are worth to him. For a single divisible good, Dobzinski, Lavi and Nisan showed that the adaptive clinching auction of Ausubel is incentive compatible, individually rational and Pareto optimal,…

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
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue 3: The k-HL Mechanism Is Ex-Post IC-IR and a (k+3)-Approximation to Welfare with k Signal ValuesResearch Paper

In many auctions a bidder's value for what she wins depends on information held by others. The value of an oil lease, a spectrum licence or a piece of art to one bidder depends on survey data, market forecasts or expert opinions that other bidders hold privately. The model of interdependent values (Milgrom and Weber, 1982) captures this: each agent iii holds…

9 thms2 active usersReviewed
PreviousPage 33 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