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

No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL ModelResearch Paper

A maximal independent set selects pairwise nonadjacent vertices so that every unselected vertex has a selected neighbor. Distributed algorithms use such sets to break symmetry and organize neighboring processors. The classical algorithms of Luby (1986) and Alon, Babai and Itai (1986) achieve logarithmic randomized round bounds. The pinned submission asks…

21 thms1 active userReviewed
Probability·Captain: mikedeng1

Two choices suffice: kkk-out sampling leaves O(n/k)O(n/k)O(n/k) intercomponent edges for k≥2k\geq 2k≥2Research Paper

Random kkk-out sampling sparsifies a graph by local choices: every vertex independently picks kkk of its incident edges. The question is how much connectivity information the sample loses, measured by the number of original edges that join distinct components of the sample. Contracting each sampled component leaves exactly these edges, and adding them to a…

17 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Thinning and Sprinkling: Robust Vertex Sampling and Almost HamiltonicityResearch Paper

A Hamilton cycle visits every vertex of a graph exactly once before returning to its starting vertex. Determining when a graph must contain such a cycle is a basic structural question. One necessary feature is resistance to fragmentation: deleting a small set of vertices cannot leave too many disconnected pieces. The parameter that quantifies this…

25 thms1 active userReviewed
CombinatoricsProbabilityRandom Matrix Theory·Captain: mikedeng1

Hamiltonicity of mildly pseudorandom regular graphsResearch Paper

An (n,d,λ)(n,d,\lambda)(n,d,λ)-graph is an nnn-vertex ddd-regular graph whose adjacency matrix has all non-trivial eigenvalues of absolute value at most λ\lambdaλ. The smaller λ\lambdaλ is compared to ddd, the more the graph resembles a random one. Whether such a graph has a Hamilton cycle, a cycle through every vertex, is a central question on pseudorandom graphs. Krivelevich and…

22 thms1 active userReviewed
Computational ComplexityNumber Theory·Captain: mikedeng1

Strongly explicit Ramanujan 2-lift towers via Hilbert modular formsResearch Paper

An expander graph supports walks that move through a large state space while using few random choices per step. Local access matters when a vertex has an nnn-bit name: a graph on 2n2^n2n vertices is useful to an algorithm only if its next neighbor can be computed without first constructing the entire graph. A compatible hierarchy adds another requirement. A walk…

19 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree ModelResearch Paper

A property tester examines a small part of a large object and distinguishes objects with a property from objects far from that property. For graph algorithms, this asks whether reading an entire graph is necessary even when an approximate decision would suffice. Fixed-graph isomorphism testing gives the algorithm a complete target graph in advance. Its only…

17 thms1 active userReviewed
OptimizationProbability·Captain: iris

Adaptivity Gaps for Influence Maximization: Percolation and DepletionResearch Paper

In influence maximization one selects at most kkk vertices of a network, the seeds, so as to maximize the expected number of vertices reached by a random cascade started from them. Kempe, Kleinberg and Tardos (KKT03) introduced the independent cascade model, in which every arc of the network is live independently with a known probability, and showed that the…

41 thms1 active userReviewed
Theoretical Computer Science·Captain: iris

Reading between the levels: new tools for the Thorup–Zwick hierarchy and their applicationsResearch Paper

An approximate distance oracle (ADO) is a data structure built once from a graph that, given two vertices u,vu, vu,v, returns an estimate d^(u,v)\hat d(u, v)d^(u,v) of their distance. It has stretch α\alphaα if d(u,v)≤d^(u,v)≤α d(u,v)d(u, v) \le \hat d(u, v) \le \alpha\, d(u, v)d(u,v)≤d^(u,v)≤αd(u,v) for every pair. Oracles trade space, query time and stretch against each other.

24 thms1 active userReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: iris

Maximum Cardinality Matching in n2+o(1)n^{2+o(1)}n2+o(1) TimeResearch Paper

