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

Applied Combinatorics VI: Ramsey's Theorem and Erdős's Lower BoundTextbook

Ramsey theory studies the principle that complete disorder is impossible: every sufficiently large structure contains a large, perfectly uniform substructure. Its most familiar instance concerns graphs. In any graph on six vertices there are three vertices that are pairwise adjacent or three that are pairwise non-adjacent, and the same phenomenon persists…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGroup TheoryOperations Research+1·Captain: mikedeng1

λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 2: Cayley Graphs of Finite Quotients of a Property (T) Group Are Linear EnlargersResearch Paper

An expander is a sparse graph in which every set of vertices has many neighbours outside itself. Expanders are the building blocks of superconcentrators (sparse directed graphs that route any rrr inputs to any rrr outputs along vertex-disjoint paths), of sorting and switching networks, and of many constructions in complexity theory and coding; the survey of…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators 1: A Diameter Bound from λ1Research Paper

The eigenvalues of the Laplacian of a graph carry metric information about the graph. The second-smallest one, λ1(G)\lambda_1(G)λ1​(G), was named the algebraic connectivity by Fiedler (Fiedler 1973), who showed it is positive exactly for connected graphs. N. Alon and V. D. Milman (J. Combin. Theory Ser. B 38 (1985) 73–88) showed that a large λ1\lambda_1λ1​ also forces two…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 2: FOREST's Forests E_i Preserve Local Node-Connectivity up to i in a Simple GraphResearch Paper

Given a kkk-connected graph, many connectivity algorithms run in time that grows with the number of edges ∣E∣|E|∣E∣. A sparse certificate is a spanning subgraph with only O(k∣V∣)O(k|V|)O(k∣V∣) edges that is still kkk-connected; computing one first and running the expensive algorithm on it replaces ∣E∣|E|∣E∣ by k∣V∣k|V|k∣V∣ in the bound. Finding a kkk-connected spanning subgraph with the minimum…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

A Linear-Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph 1: The FOREST Decomposition Preserves Local Edge-ConnectivityResearch Paper

Many graph algorithms for connectivity questions run in time proportional to the number of edges. When the question is only whether a graph is kkk-edge-connected, or what its local edge-connectivities are up to a threshold kkk, most edges are irrelevant: a spanning subgraph with O(k∣V∣)O(k|V|)O(k∣V∣) edges already carries the answer. Such a subgraph is called a sparse…

10 thms3 active usersReviewed
🏆Completed
Control TheoryDynamical SystemsLinear algebra·Captain: mikedeng1

On Controllability of Delayed Boolean Control Networks: Trajectory Controllability Avoiding Forbidden Trajectories Iff the Reduced Transition-Count Matrix Is IrreducibleResearch Paper

Boolean networks model gene regulatory networks by giving each gene an on/off value and updating all values synchronously by logical rules (Kauffman, 1969). Adding external Boolean inputs gives Boolean control networks (BCNs), in which a designer (a drug, an intervention) chooses the inputs over time. The basic control-theoretic question is controllability:…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization III: The Defect of a Stable Set Inequality Bounds Its N-IndexResearch Paper

Many 0–1 optimization problems can be written as linear programs over the convex hull of the 0–1 points of a polytope, but that hull usually has no manageable description by inequalities. Lift-and-project methods approximate it by a sequence of convex sets. Each set comes from a linear or semidefinite system in more variables, followed by a projection.…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear algebraOperations Research+1·Captain: mikedeng1

Approximating Clique-Width and Branch-Width: Well-Linked Sets Certify Clique-WidthResearch Paper

Clique-width is a graph parameter introduced by Courcelle and Olariu (Discrete Appl. Math. 101 (2000)) that measures how far a graph is from being built by a few labelled operations. Every problem expressible in monadic second-order logic with quantification over vertices and vertex sets (MSO1_11​) can be solved in linear time on graphs given together with a…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsNumber TheoryTheoretical Computer Science·Captain: mikedeng1

Fast Algorithms for Finding Nearest Common Ancestors II: Nearest Common Ancestors in a Complete Binary Tree by Symmetric-Order ArithmeticResearch Paper

