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
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Instance-Optimality of Single-Pair Personalized PageRankResearch Paper

Random walks with restart are a basic tool of network analysis. The personalized PageRank (PPR) π(s,t)\pi(s,t)π(s,t) of a target ttt with respect to a source sss measures how close ttt is to sss in a directed graph. It was introduced for personalized web search by Brin and Page, and it is now used in recommender systems, node embeddings, local clustering and graph neural…

21 thms1 active userReviewed
Probability·Captain: mikedeng1

From Oblivious to Adaptive Adversaries: Black-Box Reductions for Monotone Dynamic Problems with Applications to Cuts, Distances, and ClusteringResearch Paper

A randomized dynamic graph algorithm receives updates and maintains an answer after each one. An oblivious adversary commits to its update sequence independently of the algorithm's randomness. An adaptive adversary can choose the next update after inspecting earlier published answers. A guarantee for every fixed sequence does not automatically cover…

6 thms1 active userReviewed
cryptographyInformation Theory·Captain: mikedeng1

Non-Interactive Network Sum-Secure ComputationResearch Paper

Several users may need a server to compute an aggregate while protecting the aggregate from an observer of the communication network. Here the confidential object is the sum itself. The users' individual inputs are arbitrary deterministic values; there is no prescribed probability distribution on those inputs. Bai, Guang and Wang formulate this task with…

14 thms1 active userReviewed
CombinatoricsProbability·Captain: Shuze Chen

Fractional colorings of KrK_rKr​-free graphs with local demandsResearch Paper

Lower bounds on the independence number in terms of degrees are among the oldest themes of extremal graph theory. For triangle-free graphs, Ajtai, Komlós and Szemerédi proved α(G)=Ω(nlog⁡d/d)\alpha(G)=\Omega(n\log d/d)α(G)=Ω(nlogd/d) for average degree ddd, and Shearer sharpened this to α(G)≥nf(d)\alpha(G)\ge n f(d)α(G)≥nf(d) with the explicit function f(d)=(dlog⁡d−d+1)/(d−1)2f(d)=(d\log d-d+1)/(d-1)^2f(d)=(dlogd−d+1)/(d−1)2 (Shearer 1983), later to the…

29 thms1 active userReviewed
CombinatoricsOptimizationTheoretical Computer Science·Captain: Shuze Chen

Better Bounds for Semi-Streaming Maximum Matching via Load BalancingResearch Paper

Graphs too large to store are often processed as a stream: the edges arrive one at a time, in an order nobody controls, and an algorithm may read the stream a few times (passes) while keeping only a small summary in memory. The semi-streaming model of Feigenbaum, Kannan, McGregor, Suri and Zhang (FKM+05) allows O~(n)=O(n⋅polylog n)\tilde O(n)=O(n\cdot\mathrm{polylog}\,n)O~(n)=O(n⋅polylogn) bits…

24 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Small classes have linear neighbourhood complexityResearch Paper

A graph class can be studied by counting how many of its graphs exist on a fixed set of labels. It can also be studied by counting the different adjacency patterns visible on a chosen vertex set inside one graph. These are different measurements: the first concerns a collection of whole graphs, while the second concerns local observations within an…

21 thms1 active userReviewed
Combinatorics·Captain: Shuze Chen

Byzantine Partition Detection Under ChurnResearch Paper

Byzantine fault-tolerant protocols are proved correct under two separate assumptions: a bound ttt on the number of faulty processes, and enough vertex connectivity in the communication network (classically, connectivity above a multiple of ttt). The second assumption is usually taken for granted. Sengupta and Perrin ask whether the participants themselves can…

25 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignTheoretical Computer Science·Captain: iris

Pairwise Exchanges of Freely Replicable Goods with Negative ExternalitiesResearch Paper

Datasets, software and patents are freely replicable: giving a copy costs the giver nothing directly. Firms that hold such goods are often competitors, so each one gains from acquiring a good and loses when a rival acquires one. Data consortia and patent pools face this tension: every member wants access to the others' goods, and no member wants its rivals…

30 thms1 active userReviewed
Combinatorics·Captain: Shuze Chen

An approximate cactus-decomposition for vertex-connectivityResearch Paper