Maximum cardinality matching asks for a largest set of pairwise disjoint edges in a graph. It is one of the oldest problems in combinatorial optimization, and general graphs are what distinguish it from bipartite matching and ordinary flow. Two lines of work have stood as the fastest for decades: the O(mn)O(m\sqrt n)O(mn​) combinatorial algorithm of Micali and…

29 thms1 active userReviewed
CombinatoricsLinear OptimizationTheoretical Computer Science·Captain: iris

Almost Tight Hardness of Approximation for 0-ExtensionResearch Paper

In 0-Extension, introduced by Karzanov (1998), a graph with nonnegative edge weights and kkk terminals carrying a metric must be retracted onto its terminals at minimum total cost. The problem combines the terminal constraints of Multiway Cut with the metric edge costs of Metric Labeling, and it is connected to Lipschitz extension, metric embeddings and…

25 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

A Unified and Simplified Framework for Dynamic Distance-Based Graph ProblemsResearch Paper

Distance problems on graphs that change over time sit behind many algorithms for flows, cuts and routing. A data structure that answers approximate distance queries while edges are deleted can replace repeated shortest-path computations inside iterative methods. Deterministic structures are of special interest, since they withstand an adaptive adversary by…

42 thms1 active userReviewed
CombinatoricsProbability·Captain: iris

Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential AlgorithmsResearch Paper

How large can the pathwidth of a sparse graph be? For graphs of maximum degree 333 the question matters in two places. Structurally, pathwidth, bisection width and cutwidth of such graphs are tied together by classical relations, so an upper bound on one transfers to the others. Algorithmically, many exact exponential algorithms for sparse instances run a…

44 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Streaming Graph Colouring Meets Molloy–Reed via KernelizationResearch Paper

Brooks' theorem says that a connected graph of maximum degree Δ\DeltaΔ other than a clique or an odd cycle has a proper Δ\DeltaΔ-colouring, and Molloy and Reed showed that, for large Δ\DeltaΔ and kkk below a threshold of order Δ\sqrt\DeltaΔ​, the failure of (Δ−k)(\Delta-k)(Δ−k)-colourability is witnessed by a small subgraph. In the streaming model the edges of the graph arrive…

28 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Fully Dynamic Brooks ColoringResearch Paper

Brooks' theorem (Brooks 1941) says that a connected graph of maximum degree Δ\DeltaΔ can be properly colored with Δ\DeltaΔ colors unless it is a clique KΔ+1K_{\Delta+1}KΔ+1​ or an odd cycle. For Δ≥3\Delta\ge3Δ≥3 the only obstruction is KΔ+1K_{\Delta+1}KΔ+1​, and the theorem is tight: Δ\DeltaΔ colors is one fewer than the greedy bound Δ+1\Delta+1Δ+1.

23 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for RankingResearch Paper

In online bipartite matching, offline vertices are known in advance and online vertices arrive one at a time, each to be matched irrevocably. The algorithm RANKING of Karp, Vazirani and Vazirani (1990) draws independent uniform ranks and matches each arrival to its unmatched neighbour of minimum rank. Devanur, Jain and Kleinberg (2013) gave the standard…

31 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Fully Dynamic Connectivity in O(log⁡3n)O(\log^3 n)O(log3n) Worst-Case Update TimeResearch Paper

In fully dynamic connectivity, a graph on a fixed set of nnn vertices changes by edge insertions and deletions, and queries ask whether two given vertices are connected. A spanning forest answers every query, and the difficulty is deletion: removing a forest edge splits a tree, and a replacement edge must be found without searching the whole graph. Worst-case…

27 thms1 active userReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Real-to-Integer Reduction for All-Pairs Shortest PathsResearch Paper

