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: 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
🏆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
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Linear Programming and Community Detection 7: The LP Relaxation Fails w.h.p. in the Logarithmic-Degree SBMResearch Paper

The stochastic block model (SBM) is the standard benchmark for community detection: a random graph whose vertices are split into hidden communities, with denser connections inside a community than across. For two equal communities, the best possible estimator of the hidden partition is the minimum bisection problem, which is NP-hard in the worst case. Its…

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

Linear Programming and Community Detection 4: A Distance-Based Condition Under Which the Metric LP Relaxation Fails to Recover the Planted BisectionResearch Paper

The minimum bisection problem asks, for a graph on an even number nnn of vertices, for a split of the vertices into two halves that cuts as few edges as possible. It is NP-hard, and it is the maximum a posteriori estimator for the two-community stochastic block model (SBM), the standard benchmark for community detection (Abbe, 2018). Convex relaxations are…

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

Load Balancing Under Strict Compatibility Constraints 2: Random Graphs with Server Degree c(N) → ∞ and Nc(N)/(M(N) ln N) → ∞ Are Almost Surely Proportionally Sparse and SubcriticalResearch Paper

In large data centres, an incoming task often cannot run on every server: its data, software or licences sit on only some of the machines. Such strict compatibility constraints are modelled by a bipartite graph between task types (dispatchers) and servers. For the fully flexible system, in which every task can go to every server, the JSQ(ddd) policy (sample ddd…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Linear Programming and Community Detection 2: The Minimum Bisection Recovery Condition d_in − d_out > n/4 − 1 Is TightResearch Paper

The minimum bisection problem partitions an even-sized graph into two equally large groups while cutting as few edges as possible. In community detection, a graph may have been generated around an unknown, balanced pair of groups. The statistical question is whether an optimizer can identify that planted partition from the edges. Before studying random…

3 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Linear Programming and Community Detection 1: Minimum Bisection Recovers the Planted Bisection When d_in − d_out > n/4 − 1Research Paper

Community detection asks for a partition of the vertices of a graph into groups that are densely connected inside and sparsely connected across. In its simplest form there are two communities of equal size, and the natural combinatorial formulation is the minimum bisection problem: among all ways of splitting the vertex set into two halves, find one that…

5 thms2 active usersReviewed
🏆Completed
Information TheoryProbabilityStatistics·Captain: mikedeng1

Partial Recovery in the Graph Alignment Problem I: If D(P‖Q)/α = o(log n/n), No Algorithm Recovers a Fraction α of a Correlated Erdős–Rényi AlignmentResearch Paper

Graph alignment asks for the correspondence between the vertices of two graphs that are noisy copies of each other with hidden labels. It arises in the de-anonymization of social networks, where an anonymized friendship graph is matched against a public one (Narayanan–Shmatikov 2009), and in computational biology, where protein–protein interaction networks…

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

Lightning Network Economics: Topology I: A Cost-Minimizing Lightning Network Is Bipartite, with All Net Flows from One Side to the OtherResearch Paper

The Lightning Network (LN) is a second-layer payment system for Bitcoin. Instead of recording every payment on the blockchain, two parties lock funds in a payment channel and settle many payments off-chain; payments between parties without a common channel are routed along paths of channels. Locking funds is costly, and the amount a channel needs grows with…

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

Flow Allocation Games 2: In Unit-Ranking Games Every Strong Equilibrium Has Total Flow at Least the Optimum Divided by the Min-Max Cycle Length dResearch Paper

Financial networks are webs of liabilities: firm uuu owes firm vvv an amount c(u,v)c_{(u,v)}c(u,v)​, and every firm holds some external assets. When firms cannot pay in full, how much money actually moves through the network depends on how each firm splits its available funds among its creditors. The classical clearing model of Eisenberg and Noe (2001) fixes this split by a…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Shortest Paths in Graphs of Convex Sets I: The Perspective Mixed-Integer Convex Program (5.5) Has the Same Optimal Value as the Shortest-Path Problem in a Graph of Convex SetsResearch Paper

Many planning problems combine a discrete choice with a continuous one. A robot moving through a cluttered room chooses which free regions to traverse and where exactly to cross between them; a vehicle chooses a sequence of operating modes and a trajectory within each mode. Marcucci, Umenberger, Parrilo and Tedrake (arXiv:2101.11565, SIAM J. Optim. 2024, doi…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: mikedeng1

Three Conjectures in Extremal Spectral Graph Theory 2: For Large n, K₂ + Pₙ₋₂ Is the Unique Planar Graph on n Vertices of Maximum Spectral Radius (Boots–Royle / Cao–Vince Conjecture)Research Paper

The spectral radius of a graph, the largest eigenvalue of its adjacency matrix, measures how densely and how unevenly the edges of the graph are distributed. Asking which graph in a class maximizes it is a spectral analogue of the extremal question "which graph in the class has the most edges". For planar graphs the question has a long history in spectral…

21 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: mikedeng1

Three Conjectures in Extremal Spectral Graph Theory 1: For Large n, K₁ + Pₙ₋₁ Is the Unique Outerplanar Graph on n Vertices of Maximum Spectral Radius (Cvetković–Rowlinson Conjecture)Research Paper

The spectral radius λ1(G)\lambda_1(G)λ1​(G) of a graph GGG, the largest eigenvalue of its adjacency matrix, is a standard measure of how densely and how centrally a graph is connected. A classical theme of spectral graph theory asks, for a natural family of graphs, which member of the family on nnn vertices maximizes λ1\lambda_1λ1​. For planar graphs this question was raised…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: mikedeng1

Three Conjectures in Extremal Spectral Graph Theory 3: For Large n, a Connected n-Vertex Graph Maximizing Spectral Radius Minus Average Degree Is a Pineapple GraphResearch Paper

How far is a graph from being regular? Several numerical irregularity measures answer this question, and spectral graph theory supplies a natural one. For a graph GGG with nnn vertices and e(G)e(G)e(G) edges, the largest eigenvalue λ1(G)\lambda_1(G)λ1​(G) of the adjacency matrix is always at least the average degree d(G)=2e(G)/nd(G) = 2e(G)/nd(G)=2e(G)/n, with equality exactly when GGG is regular. The…

13 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityStochastic Systems·Captain: mikedeng1

Separation of Time-Scales and Model Reduction for Stochastic Reaction Networks 1: The Balance Condition for Linear Combinations of Species Decomposes over Strongly Connected ComponentsResearch Paper

A stochastic reaction network tracks the counts of chemical species as reactions occur. Different species and reaction rates may grow at different powers of a large system-size parameter. Kang and Kurtz's model-reduction paper uses these powers to identify candidate time scales and combinations of species that can remain bounded. Before a reduced model can…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsGeometry & Topology·Captain: mikedeng1

Planar Graphs Have Bounded Queue-Number 2: Every Graph of Euler Genus g Has Queue-Number at Most 4g + 49Research Paper

A queue layout of a graph places its vertices on a line and splits its edges into classes, called queues, so that inside one queue no edge is nested inside another. The minimum number of queues is the queue-number. Queue layouts were introduced by Heath, Leighton and Rosenberg (1992) and Heath and Rosenberg (1992) as the dual of stack layouts (book…

13 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Planar Graphs Have Bounded Queue-Number 1: Every Planar Graph Has a 49-Queue LayoutResearch Paper

A queue layout represents a graph by placing its vertices in a line and assigning edges to queues. The order and assignment must prevent nested edges from sharing a queue. This gives a graph parameter that measures how much queue capacity is needed for a particular graph. Heath, Leighton, and Rosenberg asked whether one fixed number of queues suffices for…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: mikedeng1

A Harary-Sachs Theorem for Hypergraphs: The Codegree-d Coefficient of the Characteristic Polynomial of a k-Graph as a Weighted Sum over Its Veblen InfragraphsResearch Paper

The characteristic polynomial of an ordinary graph records spectral information in coefficients that can also be described by finite graph configurations. The classical Harary–Sachs theorem is an instance of this connection. For a uniform hypergraph, the adjacency object is a tensor rather than a matrix, and its characteristic polynomial is defined through…

45 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

A c^k n 5-Approximation Algorithm for Treewidth 2: X Is a Balanced S-Separator iff V(G)∖X Splits into Three Mutually Non-Adjacent Parts Each Holding at Most |S|/2 Vertices of SResearch Paper

The paper of Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk (2016) has an algorithmic headline. This mission concerns one of its finite graph lemmas, Lemma 2.9. The lemma translates a condition phrased separately for every connected component into a condition on three vertex sets. A reader of graph decompositions encounters both forms:…

6 thms2 active usersReviewed
🏆Completed
Markov ChainOperations ResearchProbability·Captain: mikedeng1

Routing Betweenness Centrality: Under Source-Oblivious Loop-Free Routing, the Betweenness of a Node Sequence Is a Sum over Targets of Chained Pairwise DependenciesResearch Paper

Betweenness centrality measures how much of the communication in a network passes through a node. Freeman's original measure (Freeman 1977) counts the fraction of shortest paths between each pair of nodes that pass through it, and Brandes' algorithm (Brandes 2001) made it computable on large graphs. Variants replace shortest paths by maximum flows (Freeman,…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear 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
Combinatorics·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
CombinatoricsTheoretical 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
PreviousPage 9 of 13Next

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