Combinatorics

We construct a finite translational tile in ℤ³ that admits tilings but no fully periodic tiling. Its unit-cube thickening has the same property in ℝ³, even when arbitrary real translations are allowed. This gives a negative resolution of the periodic tiling conjecture in dimension three.

The compact set of rank-one orthogonal projectors on ℝ⁴, with the Frobenius metric, cannot be covered by ten sets of strictly smaller diameter. It therefore gives a counterexample to Borsuk's conjecture in dimension nine.

We prove that every finite nonempty graph G satisfies \(\chi_{\mathrm{list}}(G)\le C h(G)\) for an absolute integer C, where \(h(G)\) is the largest order of a clique minor. This resolves the Linear List Hadwiger conjecture affirmatively.

We disprove the Colin de Verdière chromatic conjecture by constructing graphs whose chromatic number exceeds their Colin de Verdière invariant by more than one. The examples have independence number at most two. In fact, their ordinary fractional chromatic number also exceeds their Colin de Verdière invariant by more than one.

We disprove Hadwiger's conjecture by constructing arbitrarily large graphs whose chromatic number exceeds their Hadwiger number. The examples have independence number at most two, and even their ordinary fractional chromatic number exceeds their Hadwiger number. Thus they also disprove the fractional-coloring weakening discussed by Reed and Seymour.

We prove that every coloring of the Euclidean plane with five colors has a monochromatic unit-distance pair, with no regularity assumption on the color classes. Consequently, the chromatic number of the plane is either six or seven.

We prove Erdős's conjecture that every set of positive integers with divergent reciprocal sum contains arithmetic progressions of every finite length. More quantitatively, for every fixed k ≥ 3, we show \(\displaystyle r_k(N)\le C_kN\exp\bigl(-c_k(\log N)^{\varepsilon_k}\bigr)\) with \(C_k,c_k,\varepsilon_k\gt 0\), where \(r_k(N)\) is the largest size of a subset of \(\{1,\ldots,N\}\) with no nonconstant k-term arithmetic progression.

We prove that there are absolute constants c > 0 and K₀ such that \(W_r(k)\gt k^{ck\lfloor\log_2 r\rfloor}\) for every \(k\ge K_0\) and r ≥ 2. Consequently \(W_r(k)^{1/k}\to\infty\) for each fixed r ≥ 2, giving a quantitative positive resolution of Erdős's superexponential-growth question, including the two-color case.

We disprove Sidorenko's conjecture with a bipartite graph on 35 vertices and 66 edges: its homomorphism density in some finite simple graph is smaller than the conjectured lower bound. The same connected graph also disproves the forcing conjecture: at one fixed density, asymptotically matching the edge and pattern densities does not imply quasirandomness.

For every sufficiently large prime q, we construct a finite intersecting \((q+1)\)-partite \((q+1)\)-uniform hypergraph with covering number \(q+1\) and exactly \(q+1\) nonisolated vertices in each part. This disproves Ryser's covering conjecture, even for intersecting hypergraphs with equally sized parts.

For every sufficiently large prime \(s\equiv2\pmod3\) and every sufficiently large odd integer n, with the threshold depending on s, we construct an intersecting \((s^n+1)\)-partite \((s^n+1)\)-uniform hypergraph with covering number \(s^n+1\). This disproves Ryser's covering conjecture in its intersecting case.

We prove Hindman's finite sums and products conjecture: for every finite coloring of the positive integers and every positive integer k, there is a k-element set whose nonempty subset sums and nonempty subset products all have the same color.

We prove the Harary–Hill conjecture: for every positive integer n, the ordinary crossing number of the complete graph K_n is \(\displaystyle \frac14\left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor.\)

We prove the Zarankiewicz crossing-number conjecture, resolving Turán's brickyard problem. For all positive integers m, n, the ordinary crossing number of the complete bipartite graph \(K_{m,n}\) is \(\displaystyle \left\lfloor\frac m2\right\rfloor \left\lfloor\frac{m-1}{2}\right\rfloor \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor.\)

For every fixed integer d ≥ 3, we prove that every set of n ≥ 2 distinct points in ℝ^d determines at least \(c_d n^{2/d}\) distinct distances, where \(c_d\gt 0\) depends only on d. This resolves the higher-dimensional Erdős distinct-distances conjecture positively.

We prove the weak pinned Erdős distinct-distance conjecture. For every fixed ε > 0, all but \(o(n)\) points of any n-point planar set determine at least \(n^{1-\varepsilon}\) distinct nonzero distances.

We prove a power saving for the planar unit-distance problem: for some absolute \(\beta\lt 4/3\), every set of n points in the Euclidean plane determines \(O(n^\beta)\) unordered pairs at unit distance.

We prove that an isomorphism of Bruhat intervals in arbitrary Coxeter systems preserves their equal-parameter Kazhdan–Lusztig polynomials. This resolves the full combinatorial invariance conjecture positively.

