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

A counterexample to Sidorenko's conjectureOpen Problem

Graph homomorphism inequalities compare the frequency of a fixed pattern with what edge density predicts. The mission asks for one finite host graph violating the proposed bound for a specified bipartite pattern. The source manuscript presents the surrounding research claim.

6 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

A linear list-coloring bound in terms of the Hadwiger numberOpen Problem

List coloring permits each vertex to have different allowable colors. The mission asks whether the size of the largest clique minor still controls the required list size up to a universal linear factor. The source manuscript presents the surrounding research claim.

9 thms2 active usersReviewed
🏆Completed
Number Theory·Captain: marwahaha

Bounded-Step Walks on Gaussian PrimesOpen Problem

A planar prime walk can go around a gap that would block a walk on a line. The Gaussian moat problem therefore asks for an obstruction to every possible bounded-step route through distinct Gaussian primes. The source manuscript presents the surrounding research claim.

2 thms2 active usersReviewed
🏆Completed
Dynamical SystemsProbability·Captain: wurtle

The free uniform spanning forest is a factor of IIDResearch Paper

A uniform spanning tree of a finite connected graph is a spanning tree chosen uniformly at random. On an infinite graph one takes limits along finite pieces: the free uniform spanning forest (FUSF) is the weak limit of uniform spanning trees of an increasing sequence of finite connected subgraphs, with no boundary identification. Uniform spanning forests…

11 thms2 active usersReviewed
🏆Completed
Group TheoryProbability·Captain: wurtle

No percolation at criticality on quasi-transitive graphsResearch Paper

In Bernoulli bond percolation on a graph G=(V,E)G=(V,E)G=(V,E), each edge is kept (open) independently with probability ppp. As ppp grows, an infinite connected component of open edges appears at the critical probability pc(G)p_c(G)pc​(G). The criticality problem asks whether an infinite cluster can already exist at pcp_cpc​. A negative answer means the phase transition is continuous.…

25 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: wurtle

Cycle--clique Ramsey numbersResearch Paper