The nearest common ancestor (nca) problem asks, for a fixed rooted tree and a sequence of vertex pairs (v,w)(v, w)(v,w), for the deepest vertex that is an ancestor of both. It is a basic step in suffix-tree string algorithms and is equivalent to range-minimum queries (Bender, Farach-Colton, 2000). Harel and Tarjan, Fast Algorithms for Finding Nearest Common Ancestors,…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

A New Approach to the Maximum-Flow Problem 2: The Nonsaturating-Push Bound for FIFO Push-RelabelResearch Paper

The maximum-flow problem asks how much of a commodity can be sent from a source to a sink through a network whose edges carry capacities. It is a basic model of operations research. Transportation, scheduling, bipartite matching and image segmentation reduce to it, and it is the inner step of many combinatorial algorithms.

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

A New Approach to the Maximum-Flow Problem 1: The Generic Push-Relabel Algorithm and Its Operation BoundResearch Paper

The maximum-flow problem asks how much of a commodity can be sent from a source to a sink through a network whose edges have capacities. It is a basic model in operations research (transportation, scheduling, bipartite matching) and a standard subroutine in combinatorial optimization.

17 thms3 active usersReviewed
🏆Completed
CombinatoricsDynamic ProgrammingOperations Research·Captain: mikedeng1

The Steiner Problem in Graphs: Algorithm A Computes the Length of the Steiner TreeResearch Paper

The Steiner problem in graphs asks for the cheapest way to connect a prescribed set of nodes of a network, where intermediate nodes may be used freely. It is the network version of the classical Euclidean Steiner tree problem surveyed by Gilbert and Pollak (SIAM J. Appl. Math. 16, 1968), and it arises wherever a few sites must be joined through an existing…

10 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Sorting in c log n Parallel Steps: Sorting Networks of Logarithmic DepthResearch Paper

A sorting network is a sorting procedure whose sequence of comparisons is fixed in advance, independently of the data. Its depth, the number of rounds of simultaneous comparisons on disjoint pairs, is the parallel running time. Sorting networks are used in parallel and hardware sorting, in switching networks, and in cryptography, where a data-independent…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Shortest Connection Networks And Some Generalizations: Construction Principles P1 and P2 Yield a Shortest Spanning Subtree of Every Connected Labelled GraphResearch Paper

Connecting a set of terminals by a network of direct links of least total length is one of the oldest problems of combinatorial optimization. R. C. Prim's 1957 paper in the Bell System Technical Journal (DOI) was motivated by the rate structure for Bell System leased-line services, in which the charge for connecting a set of terminals depends on the length…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

A Simple Parallel Algorithm for the Maximal Independent Set Problem II: The Round Bound of the Derandomized AlgorithmResearch Paper

A maximal independent set (MIS) of a graph is a set of pairwise non-adjacent vertices to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be computed by a fast parallel algorithm was a central question of parallel complexity in the early 1980s: Karp and…

16 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

A Simple Parallel Algorithm for the Maximal Independent Set Problem I: One Round of Monte Carlo Algorithm A or B Removes an Expected Eighth of the EdgesResearch Paper

A maximal independent set (MIS) of a graph is a set of vertices, no two adjacent, to which no further vertex can be added. Sequentially an MIS is found greedily in linear time, but the greedy scan is inherently serial. Whether an MIS can be found fast in parallel was a central question of parallel complexity in the early 1980s: an MIS algorithm is a…

8 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Critical-Path Planning and Scheduling I: Critical Jobs Occur Only When the Completion Time Is the Earliest, and Then Form a Path from Origin to TerminusResearch Paper

The Critical-Path Method (CPM) was introduced by J. E. Kelley, Jr. (Remington Rand) and M. R. Walker (du Pont) in Critical-Path Planning and Scheduling (Proc. Eastern Joint Computer Conference, 1959, pp. 160–173, doi:10.1145/1460299.1460318). Together with PERT, developed at the same time for the Polaris programme, it became the standard way to plan and…

7 thms3 active usersReviewed
Combinatorics·Captain: hao jia