We prove that the chromatic quasisymmetric function of every natural unit interval graph is elementary-positive over \(\mathbb N[q]\). This resolves the elementary-positivity part of the Shareshian–Wachs conjecture.

We determine the sharp logarithmic exponent of the off-diagonal Ramsey number \(r(5,t)\): \(\displaystyle r(5,t)=\frac{t^4}{(\log t)^{3+o(1)}} \qquad (t\longrightarrow\infty).\)

For every fixed integer s ≥ 6, we determine the sharp logarithmic exponent of the off-diagonal Ramsey number: \(\displaystyle r(s,t)=\frac{t^{s-1}}{(\log t)^{s-2+o(1)}} \qquad (t\longrightarrow\infty).\)

We prove that the two-color Ramsey number of the n-dimensional binary cube is at most \(C2^n\), where C is an absolute constant. This resolves positively the hypercube Ramsey conjecture of Burr and Erdős.

We classify finite Euclidean Ramsey configurations by a necessary and sufficient tensor condition over their coordinate fields. The Ramsey property here concerns monochromatic congruent copies at the original scale under arbitrary finite colorings. The criterion shows that every nonempty subtransitive set and every nonempty set of at most five points on a circle is Ramsey. In particular, some Ramsey cyclic quadrilaterals are not subtransitive, disproving the necessity direction of the Leader–Russell–Walters conjectured characterization.

We prove that every nonempty finite oriented graph has a vertex with at least as many vertices at directed distance two as at directed distance one. This resolves Seymour's second neighborhood conjecture positively.

We prove that every finite loopless k-edge-connected multigraph on at least two vertices, with k ≥ 1, has a spanning tree meeting each cut in at most \(C/k\) times the size of the cut, where C is a universal constant. This resolves the strong thin tree conjecture.

We give a deterministic polynomial-time construction of strong thin trees. Given a finite k-edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a \(C/k\) fraction of its edges, for a universal constant C. The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.

We prove the graph-decomposition conjecture of Ascoli, He, Park, and Talagrand. Every graph admits a partition into a universally bounded number of fixed edge pieces, each having ordinary containment threshold at most a universal constant times the original graph's integral expectation threshold. The partition is chosen before sampling the random host, and the separate embeddings of the pieces need not agree on shared vertices.

We prove Talagrand's discrete-convexity conjecture. There is a universal integer k such that, whenever an arbitrary family has Bernoulli product measure at least \(1-1/k\), the sets not contained in a union of k members admit a cover of total cost at most 1/2 at the same density.

We prove Talagrand's conjecture that integral and fractional expectation thresholds are within a universal constant factor, with the same covering budget.

We prove the second Kahn–Kalai conjecture. For every finite simple graph H with h ≥ 1 edges and at most n vertices, the threshold for \(G(n,p)\) to contain an ordinary copy of H is at most \(C p_{\mathrm E}(n,H)(1+\log_2 h)\), where C is universal. Here \(p_{\mathrm E}(n,H)\) is the least density at which every subgraph of H has expected copy count at least one half.

For every integer d ≥ 3, we construct arbitrarily large finite d-dimensional simplicial complexes with uniformly bounded vertex degrees and uniform 𝔽₂ coboundary expansion in every degree below d. Together with the known graph and two-dimensional cases, this establishes the existence of bounded-degree 𝔽₂ coboundary expanders in every positive dimension.

For every fixed integer d ≥ 3, we give a deterministic algorithm that constructs a simple nonbipartite d-regular Ramanujan graph on every sufficiently large even number n of vertices. It outputs the full adjacency list in polynomially many bit operations, with an exponent that may depend on d. Every nonconstant adjacency eigenvalue lies strictly between \(-2\sqrt{d-1}\) and \(2\sqrt{d-1}\).

We prove the circulant Hadamard conjecture: a real circulant Hadamard matrix has order 1 or 4. As a consequence, Barker sequences of length greater than one exist exactly at lengths 2, 3, 4, 5, 7, 11, 13, proving the Barker-sequence conjecture.

We prove Barnette's conjecture: every finite simple cubic bipartite planar 3-vertex-connected graph has a Hamiltonian cycle.

We prove that every finite simple undirected graph on n vertices has an edge partition into at most \(Cn\) simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle decomposition conjecture positively.

An integer polynomial is intersective if it has a root modulo every positive integer. For each degree k ≥ 2, we prove that there is an exponent \(c_k\gt 0\) such that every set \(A\subseteq\{1,\ldots,N\}\) whose differences avoid all nonzero values \(h(1),h(2),\ldots\), where h is an intersective polynomial of degree k with positive leading coefficient, satisfies \(|A|=O_h(N^{1-c_k})\). The implied constant may depend on h, but the power-saving exponent depends only on its degree.

