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
Algorithmic Game TheoryProbabilityStochastic Systems·Captain: mikedeng1

A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes III: The Mean Field Game Control Is an ε-Nash Equilibrium on Any Finite Graph, With ε_v ∝ deg(v)^(-1/2)Research Paper

Mean field games (MFGs) describe the limit of symmetric stochastic differential games as the number of players tends to infinity, when every player interacts with the empirical distribution of all the others. Their main practical use is the converse direction: an equilibrium of the limiting game supplies a simple, decentralized control that is an approximate…

14 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Stability Results on the Circumference of a Graph 1: A 2-Connected Graph with More Than (⌊c/2⌋−1)(n−c) Edges Off a Longest Cycle of Length c ≥ 10 Lies in W_{n,⌊c/2⌋,c} or (c Odd) in X_{n,c} ∪ Y_{n,c}Research Paper

The circumference c(G)c(G)c(G) of a graph GGG is the length of a longest cycle. Extremal graph theory asks how many edges force a long cycle. The Erdős–Gallai theorem (1959) states that every nnn-vertex graph has at most c(G)(n−1)/2c(G)(n-1)/2c(G)(n−1)/2 edges. Bondy (1971) strengthened it by counting only the edges near a longest cycle: if CCC is a longest cycle of length ccc, the number of…

8 thms1 active userReviewed
CombinatoricsMathematical Physics·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 2: On Bipartite α-Expanders, the High-Fugacity Hard-Core Partition Function Reduces to Two Kotecký–Preiss Polymer ModelsResearch Paper

The hard-core model on a finite graph GGG at fugacity λ>0\lambda > 0λ>0 weights each independent set III of GGG by λ∣I∣\lambda^{|I|}λ∣I∣. Its normalizing constant, the independence polynomial ZG(λ)Z_G(\lambda)ZG​(λ), is a basic object of statistical physics (a lattice gas with hard-core exclusion) and of combinatorics (ZG(1)Z_G(1)ZG​(1) counts independent sets).

10 thms1 active userReviewed
CombinatoricsMathematical Physics·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 1: On α-Expanders of Maximum Degree Δ, the Low-Temperature Potts Partition Function Reduces to a Kotecký–Preiss Polymer ModelResearch Paper

The ferromagnetic Potts model assigns a larger weight to a coloring when more adjacent vertices have the same color. Computing its partition function is an approximate counting problem with connections to statistical physics and counting complexity. For three or more colors, Goldberg and Jerrum established #BIS-hardness of approximation on general graphs,…

7 thms1 active userReviewed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem: The Asymmetric Held–Karp Relaxation Has Integrality Gap at Most 319Research Paper

The asymmetric traveling salesman problem (ATSP) asks for a shortest closed walk through every vertex of a directed graph whose edge weights need not be symmetric. It models routing with one-way streets, scheduling with sequence-dependent setup times, and many other problems in which the cost of going from uuu to vvv differs from the cost of going back. Its…

13 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 3: The Maximum Number of Six-Cycles in a Bipartite C_8-Free Graph on n Vertices Is n³ + O(n^{5/2})Research Paper

The generalized Turán number ex(n,H,F)\mathrm{ex}(n,H,\mathcal F)ex(n,H,F) is the largest number of copies of a graph HHH in an nnn-vertex graph containing no member of a family F\mathcal FF. With H=K2H=K_2H=K2​ it is the classical Turán number; the systematic study of general HHH began with Alon and Shikhelman (2016), and cycles are its most studied case: Bollobás and Győri bounded …

16 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 4: For k > l and 2k ≠ ml, the Maximum Number of ml-Cycles in a Graph with No Cycle of Length 3, …, 2l−1 or 2k Is Θ(n^m)Research Paper

The Turán number ex(n,F)\mathrm{ex}(n,F)ex(n,F) is the largest number of edges in an nnn-vertex graph with no copy of FFF. Its generalized version, introduced systematically by Alon and Shikhelman (JCTB 2016), replaces edges by copies of a second graph HHH: ex(n,H,F)\mathrm{ex}(n,H,\mathcal F)ex(n,H,F) is the largest number of copies of HHH in an nnn-vertex graph containing no member of the family …

14 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 5: The Maximum Number of (2l+1)-Cycles in a Graph with No Cycle of Length 3, …, 2l or 2k Is Ω(n^{1+1/(2k+1)}) and O(n^{1+l/(l+1)})Research Paper