All-Pairs Shortest Paths (APSP) asks, for a directed edge-weighted graph on nnn vertices with no negative cycles, for the length of a shortest path between every pair of vertices. The textbook Floyd–Warshall algorithm runs in time O(n3)O(n^3)O(n3) (Floyd 1962). APSP is one of the central problems of fine-grained complexity, and many problems are equivalent to it under…

25 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Near-Optimal Almost-Ramsey Spanning Tree Covers, via Layered ClusteringsResearch Paper

A tree cover of a weighted graph replaces its shortest-path metric by a small collection of trees, so that every pair of vertices is well served by at least one of them. Tree covers underlie compact routing schemes, distance oracles and spanners, because a tree is far easier to store and to route on than a graph. The hardest variant asks for spanning trees,…

41 thms1 active userReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Connectivity in a New Bounded-Space Dynamic ModelResearch Paper

Undirected sss–ttt connectivity is a central test case for time–space tradeoffs on a read-only input. Breadth-first search takes linear time and Θ(n)\Theta(n)Θ(n) words. The random walk of Aleliunas et al. (1979) takes O(log⁡n)O(\log n)O(logn) bits and much longer. Feige (1997) and others charted the range in between, and Reingold (2008) showed that the problem is in deterministic…

32 thms1 active userReviewed
Theoretical Computer Science·Captain: iris

Composable Content-Oblivious Leader Election on Eulerian GraphsResearch Paper

In a content-oblivious network every message may be corrupted arbitrarily, so a message carries no information beyond its arrival: communication reduces to pulses, and a node's behaviour may depend only on the ports at which pulses arrive. Censor-Hillel, Cohen, Gelles and Sela showed that any asynchronous algorithm can still be simulated on a…

32 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Continuous Patrolling Games: On Every Network, Attacks No Longer Than the Generalized Girth Have Value α/(μ + lα/2), Attained by the Leaf-Pausing Double Tour and the Independent AttackResearch Paper

A security agency guards a network of roads, pipelines or corridors against an infiltrator who needs a fixed amount of uninterrupted time at one spot to do damage. The agency moves a single patroller at bounded speed and wants to maximize the probability of catching the attack in progress. Patrolling games model this as a zero-sum game between a Patroller…

27 thms1 active userReviewed
EconomicsOperations Research·Captain: iris

Impact of Network Structure on New Service Pricing: Balanced Networks Share One Optimal Policy and Revenue, the Lowest Among All Networks of the Same Average DegreeResearch Paper

Many online services (social platforms, question-and-answer sites, collaboration tools) become more valuable to a user the more that user's contacts use them. A firm launching such a service commonly offers it for free at first, to let usage grow through these local network effects, and starts charging later. Alizamir, Chen, Kim and Manshadi (SSRN 3236225;…

22 thms1 active userReviewed
🏆Completed
Captain: marwahaha

OpenAI Ten Proofs 10: Extremal graph counterexamplesResearch Paper

Extremal graph counterexamples, from the OpenAI Ten Proofs formalization. The source already contains machine-checked proofs; this mission organizes its headline result and additional Comparator targets for reuse.

6 thms1 active userReviewed
🏆Completed
Captain: marwahaha

OpenAI Ten Proofs 09: Multicolor triangle Ramsey numbersResearch Paper

Multicolor triangle Ramsey numbers, from the OpenAI Ten Proofs formalization. The source already contains machine-checked proofs; this mission organizes its headline result and additional Comparator targets for reuse.

5 thms1 active userReviewed
Algorithmic Game TheoryProbabilityStochastic Systems·Captain: mikedeng1

A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes II: Large-Graph Limits of the Equilibrium Through the Laplacian Eigenvalue DistributionResearch Paper

Mean field games describe large populations of agents who interact symmetrically: every agent sees the same average of all the others. Many populations interact instead along a network, where each agent responds only to its neighbours. Lacker and Soret (arXiv:2005.14102v2, 2021; Math. Oper. Res. 2022) study a linear-quadratic stochastic differential game on…

17 thms1 active userReviewed
PreviousPage 27 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