Six Colors for Star Edge-Coloring Subcubic Graphs (OPG-37271)Open Problem

A star edge coloring is a proper edge coloring with an additional local restriction: no path or cycle of four edges may use only two colors. It sits between ordinary proper edge coloring and strong edge coloring. The problem is local enough to admit finite obstruction searches, but global enough that independently valid local colorings may fail to fit…

11 thms3 active usersReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General GraphsResearch Paper

The maximum-weight perfect matching (MWPM) problem asks for a perfect matching of maximum total weight in an undirected graph with integer edge weights. It is a basic primitive of combinatorial optimization. It appears directly in resource allocation, exchange markets and scheduling, and as a subroutine in Christofides' 3/2-approximation for metric TSP.…

18 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Beyond Gomory-Hu: All-Pairs ×\times× All-Pairs Mincuts in O(n)O(n)O(n) SpaceResearch Paper

Two classical representations of minimum cuts in an undirected weighted graph G=(V,E,w)G=(V,E,w)G=(V,E,w) with nnn vertices answer complementary questions. The Gomory–Hu tree (Gomory–Hu 1961) stores, in O(n)O(n)O(n) space, one minimum (x,y)(x,y)(x,y)-cut for every terminal pair x,yx,yx,y, but only one of the possibly many. The Picard–Queyranne representation (Picard–Queyranne, Math. Programming Study…

41 thms2 active usersReviewed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Minimum-Cost kkk-Arborescence Packing in O~(km+k4n)\tilde O(km+k^4 n)O~(km+k4n) TimeResearch Paper

A packing of kkk arc-disjoint spanning arborescences rooted at a common vertex rrr keeps every vertex reachable from rrr after the deletion of any k−1k-1k−1 arcs. Finding such a packing of minimum total cost is a building block of approximation algorithms for network design, including minimum-cost kkk-edge-connected spanning subgraphs and flexible graph connectivity, and…

37 thms2 active usersReviewed
CombinatoricsHarmonic AnalysisTheoretical Computer Science·Captain: mikedeng1

Sparsest Cut on Abelian Cayley GraphsResearch Paper

The sparsest cut problem asks for a set of vertices of a graph that is poorly connected to the rest. It is NP-hard to solve exactly, and the best polynomial-time guarantee for general graphs remains the O(log⁡n)O(\sqrt{\log n})O(logn​) approximation of Arora, Rao and Vazirani (ARV09); no subexponential-time constant-factor approximation is known for general graphs. This…

17 thms2 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

Near-Linear Estimation of Network UnreliabilityResearch Paper

The unreliability uuu of a network is the probability that it becomes disconnected when its links fail at random. It is the basic reliability measure for communication and transport networks, and computing it exactly is #P-hard (Provan–Ball 1983). Approximation is therefore the only option. A Monte Carlo sample has relative variance Θ(1/u)\Theta(1/u)Θ(1/u), which is…

21 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Smallest Multiplicative Stretch for an α\alphaα-APASP Below O~(nω)\widetilde O \left(n^{\omega}\right)O(nω) RuntimeResearch Paper

All-pairs approximate shortest paths (APASP) asks, for a weighted undirected graph GGG on nnn vertices, for an estimate d[u,v]d[u,v]d[u,v] of every distance δ(u,v)\delta(u,v)δ(u,v) with δ(u,v)≤d[u,v]≤α δ(u,v)\delta(u,v)\le d[u,v]\le\alpha\,\delta(u,v)δ(u,v)≤d[u,v]≤αδ(u,v). The factor α\alphaα is the stretch. Exact all-pairs shortest paths in weighted graphs has no known truly subcubic algorithm, so approximation is the standard…

22 thms2 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Harmonic Ranking for Edge-Weighted Oblivious MatchingResearch Paper

A query–commit matching problem combines discovery with allocation. A successful query can force an immediate decision, so learning which pairs are available cannot be separated from choosing a matching. This matters in the mathematical study of allocation rules that must act without seeing the complete compatibility graph. The edge-weighted oblivious model…

30 thms2 active usersReviewed
PreviousPage 13 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