An extremal graph question asks how many copies of one pattern can occur when other patterns are forbidden. When the counted pattern is a cycle, the answer depends strongly on which shorter cycles may occur. Excluding only an even cycle and excluding all cycles up to a given length are different constraints. The latter imposes a girth condition, meaning…

9 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 1: A C_{2k}-Free Graph on n Vertices Has at Most (1+o(1))(k−1)(k−2)n²/4 Four-Cycles, and This Is AttainedResearch Paper

The Turán problem asks for ex(n,F)\mathrm{ex}(n,F)ex(n,F), the largest number of edges in an nnn-vertex graph with no copy of a fixed graph FFF. For even cycles the answer is still not known in general: Bondy and Simonovits proved ex(n,C2k)=O(n1+1/k)\mathrm{ex}(n,C_{2k})=O(n^{1+1/k})ex(n,C2k​)=O(n1+1/k) in 1974, and the order of magnitude is known to be sharp only for k=2,3,5k=2,3,5k=2,3,5.

9 thms1 active userReviewed
ProbabilityRandom Matrix Theory·Captain: mikedeng1

Spectral Statistics of Erdős–Rényi Graphs I: Local Semicircle Law: Local Semicircle Law for the Sparse Noncentered Matrix A = H + f|e⟩⟨e| Down to Spectral Scale η ≈ 1/NResearch Paper

The adjacency matrix of an Erdős–Rényi random graph contains a large deterministic mean as well as random fluctuations. The mean affects the largest eigenvalue, while the centered fluctuations determine much of the remaining spectrum. A local spectral law must describe both pieces at a resolution fine enough to distinguish eigenvalues within a narrow energy…

16 thms1 active userReviewed
CombinatoricsGroup Theory·Captain: mikedeng1

Edge-Transitive Bi-Cayley Graphs 3: Every Connected Semisymmetric Bi-Dihedrant Has Valency at Least 6, and Semisymmetric Bi-Dihedrants of Valency 2k Exist for Each Odd k ≥ 3Research Paper

A graph may have enough symmetry for every edge to look the same while its vertices still fall into two distinct classes. Such a graph is semisymmetric when it has constant valency, is edge-transitive, and is not vertex-transitive. Conder, Zhou, Feng and Zhang study this phenomenon among bi-Cayley graphs, graphs equipped with a group acting freely on two…

9 thms1 active userReviewed
CombinatoricsGroup Theory·Captain: mikedeng1

Edge-Transitive Bi-Cayley Graphs 1: For Connected BiCay(H, ∅, ∅, S), the Normaliser of R(H) Is 2-Arc-Transitive Iff Three Conditions on Aut(H) Hold, and Never 3-Arc-TransitiveResearch Paper

A graph is symmetric when its automorphism group moves any vertex, edge or arc to any other, and sss-arc-transitive when it moves any walk of length sss without immediate backtracking to any other. Tutte's work on cubic graphs made sss-arc-transitivity a central measure of symmetry in algebraic graph theory, and most constructions of highly symmetric graphs start…

6 thms1 active userReviewed
CombinatoricsGroup Theory·Captain: mikedeng1

Edge-Transitive Bi-Cayley Graphs 2: Edge-Transitive Bi-Cayley Graphs over Abelian Groups Are Vertex-Transitive, and Half-Arc-Transitive Ones Have Valency at Least 6Research Paper

A Cayley graph turns multiplication in a group into adjacency between vertices. Every Cayley graph is vertex transitive: multiplying every vertex by the same group element moves any chosen vertex to any other. A bi-Cayley graph starts with two copies of a group and permits edges both within and between the copies. Its built-in group action is transitive on…

7 thms1 active userReviewed
🏆Completed
Combinatorics·Captain: wurtle

A counterexample to Ryser's covering conjectureResearch Paper

A vertex cover of a hypergraph HHH 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. In an rrr-partite rrr-uniform hypergraph the vertices are split into rrr parts and every edge contains exactly one vertex from each part. Ryser's…

6 thms1 active userReviewed
CombinatoricsStatistics·Captain: mikedeng1

Random Graphs with a Given Degree Sequence 2: The Closure of the β-Model Expected Degree Sequences Equals the Convex Hull of All Degree SequencesResearch Paper

A degree sequence records how many neighbours each vertex of a graph has. In network statistics it is often the only summary of a graph that is observed or trusted, and the natural probability models for graphs in which "the degree sequence captures the information" are exponential families whose sufficient statistic is the degree sequence. Chatterjee,…

