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
CombinatoricsDiscrete Geometry·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 3: Larman's Bound 2^(d−1)·n Holds in the Base AbstractionResearch Paper

The diameter of a polyhedron is the largest number of edges needed to travel between two vertices of its graph, its 1-skeleton. Whether this number is bounded by a polynomial in the dimension ddd and the number of facets nnn is a long-standing open question in polyhedral combinatorics; edge walks are the moves of vertex-following methods such as the simplex…

2 thms2 active usersReviewed
🏆Completed
CombinatoricsDiscrete Geometry·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 2: The Kalai–Kleitman Bound n^(1+log d) Holds in the Base AbstractionResearch Paper

The diameter of a polyhedron is the largest number of edges needed to travel between two vertices of its graph. Bounding that number from the dimension and the number of facets is a central question in polyhedral combinatorics because edge walks are the discrete moves available to many vertex-based optimization methods. The Kalai–Kleitman bound gives a…

2 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

On a Routing Problem: Successive Approximations from the Direct-Route Policy Decrease to the Unique Solution of the Routing Equation Within N − 1 IterationsResearch Paper

Finding the quickest route between two points of a road network is among the oldest problems of operations research. It is the subproblem inside vehicle routing, network flow and many dynamic programs. Richard Bellman's four-page note On a routing problem (Quarterly of Applied Mathematics, 1958) treats it as a dynamic program. The minimal travel times…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 4: Vertex Cover in Connected Graphs of Degree ≤ 3 Reduces to Weighted Vertex Cover for Interval-Order InstancesResearch Paper

In the single-machine scheduling problem 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_jC_j1∣prec∣∑wj​Cj​, a set NNN of nnn jobs, each with a processing time pj≥0p_j\ge 0pj​≥0 and a weight wj≥0w_j\ge 0wj​≥0, is processed on one machine without interruption, subject to precedence constraints given by a partial order PPP on NNN. The aim is to minimize the weighted sum of completion times ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​. The problem is…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 5: An r-Approximate Vertex Cover of the Variable-Cost Graph Yields an (r + ε)-Approximate Vertex Cover of GResearch Paper

