Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Graph Theory

699 missions · 311 completed

Missions

Open388Completed311All699
🏆Completed
Linear OptimizationOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) II: When Least-Cost Dipaths Exist, the Shortest Dipath Cost Equals the Maximum Feasible PotentialTextbook

The shortest path problem asks, in a network whose links carry costs, for a cheapest directed route from a fixed origin to every other point. It is the basic subroutine of network optimization: minimum-cost flow algorithms, matching algorithms and many dynamic programs call it repeatedly, and arc costs that are negative arise naturally, for instance as −log⁡-\log−log…

22 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: iris

Combinatorial Optimization (Cook et al.) V: A Minimum-Cost Flow Problem with Integral Demands and Capacities Has an Integral Optimal SolutionTextbook

The minimum-cost flow problem is the common roof over shortest paths, maximum flows, transportation and assignment problems, and transshipment. It asks for the cheapest way to move a commodity through a directed network so that every node receives its prescribed net amount and no arc carries more than its capacity. Its central structural fact is…

21 thms2 active usersReviewed
EconomicsOperations ResearchProbability·Captain: iris

Exit Spirals in Coupled Networked Markets: Two Independent Random Networks with Simple Complementarities Lose All Activity Discontinuously at a Critical ShockResearch Paper

Financial intermediaries often need access to two markets at once. A dealer that funds bond inventory in the repo market cannot operate without access to the collateral market, and the reverse also holds. Aymanns, Georg and Golub (SSRN 2881814; Operations Research, doi:10.1287/opre.2023.2439) model this coupling as a participation game on a multilayer…

19 thms2 active usersReviewed
CombinatoricsOptimization·Captain: iris

Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph: Isolated Nodes Keeping ϑ-Rank 1 for Odd Cycles and ComplementsResearch Paper

The stability number α(G)\alpha(G)α(G) of a graph, the largest size of a set of pairwise non-adjacent nodes, is NP-hard to compute. Motzkin and Straus showed that it is the value of a copositive program, α(G)=min⁡{t:t(AG+I)−J copositive}\alpha(G)=\min\{t: t(A_G+I)-J \text{ copositive}\}α(G)=min{t:t(AG​+I)−J copositive}. That turns approximating α(G)\alpha(G)α(G) into approximating the cone of copositive matrices. Parrilo (2000 thesis)…

31 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOperations Research·Captain: mikedeng1

Correlation Clustering: Algorithm Cautious Is a Constant-Factor Approximation for Minimizing DisagreementsResearch Paper

In many clustering tasks the data come as pairwise judgements rather than as points in a metric space: a classifier says, for each pair of documents, whether they refer to the same entity or not. Correlation clustering asks for a partition that agrees with as many of these judgements as possible, without fixing the number of clusters in advance. The problem…

12 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Differences-in-Neighbors for Network Interference in Experiments: The DN Estimator Has Bias at Most d²ε Under ε-Smooth Neighborhood InterferenceResearch Paper

Online platforms, social networks and marketplaces run randomized experiments (A/B tests) to estimate the effect of a new feature. The standard analysis assumes that one unit's treatment does not affect another unit's outcome. On a network this fails: a treated user changes what their friends see, a treated seller changes what competing sellers sell. The…

9 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Pure Nash Equilibria and Best-Response Dynamics in Random Games: Best-Response Dynamics Reaches a Pure Nash Equilibrium for All Large N When the Tie Probability Is SmallResearch Paper

A pure Nash equilibrium (PNE) of a game is a strategy profile from which no player gains by a unilateral deviation. Unlike mixed equilibria, pure equilibria need not exist, and even when they do they can be hard to find: computing an equilibrium is PPAD-complete in general (Daskalakis, Goldberg & Papadimitriou 2009). The simplest learning procedure that…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations 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
Linear algebraMachine Learning·Captain: mikedeng1

Geometric Deep Learning V: A Degree-r Polynomial Filter Σ αₖΔᵏX of a Graph Laplacian Is Localised in r-Hop NeighbourhoodsTextbook

