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
Complexity TheoryTheoretical Computer Science·Captain: iris

Lower Bounds for the Weisfeiler-Leman Algorithm via Implicit Parity SystemsResearch Paper

The kkk-dimensional Weisfeiler–Leman algorithm (kkk-WL) is the central combinatorial heuristic for graph isomorphism. It refines a coloring of kkk-tuples of vertices round by round, and two graphs are told apart when their color statistics differ. The number of rounds is a natural measure in several fields: it equals the quantifier depth in the logic Ck+1C^{k+1}Ck+1 with…

38 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree AlgorithmsResearch Paper

An induced matching (or strong matching) of a graph is a set of pairwise vertex-disjoint edges whose endpoints span no other edges. Induced matchings appear in strong edge colouring (each colour class of a strong edge colouring is an induced matching), in the Ruzsa–Szemerédi problem, and in the analysis of graph algorithms and interference-free scheduling.…

23 thms2 active usersReviewed
Algebraic TopologyAlgorithmic Game TheoryCombinatorics·Captain: iris

Balanced Fair Division and Generalized Kneser GraphsResearch Paper

Many allocation problems divide indivisible goods between groups rather than individuals: households sharing what they receive, teams, or departments. Every member of a group gets the same bundle, but each member judges it with her own preferences, so a bundle that one member finds fair another may envy. Exact envy-freeness is impossible already for a…

32 thms2 active usersReviewed
Harmonic AnalysisProbabilityStatistics·Captain: iris

Sharp detection thresholds for random geometric graphs with polynomial average degreesResearch Paper

A random geometric graph (RGG) hides a latent geometry: each vertex carries a random point, and edges join nearby points. In high dimension the geometry washes out, and a basic question in probability, statistics and theoretical computer science is the dimension at which the graph becomes statistically indistinguishable from an Erdős–Rényi graph with the…

34 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SATResearch Paper

A strong backdoor of a CNF formula φ\varphiφ into a tractable class is a set XXX of variables such that every assignment to XXX turns φ\varphiφ into a formula of that class. Once a small backdoor is known, satisfiability is decided by trying all 2∣X∣2^{|X|}2∣X∣ assignments and solving each reduct in the class. The size of a smallest backdoor is therefore a parameter that…

32 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest PathsResearch Paper

In the k vertex-disjoint paths problem (k-DP) the input is a directed graph with nnn vertices, mmm edges and kkk terminal pairs (si,ti)(s_i,t_i)(si​,ti​), and the task is to connect every pair by a path so that the paths are pairwise vertex-disjoint. In the k disjoint shortest paths problem (k-DSP) every path must in addition be a shortest path between its terminals. Already for…

24 thms2 active usersReviewed
ProbabilityRandom Matrix TheoryTheoretical Computer Science·Captain: iris

Bethe Hessian Recovery through the Kesten–Stigum RegimeResearch Paper

The stochastic block model (SBM) is the standard test case for graph partitioning: vertices carry hidden community labels, and edges appear independently with probabilities that depend on the labels. In the sparse regime, where every vertex has bounded expected degree ddd, exact recovery is impossible (some vertices are isolated), and the question is weak…

38 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

NP-hardness of additive approximation for generalized Turán problemsResearch Paper

Graph modification problems ask how far an input graph is from a property. For the property of being F\mathcal FF-free, Alon, Shapira and Sudakov proved that when no member of the family F\mathcal FF is bipartite, the minimum number of edge deletions that make a graph F\mathcal FF-free is NP-hard to compute, and even to approximate within an additive error …

34 thms2 active usersReviewed
Markov ChainProbabilityTheoretical Computer Science·Captain: iris

A simple proof of rapid mixing on random regular graphs beyond uniquenessResearch Paper

The hard-core model on a graph is the distribution on independent sets weighted by λ∣I∣\lambda^{|I|}λ∣I∣, and it is the central test case for sampling from distributions on combinatorial structures. Glauber dynamics, which resamples one vertex at a time, is the standard sampler. As surveyed in §1 of arXiv:2606.27545, on graphs of maximum degree Δ\DeltaΔ the…