The cactus theorem of Dinitz, Karzanov and Lomonosov (1976) states that the minimum edge-cuts of a connected graph are represented by a cactus: a connected graph in which any two cycles share at most one vertex. That representation underlies algorithms for enumerating minimum cuts, connectivity augmentation and dynamic minimum cuts. For vertex-connectivity…

21 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

FPT-Algorithms for Connected Feedback Vertex Set: Single-exponential fixed-parameter tractability on general graphsResearch Paper

A feedback vertex set removes every cycle from an undirected graph when its vertices are deleted. Requiring the removed vertices themselves to induce a connected graph gives the Connected Feedback Vertex Set problem. These are different requirements: eliminating cycles does not ensure that the chosen vertices can communicate along edges whose endpoints also…

10 thms1 active userReviewed
Computational GeometryDiscrete Geometry·Captain: iris

The Stretch Factor of Planar Delaunay Triangulations Is Nearly DeterminedResearch Paper

A Delaunay triangulation of a finite point set S⊂R2S\subset\mathbb R^2S⊂R2 is a triangulation in which the open circumdisk of every triangle contains no point of SSS. Its stretch factor is the worst ratio dD(u,v)/∥u−v∥d_D(u,v)/\|u-v\|dD​(u,v)/∥u−v∥ over pairs u≠vu\ne vu=v of SSS, where dD(u,v)d_D(u,v)dD​(u,v) is the length of a shortest path from uuu to vvv along the edges of DDD. A uniform bound ttt on this ratio makes…

32 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Asymptotically Optimal Weighted Edge Colorings via Local Bin PackingResearch Paper

In weighted edge coloring each edge of a graph carries a weight in (0,1](0,1](0,1], and a coloring is feasible when, at every vertex, the edges of each color have total weight at most one. The problem generalizes ordinary edge coloring (all weights one) and bin packing (a star). Its principal application is multirate routing in three-stage Clos networks, where…

20 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Tight Query Depth of Recursive Randomized Greedy MISResearch Paper

A maximal independent set (MIS) of a graph is an inclusion-wise maximal set of pairwise nonadjacent vertices. The randomized greedy MIS (RGMIS) algorithm draws a uniformly random permutation π\piπ of the vertices, scans them in that order, and adds a vertex whenever none of its earlier neighbours has been added. Its output V∗V^*V∗ is the lexicographically first…

45 thms1 active userReviewed
Complexity TheoryProbability·Captain: mikedeng1

A Fully Polynomial Randomized Approximation Scheme for Hypergraph UnreliabilityResearch Paper

Network unreliability quantifies the risk that independent component failures disconnect a system. A hyperedge models one component connecting a whole set of vertices, so one failure can remove a connection among arbitrarily many endpoints. All-terminal unreliability is the probability that the surviving hypergraph has more than one connected component. The…

29 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence PatternsResearch Paper

A hypergraph records a finite collection of constraints by assigning each constraint the set of variables it involves. In database query evaluation and constraint satisfaction, the shape of these overlaps can determine which decomposition methods are available. Different notions of width measure different freedoms in choosing a decomposition. Fractional…

22 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

A Tight Space Lower Bound for Pivot-Based Distance OraclesResearch Paper

A distance oracle stores information about a graph so that later queries can estimate the distance between two vertices. Storing a separate answer for every pair can require quadratic space, even when the input graph itself has only linearly many edges. Allowing a multiplicative error creates a space–accuracy trade-off. The question addressed here concerns…

17 thms1 active userReviewed
Probability·Captain: mikedeng1

Adaptive Steps and Certificates for Semi-Streaming Shortest PathsResearch Paper

A graph can have too many edges to keep in memory while its vertices and a sparse collection of edges still fit. In the semi-streaming model, an algorithm reads an insertion-only stream repeatedly and keeps a small working memory between scans. For shortest paths, the number of complete scans is a substantial part of the cost. Assadi, Hoppenworth and…

12 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Maximum Matching and Related Problems in Catalytic LogspaceResearch Paper

A matching in a graph is a collection of edges that share no vertices. A maximum matching has as many edges as any such collection. Matching is a basic problem in combinatorial optimization, but the computational resources needed to construct one depend on the machine model. A polynomial-time procedure can retain intermediate data that do not fit in…

28 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

LOCAL LLL in poly(loglog n) RoundsResearch Paper

The variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…

20 thms1 active userReviewed
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
PreviousPage 14 of 16Next

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