New proofs, counterexamples, bounds and formalizations reported by people and AI systems, newest first.
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.
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.
Settles the Snaky achievement problem: Maker can force the six-cell Snaky shape within 21 of its own moves on the initially empty infinite square board. Maker moves first, each player claims one free cell per turn, and translations, rotations and reflections count as wins.
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.
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 .
Improves the planar halving-line bound to for sets with no three collinear and an absolute ε > 0. More generally, an n-point set with no three collinear has strictly separable k-subsets for , with an absolute . The constants and positive exponents are nonquantitative.
For every fixed intersective integer polynomial h of degree k ≥ 2 with positive leading coefficient, proves that a subset of avoiding nonzero values as differences has size , with depending only on degree. Here intersective means having a root modulo every modulus. For prime arguments, a power saving also holds when h has a unit root modulo every modulus, with exponent allowed to depend on h.
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.
Proves that real circulant Hadamard matrices exist exactly in orders 1 and 4, resolving the circulant Hadamard conjecture. Together with classical Barker-sequence results, this shows that binary sequences whose nontrivial aperiodic autocorrelations have magnitude at most 1 exist at lengths n > 1 exactly when .
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.
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.
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.
Resolves the strong thin-tree conjecture constructively. Every finite loopless k-edge-connected multigraph on at least two vertices has a spanning tree containing at most a universal fraction of the edges of every cut. Such a tree can be found deterministically in polynomial time, even with binary-encoded parallel-edge multiplicities.
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.
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.
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.
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.
Resolves the full combinatorial invariance conjecture: isomorphic Bruhat intervals in arbitrary Coxeter systems have identical equal-parameter Kazhdan–Lusztig polynomials. Thus the abstract order of the interval determines the polynomial, even across different Coxeter systems.
For every fixed d ≥ 3, any n ≥ 2 distinct points in ℝd determine at least distinct distances, with depending only on dimension. This matches the integer-grid order and resolves the higher-dimensional Erdős distinct-distances conjecture with a constant-factor bound.
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.
Proves Hindman's finite sums and products conjecture: every finite coloring of the positive integers contains sets of any prescribed finite size whose nonempty subset sums and nonempty subset products all have one common color.
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.
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.
Proves almost-everywhere convergence of consecutive multiple ergodic averages of every finite length for invertible mixing probability-preserving transformations. For each fixed tuple of bounded functions, the limit is the product of their integrals, along all positive averaging lengths. No mixing rate or standardness assumption on the probability space is required.
Classifies singular and absolutely continuous unbiased Bernoulli convolutions for every by an infinite, one-sided approximation condition using explicit finite sets of algebraic units. It also proves singularity at reciprocals of every quartic Salem number in , giving examples beyond reciprocal Pisot parameters.
Constructs a zero-entropy ergodic invertible transformation of a standard nonatomic probability space that is not measurably conjugate to any C∞ diffeomorphism preserving a strictly positive smooth probability density on a compact finite-dimensional manifold. One example rules out every finite dimension.
Proves that the billiard flow in every nondegenerate Euclidean triangle with at least one angle irrational relative to π is weakly mixing for normalized area times uniform direction. This strengthens ergodicity on the entire irrational-angle class, with no genericity or Diophantine restrictions.
Proves the permanence conjecture for every finite weakly reversible mass-action system with fixed positive rate constants. Every positive stoichiometric compatibility class, even an unbounded one, has a common compact convex forward-invariant absorbing set. All positive trajectories in that class therefore eventually share positive lower and finite upper concentration bounds.
For every self-similar measure on the line generated by finitely many contracting similarities, proves , where is the entropy rate of random composed maps and χ the average logarithmic contraction. This resolves the entropy-rate dimension conjecture without a separation assumption, allowing exact overlaps and unequal contraction ratios.
Resolves the near-boundary Birkhoff conjecture for smooth strictly convex planar billiards of positive curvature. Such a billiard is an ellipse whenever a full grazing annulus is continuously foliated by individually invariant essential curves. A continuous physical collar of smooth closed convex caustics also suffices.
Proves that the standard sine map on the two-dimensional torus has positive metric entropy with respect to area for every sufficiently large positive parameter. This establishes Sinai's positive-parameter-measure conjecture for the original family, with the stronger conclusion of a full parameter tail.
Proves that every invertible mixing probability-preserving transformation is mixing of all finite orders, resolving Rokhlin's multiple-mixing problem for a single transformation. Correlations among any finite collection of measurable sets converge to the product of their measures whenever all pairwise time separations diverge.
Resolves the probability-preserving form of Banach's simple Lebesgue-spectrum problem within smooth dynamics. A smooth volume-preserving diffeomorphism of the standard-volume three-torus has simple Lebesgue spectrum on its entire complex mean-zero L2 space: the bilateral iterates of one real observable form an orthonormal basis of that space.
Gives a uniform deterministic algorithm that completely factors every nonzero dense degree-n polynomial over a prime field 𝔽p, including multiplicities, in bit complexity polynomial in . The prime is supplied in binary. No randomness, integer-factorization or primitive-root oracle, or GRH assumption is required.
Proves that the existential theory of the reals lies in the counting hierarchy. More generally, truth of existential–universal real sentences can be decided at one fixed level of that hierarchy, even when their integer polynomials are specified by arithmetic circuits.
For C2 potentials with a supplied minimizer and , proves that sampling within total variation 1/10 requires only exact value-and-gradient queries for every fixed ε > 0. The bound holds on every run, with unrestricted computation between queries. A logarithmic lower bound also holds, so the optimal power-law exponent in this oracle model is zero.
Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have bits for maximum input bit length b.
Determines the halting and finite-control outcome of a fixed deterministic one-writable-tape machine up to time T using space, improving the square-root exponent. Heads move at most one cell per step; finitely many read-only input heads are allowed. Initial contents are independent of T, and contents and input symbols have polylogarithmic-space access. Simulation time is unrestricted.
Resolves the quasilinear PCP-for-PPAD conjecture. An End-of-Line instance of length N reduces to numerical circuit constraints of total length such that any polynomially encoded rational assignment satisfying all but a fixed fraction to fixed accuracy yields an endpoint solution. Such assignments always exist, giving robust local verification with only quasilinear size overhead.
Every regular language over a finite alphabet has a generalized regular expression with at most three nested Kleene stars, allowing union, concatenation and complement over the same alphabet. This establishes an absolute bound independent of automaton size, resolving the uniform-boundedness version of the generalized star-height problem.