Let h be a fixed integer polynomial of degree at least two with positive leading coefficient, having a unit root modulo every positive integer. We prove that any set \(A\subseteq\{1,\ldots,N\}\) whose differences avoid all nonzero values \(h(p)\) at primes satisfies \(|A|\le C_hN^{1-c_h}\), where \(c_h\gt 0\) and \(C_h\ge1\) depend only on h. Thus the local unit-root condition gives a fixed power saving even when polynomial arguments are restricted to primes. The proof uses the companion zero-free half-plane theorem for Dirichlet L-functions to obtain the required prime-distribution estimates.

We prove that there are absolute constants c > 0 and C < ∞ such that every set \(A\subseteq\{1,\ldots,N\}\) with no nonzero square difference satisfies \(|A|\le C N^{1-c}\). This answers the fixed-power question posed by Green and Sawhney.

There are absolute constants ε > 0 and C such that every sufficiently large even n-point set in the plane with no three collinear has at most \(Cn^{4/3-\varepsilon}\) unordered halving pairs. This gives a power saving over the classical \(O(n^{4/3})\) bound for planar halving lines. The proof is nonquantitative and does not supply explicit constants.

For every fixed integer r ≥ 4, we prove that every K_r-free graph of sufficiently large maximum degree Δ has correspondence chromatic number \(O_r(\Delta/\log\Delta)\). This resolves the Alon–Krivelevich–Sudakov coloring conjecture in the stronger correspondence-coloring form. The same bound, with a constant depending on F, holds when any fixed graph F is excluded as an ordinary subgraph. Ordinary and list coloring satisfy the same bounds.

For every fixed integer r ≥ 4, every K_r-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least \(c_r n\log d/d\), where \(c_r\gt 0\) depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.

We construct in ZFC two self-dual partitional matroids on a countably infinite common ground set that admit neither a packing/covering partition nor an intersection witness. This disproves the unrestricted infinite matroid packing/covering and intersection conjectures and answers Joó's question for two partitional matroids negatively. The examples are neither finitary nor cofinitary.

For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies \(\mathop{\mathrm{Var}}\nolimits _p(f)\le C_r I_p(f)/(\log n)^{r/(r-1)}\). The constant depends only on r, and the bound holds uniformly for all \(0\lt p\lt 1\) without a monotonicity assumption. For increasing properties, it gives the corresponding threshold-width bound with exponent \(r/(r-1)\), proving the hypergraph threshold-width conjecture of Friedgut and Kalai.

We prove the Friedgut–Kalai sharp-threshold conjecture. For every integer n ≥ 2, every nontrivial increasing family of graphs on n vertices invariant under all vertex permutations, and every \(0\lt \varepsilon\lt 1/2\), the edge probabilities at which its probability equals ε and \(1-\varepsilon\) differ by at most \(C\log(1/(2\varepsilon))/(\log n)^2\), for a universal constant C.

We prove that Maker can achieve the Snaky hexomino within 21 actual Maker moves against arbitrary legal Breaker play on the initially empty infinite square board. The same bound holds on a \(17\times17\) square; in fact, Maker can confine its claims to a fixed 251-cell board.

Starting from the complete graph on n vertices, repeatedly remove the three edges of a uniformly chosen remaining triangle. We prove that the number of edges left at termination, divided by n^3/2, converges in L² to \(1/(2\sqrt2)\). This proves the triangle case of the sharp-constant conjecture of Joos and Kühn. In particular, the same limit holds in probability and for the normalized expectation.

We prove that \(R(C_m,K_n)=(m-1)(n-1)+1\) for every pair of integers \(m\ge n\ge3\) other than \((m,n)=(3,3)\), for which \(R(C_3,K_3)=6\). This establishes the cycle–clique conjecture of Erdős, Faudree, Rousseau and Schelp. The proof combines expansion in a minimal counterexample with a large-clique lemma and an optimization of paths joining clique vertices. These arguments reduce the remaining cases to \(3{,}099\) finite parameter-pattern instances, which are excluded by two exact implementations of proved inference rules. Complete programs and deduction traces accompany the paper.

We construct a fixed \(66\times66\) binary matrix for which ordered matrix removal has no polynomial bound. This disproves the polynomial ordered binary matrix-removal conjecture. Ordered copies preserve the separate row and column orders and match both zeros and ones; removal permits changing entries in either direction.

There are absolute constants \(\eta,c_1\gt 0\) such that, for every sufficiently large integer n, one can choose n points in the unit square so that every triangle they determine has area at least \(c_1n^{-2+\eta}\). Thus the almost n⁻² upper-bound formulation of Heilbronn's triangle problem is false. The exponent η is fixed but extremely small.

We disprove the Gopalan–Servedio square-root conjecture, even up to an arbitrary constant factor. For every real C > 0, there is a nonconstant Boolean function \(f:\{-1,1\}^n\to\{-1,1\}\) on a finite sign cube such that \(\displaystyle \sum_{i=1}^n \widehat f(\{i\})\gt C\sqrt{\deg(f)}.\) Here \(\widehat f(\{i\})\) is the linear Fourier coefficient associated with the ith input, and \(\deg(f)\) is the degree of the real multilinear polynomial representing f.