31 thms2 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Nearly Exact Length Bounds for Directed Steiner Tree and Forest in Planar GraphsResearch Paper

In length-constrained network design one buys arcs of a graph so that every demand can be routed along a short path. Each arc carries two separate numbers, a purchase cost and a travel length, and the bought arcs are shared: an arc used by many demands is paid once. The difficulty is that sharing and shortness pull in opposite directions. Buying each…

66 thms2 active usersReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: iris

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with ApplicationsResearch Paper

A sensitivity oracle preprocesses a graph once so that, after a batch of at most fff edge failures or insertions arrives, a question about the modified graph is answered without recomputing from scratch. Networks fail a few links at a time, and the planner wants the new maximum throughput, the new bottleneck cut, or the new cheapest routing at once. For…

51 thms2 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: iris

Uniform Guarded Bootstrapping for Topology-Sensitive Directed Shortest PathsResearch Paper

Single-source shortest paths on a directed graph with nonnegative real weights asks for the distance from a source sss to every vertex. In the comparison–addition model, where real weights may only be added and compared, Dijkstra's algorithm with a Fibonacci heap takes O(m+nlog⁡n)O(m+n\log n)O(m+nlogn) time, and for a long time this was the best general bound. Recent work went…

26 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Faster Cluster Decomposition with Stronger Bi-Criteria GuaranteeResearch Paper

Partitioning the vertices of a graph into clusters is a basic problem in theoretical computer science, machine learning and network analysis. A single objective can reward a poor clustering, as Kannan, Vempala and Vetta showed, so they proposed a bi-criteria measure. Oveis Gharan and Trevisan sharpened it: a good cluster should be well connected inside and…

26 thms2 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Planted Dense Subgraph Conjectures Are EquivalentResearch Paper

