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
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Random Deletion for Circuits in Regular MatroidsResearch Paper

Karger's random contraction algorithm ([Kar93], [Kar95]) showed that a graph with minimum cut weight λ\lambdaλ has at most n2αn^{2\alpha}n2α cuts of weight at most αλ\alpha\lambdaαλ. Through matroid duality, cuts of a graph are the circuits of its cographic matroid and cycles are the circuits of its graphic matroid, and Subramanian ([Sub95]) proved the analogous bound …

25 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

The Complexity of Distributed Minimum Weight Cycle ApproximationResearch Paper

A network can have inexpensive routes between many pairs of devices while its cheapest round trip remains difficult to identify. A minimum weight cycle is a simple closed route of minimum total edge weight. Finding one is a basic graph optimization problem related to shortest paths. In a distributed network the graph also determines which devices can…

27 thms1 active userReviewed
CombinatoricsComputational GeometryTheoretical Computer Science·Captain: iris

Parameterized Tractability of Euclidean k-Steiner TreeResearch Paper

A Steiner tree connects a set of terminals by a network of minimum total length, possibly through auxiliary Steiner points. In the discrete Euclidean variant the Steiner points must be chosen from a finite candidate set given in the input, and in the kkk-Steiner variant at most kkk of them may be used, while the number of terminals is unrestricted. Exact…

32 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Near-Optimal Space and Time Cut Sparsification in Turnstile StreamsResearch Paper

A cut sparsifier of a weighted graph G=(V,E,w)G=(V,E,w)G=(V,E,w) on nnn vertices is a reweighted subgraph HHH that approximates the weight of every cut of GGG within a factor 1±ε1\pm\varepsilon1±ε. Benczúr and Karger showed that every graph has one with O(nlog⁡n/ε2)O(n\log n/\varepsilon^2)O(nlogn/ε2) edges, and sparsifiers have since become a basic tool for minimum cut, maximum flow, Laplacian solvers and…

22 thms1 active userReviewed
CombinatoricsMathematical LogicTheoretical Computer Science·Captain: Shuze Chen

Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler–Leman and Hypertree WidthResearch Paper

The Weisfeiler–Leman (WL) family of colour-refinement algorithms is the standard heuristic for graph isomorphism and the yardstick for the expressive power of graph neural networks. Its distinguishing power has an exact algebraic description: by Lovász's theorem two graphs are isomorphic iff every graph has the same number of homomorphisms into both, and…

22 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: Shuze Chen

Random-Walk Cuckoo Hashing is Efficient up to the Critical Load ThresholdResearch Paper

Cuckoo hashing stores keys in a table so that every key sits in one of a few cells determined by its hashes, which makes lookups take constant worst-case time. With ddd hashes per key, the table can be filled almost completely: Fountoulakis and Panagiotou (FP12) identified the exact load threshold 1−εd∗1-\varepsilon^*_d1−εd∗​ up to which all keys can be placed with high…

20 thms1 active userReviewed
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
PreviousPage 26 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