The problem 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_jC_j1∣prec∣∑wj​Cj​ asks for an order in which to process jobs on one machine, respecting precedence constraints, so as to minimize the weighted sum of completion times. It is strongly NP-hard, and for decades the best approximation ratio known has been 222, achieved by several unrelated algorithms (LP relaxations, Sidney decompositions,…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 3: Deleting Far-Apart Tree-Like Vertices of a Near-Ramanujan Graph and Matching Their Neighbours Keeps λ ≤ 2√(d−1) + εResearch Paper

Sparse graphs with small nontrivial eigenvalues, expanders, are basic objects in combinatorics and theoretical computer science. They are used in error-correcting codes, derandomization, sorting networks, and the analysis of random walks. The Alon–Boppana bound says that a ddd-regular graph on nnn vertices has a nontrivial eigenvalue of absolute value at least …

13 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

The Strong Perfect Graph Theorem VI: A Berge Graph Containing a Long Odd Prism Admits a Proper 2-Join, a Balanced Skew Partition or a Proper Homogeneous PairResearch Paper

A graph is perfect if every induced subgraph has chromatic number equal to its clique number. Berge conjectured in 1961 that a graph is perfect exactly when it contains no odd hole and no odd antihole. Chudnovsky, Robertson, Seymour and Thomas proved this strong perfect graph theorem in 2006 (Ann. of Math. 164 (2006), 51–229). Perfect graphs matter beyond…

23 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

The Strong Perfect Graph Theorem IV: A Berge Graph Whose Appearances of K4 Are All Degenerate Is Double Split, Decomposes, or Has No Appearance of K4Research Paper

A graph is perfect if every induced subgraph has chromatic number equal to its clique number. Perfect graphs are the graphs for which colouring and clique problems behave as linear programs do: the stable-set polytope of a perfect graph is described by its clique inequalities, so maximum weight stable sets and minimum colourings can be computed in…

19 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

The Strong Perfect Graph Theorem V: A Berge Graph with No Nondegenerate Appearance of K4 Containing an Even Prism Is a Nine-Vertex Even Prism or DecomposesResearch Paper

A perfect graph is a finite simple graph in which every induced subgraph has chromatic number equal to its largest clique size. This equality gives a structural reason that a clique lower bound on the number of colours is attainable for every induced part of the graph. Berge proposed a forbidden-subgraph description of perfect graphs: a graph should be…

12 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

The Strong Perfect Graph Theorem III: A Berge Graph Containing a Nondegenerate Line Graph of a Bipartite Subdivision of K4 Is a Line Graph or DecomposesResearch Paper

A graph is perfect if every induced subgraph has chromatic number equal to its clique number, and Berge if no induced subgraph is an odd cycle of length at least five (an odd hole) or the complement of one (an odd antihole). Berge conjectured in 1961 that the two classes coincide. Chudnovsky, Robertson, Seymour and Thomas proved this, the strong perfect…

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

The Price of Stability for Network Design with Fair Cost Allocation II: Two Players with a Common Terminal in an Undirected Graph Have Price of Stability at Most 4/3, and This Is TightResearch Paper

In network design games, selfish users build a shared network and split the cost of every edge among the users of that edge. Anshelevich, Dasgupta, Kleinberg, Tardos, Wexler and Roughgarden (SIAM J. Comput. 38 (2008), DOI 10.1137/070680096) studied the fair connection game, in which the cost of an edge is shared equally (the Shapley value) among its users.…

9 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Algorithm 97: Shortest Path: Floyd's Procedure Computes the Shortest Path Length Between Every Pair of PointsResearch Paper

Routing and network optimization often require the length of the best route between every ordered pair of points. Robert W. Floyd's Algorithm 97 gives a compact procedure for this task: it receives a matrix of direct-link lengths and changes the matrix in place until each entry is meant to represent a shortest-path length. The procedure is a small…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources VI: Stable, Semistable, Pseudostable and Quasistable Schedules Are Extreme Points of the Feasible RegionTextbook

Resource-constrained project scheduling with minimum and maximum time lags is the model behind make-to-order production, process-industry batch planning and large engineering projects. When the objective is the project duration or another regular function (nondecreasing in every start time), an optimum can be found among schedules that cannot be shifted to…

12 thms2 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems: The Primal-Dual Upper Bound on the Optimal TourResearch Paper

Many routing problems come with a hard limit on distance or time rather than a requirement to visit everything. A repair crew with a fixed shift wants to service as many stations as possible; a vehicle with a fixed range wants to cover as many customers as possible. The budgeted prize-collecting traveling salesman problem captures this: given edge costs and…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming: Foundations and Extensions III: Network Flows, the Integrality Theorem and König's TheoremTextbook

Minimum-cost network flow problems are the largest special class of linear programs met in practice: transportation, distribution, assignment, communication and electric networks, facility location and financial planning all reduce to moving material along the arcs of a directed network from supply nodes to demand nodes at least cost. Chapter 14 of R. J.…

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

Odd Minimum Cut-Sets and b-Matchings 2: A Capacitated b-Matching Blossom Inequality Is Violated iff G(x, d) Has an Odd Cut of Capacity Less Than OneResearch Paper

A b-matching with upper bounds in a graph G=(V,E)G=(V,E)G=(V,E) assigns a nonnegative integer xe≤dex_e\le d_exe​≤de​ to every edge so that the edges at each node iii carry at most bib_ibi​ in total. Maximizing a linear objective over such assignments is an integer program that contains ordinary matching (b≡1b\equiv 1b≡1, d≡1d\equiv 1d≡1) and appears in assignment, transportation and scheduling models…

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

Odd Minimum Cut-Sets and b-Matchings 1: A Minimum-Weight Odd-Splitting Edge of the Gomory–Hu Cut-Tree Defines an Odd Minimum Cut-SetResearch Paper

Edmonds showed that the convex hull of the matchings of a graph is described by the degree constraints together with the blossom inequalities, one for every odd set of nodes (Edmonds 1965). There are exponentially many of them, so any cutting-plane method for matching and b-matching problems must answer a separation question: given a fractional point, find…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

A New Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem: Safe Shrinking of Customer SetsResearch Paper

The capacitated vehicle routing problem (CVRP) asks for minimum-cost routes, starting and ending at a depot, that serve every customer exactly once without any vehicle carrying more than its capacity. It is one of the central problems of operations research and logistics, and exact algorithms for it have been built on branch-and-cut for three decades: a…

13 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

The Traveling-Salesman Problem and Minimum Spanning Trees, Part II: Convergence of the Constant-Step Ascent to the 1-Tree BoundResearch Paper

The traveling-salesman problem (TSP) asks for a cheapest cycle through all vertices of a weighted complete graph. Exact algorithms for it are branch-and-bound searches, and their size depends almost entirely on the quality of the lower bounds used to prune the search. In 1970 Held and Karp introduced the 1-tree bound: a Lagrangian relaxation of the degree-2…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Applied Combinatorics VII: Minimum Spanning Trees and Dijkstra's AlgorithmTextbook

Two optimization problems on weighted networks sit at the base of operations research and algorithm design. The first asks for the cheapest way to connect every node of a network, such as a cable, pipeline or communication network. The answer is a minimum weight spanning tree. The second asks for the shortest route from a depot to every other node of a road…

8 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Correspondence Coloring and Its Application to List-Coloring Planar Graphs Without Cycles of Lengths 4 to 8: Every Planar Graph Without Cycles of Lengths 4 to 8 Is 3-ChoosableResearch Paper

List colouring asks for a proper colouring of a graph in which every vertex takes its colour from its own prescribed list. A graph is kkk-choosable if such a colouring exists for every assignment of lists of size kkk. Choosability is harder to guarantee than colourability: planar triangle-free graphs are 3-colourable (Grötzsch) but not all are 3-choosable…

16 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem IV: Insertion Heuristics Can Return Poor k-Optimal ToursResearch Paper

Insertion heuristics build a traveling salesman tour one city at a time: start from a single city, and at each step choose a city not yet on the subtour and splice it into the subtour where it lengthens the subtour least. Local search heuristics start from a tour and repeatedly replace a few of its edges by others while this shortens the tour. Both families…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem III: Nearest and Cheapest Insertion Are Within a Factor of TwoResearch Paper

The traveling salesman problem (TSP) asks for a shortest closed route through a finite set of points. It is NP-hard, and in practice tours are built by fast constructive heuristics whose output is then improved or used as is. A central question in the analysis of algorithms, raised in this form by Rosenkrantz, Stearns and Lewis in 1977, is how far such a…

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

On Certain Polytopes Associated with Graphs III: The Stable Set Polytope after Substituting a Graph for a VertexResearch Paper

Many combinatorial optimization problems on graphs are linear programs over a polytope whose inequality description is unknown. The stable set polytope is the standard example: maximizing a linear function over it is the maximum weight stable set problem, which is NP-hard, and no complete inequality description is known for general graphs. A productive line…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebraProbability+1·Captain: mikedeng1

Matching Is as Easy as Matrix Inversion: Steps 1–3 Find a Minimum Weight Perfect Matching with Probability at Least 1/2Research Paper

Deciding whether a graph has a perfect matching, and finding one, are basic problems of combinatorial optimization; Edmonds' blossom algorithm solves them sequentially in polynomial time. The question behind this paper is whether they can also be solved in parallel, in polylogarithmic time on polynomially many processors (the class NC, or RNC when random…

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