The planted clique and planted dense subgraph problems are the standard average-case hard problems behind a large family of reductions in statistics and learning theory: sparse PCA, community detection, submatrix localization, tensor PCA and robust estimation all inherit computational lower bounds from them (Brennan, Bresler, Huleihel, COLT 2018; Brennan,…

26 thms2 active usersReviewed
Complexity TheoryLinear algebraProbability·Captain: iris

Nested Effective Resistance Partitions and Eulerian SparsificationResearch Paper

Spectral sparsification replaces a dense graph by a sparse reweighted graph that preserves its Laplacian quadratic form up to a factor 1±ε1\pm\varepsilon1±ε. For undirected graphs the picture has been complete for over a decade: Spielman and Srivastava sample O(nε−2log⁡n)O(n\varepsilon^{-2}\log n)O(nε−2logn) edges by effective resistance (SS11), and Batson, Spielman and Srivastava show…

63 thms2 active usersReviewed
Linear algebraTheoretical Computer Science·Captain: iris

Efficient Algorithms for Minrank and Index Coding for Low-Treewidth GraphsResearch Paper

The minrank of a graph was introduced by Haemers as an upper bound on the Shannon capacity. Its main motivation today is index coding: a sender broadcasts a string x∈Fqnx \in \mathbb F_q^nx∈Fqn​ to nnn receivers, receiver iii wants xix_ixi​ and already knows the coordinates indexed by its out-neighbours in a knowledge graph GGG, and the question is how short the broadcast can…

49 thms2 active usersReviewed
Algebraic TopologyCombinatoricsTheoretical Computer Science·Captain: iris

Improved Lower Bounds on Tree CoversResearch Paper

A tree cover approximates a finite metric by a few trees instead of one. For an nnn-point metric space (X,d)(X, d)(X,d), an (α,k)(\alpha, k)(α,k)-tree cover is a family of kkk edge-weighted trees T1,…,TkT_1, \dots, T_kT1​,…,Tk​ on the vertex set XXX such that every tree dominates the metric, dTi(x,y)≥d(x,y)d_{T_i}(x,y) \ge d(x,y)dTi​​(x,y)≥d(x,y), and every pair x,yx, yx,y is approximated within a factor α\alphaα in at least one tree.…

36 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász TheoremResearch Paper

Partitioning a graph into connected pieces of prescribed sizes, each containing a designated root, is a basic primitive in network design, districting and load balancing, and in the analysis of confluent flows. The Győri–Lovász theorem says when this is always possible. Győri proved it for undirected kkk-connected graphs (Győri 1976), and Lovász gave a…

44 thms2 active usersReviewed
CombinatoricsMathematical LogicTheoretical Computer Science·Captain: iris

Monadically Dependent Graph Classes Have Almost Bounded Merge-WidthResearch Paper

First-order model checking asks, given a graph GGG and a first-order sentence φ\varphiφ, whether φ\varphiφ holds in GGG. A central conjecture states that this problem is fixed-parameter tractable on every monadically dependent graph class: a class that cannot encode all graphs through a fixed formula over vertex-colored members. Planar graphs, classes of bounded…

41 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Smoothed Analysis for Distributed MISResearch Paper

A maximal independent set (MIS) is a basic symmetry-breaking object in distributed computing. Luby's algorithm (Luby 1986) finds one in O(log⁡n)O(\log n)O(logn) rounds, and for decades no substantially faster algorithm for general graphs was known. Khoury and Schild (arXiv:2610.18215) showed that Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n)Ω(logn/loglogn) rounds are necessary on some graphs in the LOCAL…

28 thms2 active usersReviewed
CombinatoricsComputational GeometryTheoretical Computer Science·Captain: iris

Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting SetResearch Paper

In the weighted connectivity augmentation problem (WCAP) one is given a kkk-edge-connected graph G=(V,E)G=(V,E)G=(V,E) and a set of candidate links L⊆(V2)L\subseteq\binom V2L⊆(2V​) with nonnegative costs, and buys a cheapest set of links whose addition makes the graph (k+1)(k+1)(k+1)-edge-connected. Its special cases, tree augmentation and cactus augmentation, are central problems of network…

56 thms2 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and TreewidthResearch Paper

Many inference problems on random structures show a gap between what is statistically possible and what known polynomial-time algorithms achieve. The low-degree method is the most widely used heuristic for predicting such gaps: it compares a planted law PPP with a null law QQQ only through polynomials of bounded degree in the observed coordinates, and treats a…

36 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

An O(nlog⁡n)O(n\log n)O(nlogn) Sorting Network: Standard Comparator Networks of Depth O(log⁡n)O(\log n)O(logn) and Size O(nlog⁡n)O(n\log n)O(nlogn) Sort Every InputResearch Paper

A comparator network sorts by a fixed schedule of compare-and-swap operations that does not depend on the data. Such networks are oblivious, so they model sorting in hardware, in parallel machines, and in settings where the access pattern must not leak information. Two measures matter: size, the number of comparators, and depth, the number of parallel steps…

27 thms2 active usersReviewed
Combinatorics·Captain: iris

Sparse Discrepancy Beyond Additive Functions: Acyclic, Bounded-Degree and Degenerate Sparsity PatternsResearch Paper

In combinatorial discrepancy one colours the elements of a ground set red and blue so that every set of a given system is split as evenly as possible. The Beck–Fiala theorem (Beck–Fiala 1981) bounds the discrepancy of a system in which every element lies in at most ttt sets by 2t−12t - 12t−1, independently of the number of sets and elements. Its proof, like Spencer's …

77 thms2 active usersReviewed
ProbabilityRandom Matrix TheoryTheoretical Computer Science·Captain: iris

Counting Paths in Time O∗(2k)O^*(2^k)O∗(2k), with Extensions to Counting Bounded Treewidth Graphs and Multilinear MonomialsResearch Paper

Deciding whether a directed graph contains a path on kkk vertices (kkk-Path) is a central problem of parameterized complexity. Williams' algebraic method gives a randomized 2knO(1)2^k n^{O(1)}2knO(1) algorithm for the decision problem (2009), and base 222 remains the best known exponential dependence on kkk. Counting the paths approximately has been harder. Koutis and Williams…

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