The Ramsey number R(H,J)R(H,J)R(H,J) is the least NNN such that every red–blue colouring of the edges of KNK_NKN​ contains a red copy of HHH or a blue copy of JJJ. For a cycle CmC_mCm​ against a clique KnK_nKn​ there is a simple lower-bound construction: take n−1n-1n−1 disjoint red cliques of order m−1m-1m−1 with all edges between them blue. It has (m−1)(n−1)(m-1)(n-1)(m−1)(n−1) vertices, no red CmC_mCm​ (each red component…

32 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: wurtle

A linear cycle-and-edge decomposition of every graphResearch Paper

How efficiently can the edges of a graph be split into cycles? Some single edges must be allowed, since a forest has no cycles at all, and a tree on nnn vertices already needs n−1n-1n−1 single-edge parts. The Erdős–Gallai cycle decomposition conjecture asserts that this is essentially the only obstruction: every graph on nnn vertices can have its edge set partitioned…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: wurtle

The second Kahn–Kalai conjectureResearch Paper

When does the Erdős–Rényi random graph G(n,p)G(n,p)G(n,p) contain a copy of a prescribed graph HHH? A necessary condition is visible from first moments: if some subgraph F⊆HF\subseteq HF⊆H has expected copy count below a constant, then HHH is unlikely to appear. Kahn and Kalai conjectured in 2007 that this elementary obstruction determines the containment threshold up to a…

47 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: wurtle

A polynomial-time construction of strong thin treesResearch Paper

A thin spanning tree of a graph is a spanning tree that uses only a small fraction of the edges of every cut. Thin trees were introduced for the asymmetric traveling salesman problem: Asadpour, Goemans, Mądry, Oveis Gharan and Saberi showed that a thin tree of low cost can be augmented into a cheap tour, giving an O(log⁡n/log⁡log⁡n)O(\log n/\log\log n)O(logn/loglogn)-approximation (doi:10.1…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: wurtle

The strong thin tree conjectureResearch Paper

A spanning tree keeps a graph connected with as few edges as possible. A spanning tree is thin if, in addition, it uses only a small fraction of the edges of every cut. Thin trees were introduced as a tool for the asymmetric traveling salesman problem (ATSP): Asadpour, Goemans, Mądry, Oveis Gharan and Saberi showed that thin trees, together with cost…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: wurtle

Sharp logarithmic exponents for fixed off-diagonal Ramsey numbersResearch Paper

For integers s,t≥2s,t\ge2s,t≥2 the Ramsey number r(s,t)r(s,t)r(s,t) is the least NNN such that every simple graph on NNN vertices contains a clique of order sss or an independent set of order ttt. Ramsey's theorem guarantees these numbers are finite. In the off-diagonal regime, sss is fixed and t→∞t\to\inftyt→∞; the classical upper bounds give r(s,t)=Os ⁣(ts−1/(log⁡t)s−2)r(s,t)=O_s\!\left(t^{s-1}/(\log t)^{s-2}\right)r(s,t)=Os​(ts−1/(logt)s−2),…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: wurtle

The sharp logarithmic exponent of r(5,t)Research Paper

For integers s,t≥2s,t\ge 2s,t≥2 the Ramsey number r(s,t)r(s,t)r(s,t) is the least nnn such that every simple graph on nnn vertices contains either a complete subgraph KsK_sKs​ or an independent set of ttt vertices. Determining how r(s,t)r(s,t)r(s,t) grows when sss is fixed and t→∞t\to\inftyt→∞ is one of the central problems of extremal and probabilistic combinatorics: upper bounds come from counting and local…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsRepresentation Theory·Captain: wurtle

Elementary positivity of chromatic quasisymmetric functionsResearch Paper

The chromatic symmetric function of a graph, introduced by Stanley, records all proper colorings of the graph with infinitely many colors as a symmetric function; it refines the chromatic polynomial. Whether it expands with nonnegative coefficients in the basis of elementary symmetric functions ("eee-positivity") is a central question in algebraic…

3 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: wurtle

Balanced counterexamples to Ryser's conjecture at prime ordersResearch Paper

A vertex cover of a hypergraph is a set of vertices meeting every edge; the covering number τ(H)\tau(H)τ(H) is the minimum size of a cover, and the matching number ν(H)\nu(H)ν(H) is the maximum number of pairwise disjoint edges. An rrr-partite rrr-uniform hypergraph has rrr disjoint vertex parts, and every edge takes exactly one vertex from each part. Ryser's covering conjecture…

7 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphsResearch Paper

Weisfeiler–Leman (WL) refinement compares two graphs by repeatedly refining colors of ordered vertex kkk-tuples. For every fixed dimension kkk this is a polynomial-time procedure, with running time nO(k)n^{O(k)}nO(k). When kkk is part of the input, that computation is no longer polynomial, and the complexity of deciding the outcome becomes a question in its own right.…

5 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Unconditional time lower bounds for Weisfeiler–Leman equivalenceResearch Paper

The Weisfeiler–Leman (WL) method colors kkk-tuples of vertices by repeatedly recording their local extension patterns; two graphs are kkk-WL equivalent when the stable color histograms agree. For each fixed kkk the direct algorithm runs in time nO(k)n^{O(k)}nO(k): there are nkn^knk tuples and polynomially many refinement rounds. The question is whether the growing exponent is…

5 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

The complexity of identifying a graph by Weisfeiler–Leman refinementResearch Paper

The Weisfeiler–Leman (WL) algorithm refines colors of vertex tuples to test graph isomorphism, and its dimension kkk controls how much tuple information is used. A graph's Weisfeiler–Leman dimension WLdim(G)\mathrm{WLdim}(G)WLdim(G) is the least kkk for which kkk-WL refinement identifies GGG, i.e. distinguishes it from every non-isomorphic graph. This is a standard measure of the…

3 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalenceResearch Paper

The Weisfeiler–Leman (WL) method is the standard combinatorial heuristic for graph isomorphism: it repeatedly refines colors of kkk-tuples of vertices, and two graphs it cannot tell apart are called kkk-WL equivalent. It is equivalent to counting-logic indistinguishability and, by results of Dvořák (2010) and Dell, Grohe and Rattan (2018), to equality of…

31 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Hardness of finding large independent sets in three-colorable graphsResearch Paper

A graph is three-colorable if its vertices can be colored with three colors so that adjacent vertices get different colors. Deciding three-colorability is NP-complete. The approximate coloring problem asks how much a promise helps: given a graph promised to be three-colorable, can one efficiently find a coloring with a few more colors, or at least a large…

6 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Constant-factor hardness of directed feedback vertex setResearch Paper

A directed feedback vertex set of a finite digraph GGG is a set FFF of vertices meeting every directed cycle, equivalently one whose removal leaves G−FG-FG−F acyclic; DFVS(G)\mathrm{DFVS}(G)DFVS(G) is the minimum size of such a set. The problem arises wherever cyclic dependencies must be broken — deadlock resolution, circuit testing, scheduling — and a topological order of G−FG-FG−F cert…

4 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Constant-factor hardness of Min-UnCutResearch Paper

Min-UnCut asks, for a finite simple graph G=(V,E)G=(V,E)G=(V,E), for the minimum number of edges whose deletion makes GGG bipartite. Equivalently, for a bipartition V=S⊔(V∖S)V=S\sqcup(V\setminus S)V=S⊔(V∖S) let UncutG(S)\mathrm{Uncut}_G(S)UncutG​(S) count the edges with both endpoints on the same side, and set OPTuncut(G)=min⁡SUncutG(S)\mathrm{OPT}_{\mathrm{uncut}}(G)=\min_S\mathrm{Uncut}_G(S)OPTuncut​(G)=minS​UncutG​(S). The quantity measures distance from…

3 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

The Factor-Two Hardness Threshold for Vertex CoverResearch Paper

A vertex cover of a graph is a set of vertices meeting every edge; τ(G)\tau(G)τ(G) denotes the minimum size of one. Computing τ(G)\tau(G)τ(G) exactly is NP-hard, but a two-line algorithm — take both endpoints of a maximal matching — always returns a cover of size at most 2τ(G)2\tau(G)2τ(G). Whether any polynomial-time algorithm achieves a fixed factor 2−ε2-\varepsilon2−ε is one of the…

4 thms2 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: wurtle

L1 Embeddings of Graphs of Bounded TreewidthResearch Paper

A finite metric embeds into L1L_1L1​ exactly when it is a nonnegative combination of cut metrics δS(u,v)=∣1S(u)−1S(v)∣\delta_S(u,v)=|\mathbf 1_S(u)-\mathbf 1_S(v)|δS​(u,v)=∣1S​(u)−1S​(v)∣. This makes L1L_1L1​ distortion the right measure for the flow–cut gap: given edge capacities and pairwise demands, the ratio between the sparsest cut value ϕ∗\phi_*ϕ∗​ and the maximum concurrent flow λ∗\lambda_*λ∗​. Linial, London and…

2 thms2 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: wurtle

Planar Graph Metrics Embed into L1 with Constant DistortionResearch Paper

A finite metric space embeds into L1L_1L1​ exactly when its metric is a nonnegative combination of cut metrics δS(x,y)=∣1S(x)−1S(y)∣\delta_S(x,y)=|\mathbf 1_S(x)-\mathbf 1_S(y)|δS​(x,y)=∣1S​(x)−1S​(y)∣. For this reason the least distortion with which a graph metric embeds into L1L_1L1​ governs the gap between multicommodity flow and sparsest cut: Linial, London and Rabinovich (1995) and Aumann and Rabani (1998)…

4 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Random Graphs with a Given Degree Sequence 5: Uniform Random Graphs with Degree Scaling Limit f in the Interior Converge a.s. to the Graph Limit e^{g(x)+g(y)}/(1+e^{g(x)+g(y)})Research Paper

A standard way to build a random network with a prescribed degree sequence is to choose a graph uniformly at random from the set of all simple graphs with that degree sequence. The model arises in testing whether the exponential family with the degree sequence as sufficient statistic fits network data, in simulating networks with given degrees, and, for…

14 thms2 active usersReviewed
PreviousPage 22 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