Graph neural networks and geometric learning on meshes rely on operators that combine the features of a node with those of its neighbours. The graph Laplacian is the oldest such operator: it is the discrete analogue of the Laplace–Beltrami operator of a surface, and its eigenvectors play the role of a Fourier basis on a graph. Early spectral graph networks (…

8 thms2 active usersReviewed
🏆Completed
Group TheoryMachine Learning·Captain: mikedeng1

Geometric Deep Learning VII: The E(3)-Equivariant Message-Passing Layer Leaves Node Features Invariant and Moves Coordinates with Every Rigid MotionTextbook

Many graphs that graph neural networks (GNNs) are applied to are embedded in space. In a molecular graph the nodes are atoms, and each atom carries both chemical information (its type) and its three-dimensional position. A prediction about the molecule (an energy, a binding affinity) must not depend on where the molecule sits or how it is oriented, and a…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear 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
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems: Recursive Greedy Is an O(log k/log log k)-Approximation in (n log B)^O(log^(1+ε) k) TimeResearch Paper

Directed network design asks which connections can be bought under a limited budget when traffic follows the directions of arcs. In directed tree orienteering, the reward comes from vertices reached by a rooted directed tree. The submodular version allows the reward of a new vertex to depend on which vertices have already been reached. This captures…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear 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
CombinatoricsOperations 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
CombinatoricsOperations 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
CombinatoricsOperations 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
CombinatoricsLinear 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
CombinatoricsLinear 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
Linear OptimizationOperations Research·Captain: mikedeng1

Traceability Technology Adoption in Supply Chain Networks: The Least-Costly Seed Set Problem Has an Exact Linear Programming Reformulation Whose Size Is Fixed-Parameter Tractable in TreewidthResearch Paper

Supply-chain traceability depends on firms adopting a technology together. A firm may benefit only after enough other firms in a shared supply chain have adopted; a supply chain may in turn become traceable only when a threshold number of its firms participate. Selecting firms to seed therefore couples many local adoption decisions. Blaettchen, Calmon, and…

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

The Buck-Passing Game: Every Deterministic Buck-Passing Game Has a Prior-Free Pure Nash EquilibriumResearch Paper

In a buck-passing game, each participant chooses who will receive a task, burden, or token next. The eventual share of time spent holding it depends on every participant's choice. This makes a small network into a game: a local change of one outgoing edge can alter the long-run burden across an entire part of the network. Cominetti, Quattropani, and…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations 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
Quantum Error CorrectionQuantum Information·Captain: mikedeng1

Decoding Quantum Tanner Codes: The Parallel Decoder Corrects Every Error of Weight Linear in the Code Length in Logarithmically Many RoundsResearch Paper

Quantum computers must correct errors faster than they accumulate, and quantum low-density parity-check (LDPC) codes are the leading candidates for doing so with little overhead: every check involves a bounded number of qubits, so syndromes can be measured by local circuits. In 2021–2022 the first asymptotically good quantum LDPC codes appeared, with…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations 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
Operations ResearchProbability·Captain: mikedeng1

A Dynamic Contagion Risk Model with Recovery Features: Fluid Limit for the Final Fraction of Failed Nodes in Threshold Contagion with Growth on the Configuration ModelResearch Paper

Financial networks, supply chains and contact networks share a failure mode: a node fails when enough of its counterparties have failed, and its failure in turn weakens its own counterparties. Threshold contagion on random graphs is the standard mathematical model of this. Amini, Cont and Minca (Resilience to contagion in financial networks, Mathematical…

10 thms2 active usersReviewed
Quantum Error CorrectionQuantum Information·Captain: mikedeng1

Quantum Tanner Codes 1: On a Ramanujan Left-Right Cayley Complex with Robust Dual Tensor Codes, the Quantum Tanner Code Has Rate at Least (1−2ρ)² and Distance at Least δn/(4Δ^{3/2+ε})Research Paper

An error-correcting code protects information by adding redundancy. A quantum code must also account for two kinds of errors, commonly called XXX and ZZZ errors. Quantum low-density parity-check codes use checks that each touch only a bounded number of qubits, while each qubit participates in only a bounded number of checks. Such locality matters when the…

9 thms2 active usersReviewed
PreviousPage 19 of 28Next

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