Graph theory
A graph is a set of dots joined by lines. Graph theory studies colourings, cycles and patterns in these networks.
40 AI-made results on graph theory, from 67 papers in the OpenAI math collection, each explained in plain English. 33 have a formal Lean proof listed; 7 are claimed in a paper and not yet machine-checked. They span 8 fields, led by combinatorics (21), theoretical computer science (7) and probability and statistical mechanics (4). The oldest question here dates back to 1935: Sharp logarithmic exponents for off-diagonal Ramsey numbers. Results rated Landmark include The Unique Games Conjecture and optimal approximation thresholds and Graph coloring, clique minors, and Colin de Verdière invariants.
Number theory1
-
Uniformly bounded components of Gaussian-prime graphs
Proves the Gaussian moat conjecture: no infinite walk through distinct Gaussian primes can have uniformly bounded steps. More strongly, for every distance bound D, the graph joining Gaussian primes at distance at most D has uniformly bounded finite component sizes, depending only on D, including primes on the coordinate axes.
Formal proof listed
Convex and metric geometry1
-
Bounded-distortion L1 embeddings of planar and bounded-treewidth graphs
Resolves the planar and bounded-treewidth cases of the Gupta–Newman–Rabinovich–Sinclair conjecture. Shortest-path metrics of finite connected graphs with arbitrary positive edge lengths embed into real L1 with universal distortion for planar graphs, and distortion depending only on treewidth for bounded-treewidth graphs. The corresponding multicommodity flow–cut gaps are uniformly bounded.
Formal proof listed
Theoretical computer science7
-
The Unique Games Conjecture and optimal approximation thresholds
Proves Khot's Unique Games Conjecture. Independent direct reductions also establish NP-hardness, on unweighted graphs, of approximation beyond the Goemans–Williamson ratio for Max-Cut, below factor two for Vertex Cover, and within any fixed constant factor for Min-UnCut and directed feedback vertex set. These direct proofs use established PCP and Label Cover hardness results.
Formal proof listed -
Hardness of coloring three-colorable graphs
It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed , a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs that are three-colorable in the satisfiable case and have no independent set of size otherwise, where n is the number of vertices.
Formal proof listed -
Approximate counting and entropy of perfect matchings
Gives a fully polynomial randomized approximation scheme for counting perfect matchings in arbitrary finite simple graphs, with exact detection of zero counts. Also proves the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant, bounding the maximum entropy of a matching law at every feasible edge-marginal vector in a loopless labelled multigraph, including boundary points.
Formal proof listed -
Almost-linear-time exact matching and prescribed-degree factors in general graphs
Gives a randomized algorithm finding an exact maximum-cardinality matching in any simple undirected graph in word time, with success probability at least 2/3. The time bound holds on every computation path. The same guarantees apply to finding a spanning subgraph with prescribed admissible vertex degrees, or deciding that none exists.
Claimed, not checked -
Polynomial-time scheduling on three identical machines
Resolves the three-processor unit-job scheduling problem of Garey and Johnson: a deterministic polynomial-time algorithm minimizes makespan for nonpreemptive unit-length jobs with arbitrary precedence constraints on three identical parallel machines. For an explicitly given precedence graph, it decides deadline feasibility exactly and constructs a feasible schedule.
Formal proof listed -
Rapid mixing of graph switches for every degree sequence
Resolves the simple-undirected Kannan–Tetali–Vempala conjecture: the lazy edge-switch chain mixes in time for every graphical labeled degree sequence. The same degree-constrained graphs can also be sampled exactly uniformly by an almost-surely terminating algorithm with expected polynomial bit running time.
Formal proof listed -
The computational complexity of Weisfeiler–Leman refinement
Proves unconditional deterministic time lower bounds for joint and separate k-dimensional Weisfeiler–Leman equivalence, for sufficiently large fixed k in the specified sequential adjacency-matrix models. With dimension as input, joint equivalence is EXPTIME-complete even on subcubic graphs; deciding whether refinement identifies a graph is also EXPTIME-complete.
Formal proof listed
Combinatorics21
-
Graph coloring, clique minors, and Colin de Verdière invariants
Disproves Hadwiger's conjecture even for fractional coloring: arbitrarily large finite simple graphs with independence number at most two satisfy , where is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound . In the positive direction, every finite nonempty graph satisfies for a universal constant C.
Formal proof listed -
The Euclidean plane cannot be colored with five colors
Proves that every five-coloring of the Euclidean plane has a monochromatic pair at distance one, with no restriction on the color classes. This advances the Hadwiger–Nelson problem: together with the classical seven-coloring, only six and seven remain possible chromatic numbers of the plane.
Formal proof listed -
Superexponential van der Waerden numbers
Resolves Erdős's superexponential-growth question for van der Waerden numbers. If is the least interval length forcing a monochromatic k-term progression in every r-coloring, then for an absolute c > 0, all r ≥ 2 and sufficiently large k, uniformly in r. In particular, for each fixed r.
Formal proof listed -
Counterexamples to Sidorenko’s conjecture and the forcing conjecture
Disproves Sidorenko's conjecture with a connected bipartite pattern on 35 vertices and 66 edges that occurs less frequently than in a random graph of the same edge density. The same pattern disproves the forcing conjecture of Skokan and Thoma: matching its density and the edge density of a constant graphon need not force quasirandomness.
Formal proof listed -
Counterexamples to Ryser’s covering conjecture
Disproves Ryser's covering conjecture by constructing intersecting -partite, -uniform hypergraphs with covering number , rather than the predicted bound q, for every sufficiently large prime q. A separate construction over extension fields also disproves Gyárfás's monochromatic tree-cover conjecture.
Formal proof listed -
The Harary–Hill and Zarankiewicz crossing-number formulas
Resolves the Harary–Hill conjecture and Turán's brickyard problem in the Zarankiewicz formulation, determining the crossing numbers of every complete and complete bipartite graph. The result proves the optimality of the classical drawings among all plane drawings with continuous edge arcs.
Formal proof listed -
Shareshian–Wachs elementary positivity
Resolves the elementary-positivity part of the Shareshian–Wachs conjecture: the chromatic quasisymmetric function of every natural unit interval graph has elementary-basis coefficients in . The coefficients count explicitly described permutations, giving a combinatorial explanation of positivity.
Formal proof listed -
Sharp logarithmic exponents for off-diagonal Ramsey numbers
For every fixed integer s ≥ 5, proves as , determining the logarithmic exponent and matching the classical upper bound at that scale. Here is the least number of vertices forcing an s-clique or a t-vertex independent set.
Formal proof listed -
The hypercube Ramsey conjecture
Resolves the Burr–Erdős hypercube Ramsey conjecture: the two-color Ramsey number of the n-dimensional cube is . Thus every red-blue coloring of a complete graph on a universal constant times the cube's number of vertices contains a monochromatic copy of the cube.
Claimed, not checked -
Classification of finite Euclidean Ramsey configurations
Classifies finite point configurations that occur monochromatically, at their original scale, in every finite coloring of sufficiently high-dimensional Euclidean space. The characterization is an algebraic condition over the coordinate field. It also disproves the Leader–Russell–Walters conjecture that every such configuration is a subset of a finite transitive set.
Formal proof listed -
Seymour’s second-neighborhood conjecture
Proves Seymour's second-neighborhood conjecture: every nonempty finite oriented graph has a vertex with at least as many vertices at directed distance exactly two as at directed distance one. Oriented graphs may be arbitrary apart from the exclusion of loops and oppositely directed edge pairs.
Formal proof listed -
Talagrand’s expectation thresholds, discrete convexity, and graph decompositions
Proves that integral and fractional expectation thresholds differ by at most a universal factor, and resolves Talagrand's discrete-convexity conjecture. An application proves the Ascoli–He–Park–Talagrand graph-decomposition conjecture: every graph's edges split into a universally bounded number of fixed pieces, each with containment threshold at most a universal constant times the original graph's integral expectation threshold. The pieces' embeddings need not agree on shared vertices.
Formal proof listed -
The second Kahn–Kalai conjecture with an edge-count bound
Proves the second Kahn–Kalai conjecture: for every finite simple graph H with h ≥ 1 edges and at most n vertices, its appearance threshold in is at most , with universal C. Here is the least density at which every subgraph of H has expected copy count at least 1/2.
Formal proof listed -
Bounded-degree coboundary expanders
Constructs arbitrarily large finite d-dimensional simplicial complexes, for every d ≥ 3, with uniformly bounded vertex degrees and uniform 𝔽2 coboundary expansion in every degree below d. Together with the known graph and two-dimensional cases, this establishes the existence of such expanders in every positive dimension.
Formal proof listed -
Deterministic nonbipartite Ramanujan graphs in every fixed degree
For every fixed d ≥ 3, constructs a simple d-regular nonbipartite Ramanujan graph on every sufficiently large even number n of vertices, with every nonconstant adjacency eigenvalue strictly between and . A deterministic algorithm outputs the full adjacency list in polynomial bit time, with exponent depending on d.
Claimed, not checked -
Barnette’s Hamiltonian-cycle conjecture
Proves that every finite simple cubic bipartite planar 3-vertex-connected graph has a Hamiltonian cycle, resolving Barnette's conjecture. Equivalently, every three-edge path in a finite simple cubic 3-vertex-connected bipartite Pfaffian graph lies in a Hamiltonian cycle.
Formal proof listed -
The Erdős–Gallai cycle-decomposition conjecture
Proves that the edges of every finite simple undirected graph on n vertices can be partitioned into at most simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle-decomposition conjecture, bounding the number of pieces linearly even for dense graphs.
Formal proof listed -
Correspondence coloring with a fixed forbidden subgraph
Proves the Alon–Krivelevich–Sudakov coloring conjecture in correspondence-coloring form: graphs avoiding any fixed subgraph F need colors when their maximum degree Δ is sufficiently large. Also proves the Ajtai–Erdős–Komlós–Szemerédi independence conjecture: for fixed r ≥ 4, every n-vertex Kr-free graph of average degree d ≥ 2 has an independent set of size .
Formal proof listed -
Uniform influence and sharp thresholds for graph and hypergraph properties
Proves the Friedgut–Kalai threshold-width conjectures for graphs and fixed-uniformity hypergraphs. For fixed , every nontrivial increasing relabeling-invariant property crosses from probability ε to within width for graphs and for r-uniform hypergraphs, r ≥ 3. The hypergraph influence bound also applies to nonmonotone properties.
Formal proof listed -
The sharp terminal leave in random triangle removal
Starting from the complete graph on n vertices, repeatedly delete a uniformly chosen remaining triangle. The terminal edge count is asymptotic to , with mean-square convergence after normalization by n3/2. This proves the triangle case of the Joos–Kühn sharp-constant conjecture.
Formal proof listed -
Cycle–clique Ramsey numbers
Proves the Erdős–Faudree–Rousseau–Schelp conjecture: for every , except . This is the exact threshold forcing a red m-cycle or a blue n-clique in every red–blue coloring of a complete graph.
Formal proof listed
Probability and statistical mechanics4
-
Critical percolation on every quasi-transitive graph
Resolves the Benjamini–Schramm criticality conjecture for bond percolation on every infinite connected locally finite quasi-transitive graph with : at the critical probability, there is almost surely no infinite cluster. The family also establishes this conclusion for both nearest-neighbor bond and site percolation on ℤ3.
Formal proof listed -
The Benjamini–Schramm nonuniqueness conjecture
Proves for Bernoulli bond percolation on every infinite connected locally finite nonamenable quasi-transitive graph, resolving the Benjamini–Schramm nonuniqueness conjecture. Thus there is a nonempty range of probabilities with infinitely many infinite clusters. A stronger operator bound also establishes the critical triangle condition.
Formal proof listed -
GOE bulk universality for regular graphs with weak Anderson disorder
For every fixed degree d ≥ 3, the bulk adjacency-eigenvalue point process of a uniform simple random d-regular graph converges to the Gaussian orthogonal ensemble law, including for cubic graphs. The same fixed-energy universality persists under sufficiently weak fixed iid uniform diagonal disorder, throughout compact bands strictly inside the clean spectral edges.
Claimed, not checked -
The free uniform spanning forest is a factor of IID
On every infinite connected locally finite simple unweighted graph, the free uniform spanning forest is a factor of independent vertex labels, by one isomorphism-equivariant rule using no root. Translation-invariant strongly Rayleigh binary processes on every countable group, including invariant determinantal processes with Hermitian positive-contraction kernels, are also factors of IID.
Formal proof listed
Mathematical physics1
-
QAOA attains the SK optimum in the thermodynamic-first limit
Proves that QAOA approaches the ground-state energy of the Gaussian zero-field Sherrington–Kirkpatrick model when system size tends to infinity before circuit depth. For every accuracy, finite depth and deterministic angles independent of size and disorder achieve the required limiting expected energy per spin. This also yields leading-order optimal expected MaxCut values on large-degree random regular graphs, with size tending to infinity before degree.
Formal proof listed
Topology4
-
Failure of rational injectivity for maximal coarse assembly
Constructs a uniformly discrete bounded-geometry space whose maximal coarse assembly map is not rationally injective. The example is a coarse disjoint union of finite connected graphs of uniformly bounded degree, with an infinite-order kernel class. A companion gives the analogous failure for reduced coarse assembly, disproving the rational coarse Novikov conjecture.
Formal proof listed -
Cyclic length and chromatic fixed-point loss
Determines the optimal chromatic loss from geometric H-fixed points to geometric G-fixed points for every subgroup H of a finite p-group G. At every nonnegative height, the loss equals the shortest subnormal-chain length from H to G with cyclic quotients. Each quotient counts once regardless of order, and finite spectra witness sharpness.
Claimed, not checked -
Chromatic splitting: filtrations and counterexamples
Disproves strong chromatic splitting at height three for primes p ≥ 5, and weak splitting for the derived p-completed sphere at heights p (p ≥ 5) and (p ≥ 7). Nevertheless, for n ≥ 1 and , the overlap admits a -stage filtration by the predicted localized-sphere pieces. At height three and prime three, even finite assembly from such pieces fails in the category of -local modules over the derived completed sphere.
Claimed, not checked -
Counterexamples to finite generation at chromatic height two
Refutes the Hahn–Wilson conjecture at chromatic height two. For every sufficiently large prime p, constructs a connective p-complete spectrum of exact fp-type two that cannot be built from completed by finitely many sums, shifts, cones and retracts. The examples nevertheless satisfy the finite and telescopic localization comparisons.
Claimed, not checked
Differential geometry1
-
Affine Bernstein rigidity through dimension nine and a smooth dimension-ten counterexample
Proves that every smooth locally uniformly convex affine-maximal graph of dimension three through nine, complete for its induced Euclidean metric, is an elliptic paraboloid. A smooth entire nonquadratic example in dimension ten makes this range sharp. In dimensions three through nine, the paraboloid classification also holds for connected open locally uniformly convex affine-maximal hypersurfaces complete for the affine Berwald–Blaschke metric.
Formal proof listed