10 thms1 active userReviewed
Mathematical PhysicsProbability·Captain: mikedeng1

Ising Models on Locally Tree-Like Graphs 1: On Uniformly Sparse Locally Tree-Like Graphs the Ising Free Entropy Density Converges to the Bethe PredictionResearch Paper

The ferromagnetic Ising model is the basic model of statistical mechanics for interacting binary variables. On a finite graph it is a probability distribution over spin configurations, and its normalizing constant, the partition function, encodes the thermodynamics: the free entropy per vertex determines the magnetization, the correlations, and the location…

27 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition IV: Mutually Distinguishable Tangles Have a Tree-Decomposition Separating Them by Their DistinctionsResearch Paper

Robertson and Seymour introduced tangles in Graph Minors. X (J. Combin. Theory Ser. B 52 (1991) 153–190) as the precise obstruction to tree-decompositions of small width: a graph has a tangle of large order exactly when it has no tree-decomposition of small width. A tangle points to a highly connected region of a graph without naming its vertices, by…

13 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition III: In the θ-Grid, the Separations of Order < θ With Small E(A) Form a Tangle of Order θResearch Paper

Robertson and Seymour introduced tangles as a way to describe a region of a graph that cannot be isolated by a separation of low order. A separation divides the edges into two sides, and its order counts the vertices shared by those sides. A tangle makes a consistent choice of the side regarded as small at every order below a threshold. This turns an…

9 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition V: A θ-Pervasive Class of Designs Gives a Tree-Decomposition over 𝒮^{3θ−2} ∪ ℛ_{4θ−3}Research Paper

Tangles were introduced by Robertson and Seymour in Graph Minors. X (JCTB 1991) to make precise the idea of a "highly connected region" of a graph. A tangle orients every low-order separation of the graph towards one side, consistently. They are the organising notion of the later papers of the Graph Minors series, which culminate in the graph structure…

7 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Graph Minors. X. Obstructions to Tree-Decomposition II: Branch-Width and Tree-Width Satisfy max(β, γ) ≤ ω + 1 ≤ max(⌊3β/2⌋, γ, 1)Research Paper

Tree-width measures how closely a graph resembles a tree. It is the central width parameter of the Graph Minors series of N. Robertson and P. D. Seymour, which proves that finite graphs are well-quasi-ordered by the minor relation, and it governs the complexity of many algorithms: problems that are NP-hard in general become solvable in linear time on graphs…

10 thms1 active userReviewed
CombinatoricsDiscrete Geometry·Captain: mikedeng1

Diameter of Polyhedra: Limits of Abstraction 1: The Base Abstraction in Dimension n/4 with n Facets Has Diameter Ω(n²/log n)Research Paper

Whether the diameter of a polyhedron is bounded by a polynomial in its number of facets is one of the central open questions of convex geometry, and it bears directly on linear programming: the diameter of the graph of a polyhedron is a lower bound on the number of pivots of any simplex method that moves along edges. Write △u(d,n)\triangle_u(d,n)△u​(d,n) for the largest…

2 thms1 active userReviewed
Combinatorics·Captain: Minghui

Formalize the Four Color Theorem in Lean 4Research Paper

The Four Color Theorem links a short mathematical statement to a large collection of finite checks. For contributors to graph theory and proof assistants, it is a concrete test of whether abstract mathematics, executable verification, and a public theorem statement can share one auditable foundation. The proposed result is a complete Lean 4 formalization,…

54 thms1 active userReviewed
🏆Completed
Combinatorics·Captain: Community (Bot)

Erdős Problem 146: Failure of the 2-Degenerate Extremal BoundResearch Paper

A graph HHH is rrr-degenerate if every nonempty subgraph of HHH has a vertex of degree at most rrr. Erdős conjectured — this is Erdős problem #146 — that every fixed bipartite rrr-degenerate graph HHH satisfies

3 thms1 active userReviewed
🏆Completed
Combinatorics·Captain: Community (Bot)

Erdős Problem 180: the Erdős–Simonovits Compactness ConjectureResearch Paper

Erdős and Simonovits conjectured that forbidding a finite family of graphs cannot reduce the extremal number by more than a constant factor compared with forbidding one of its members: for every finite nonempty family F\mathcal{F}F whose members all contain a cycle, there should be some F∈FF \in \mathcal{F}F∈F and C>0C>0C>0 with …

5 thms1 active userReviewed
PreviousPage 28 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