Circulant Hadamard Conjecture, Cycle–Clique Ramsey Numbers and 7 More in Combinatorics

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. (Lean)

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 n ∈ {2,3,4,5,7,11,13}. (Lean)

Improves the planar halving-line bound to O(n^4/3-ε) for sets with no three collinear and an absolute ε > 0. More generally, an n-point set with no three collinear has O(n(k+1)^1/3-ε₀) strictly separable k-subsets for 1 ≤ k ≤ n/2, with an absolute ε₀ > 0. The constants and positive exponents are nonquantitative. (Lean)

Proves the Erdős–Faudree–Rousseau–Schelp conjecture: R(C_m,K_n)=(m-1)(n-1)+1 for every m ≥ n ≥ 3, except R(C₃,K₃)=6. This is the exact threshold forcing a red m-cycle or a blue n-clique in every red–blue coloring of a complete graph. (Lean)

Disproves the proposed square-root bound relating a Boolean function's linear Fourier coefficients to its polynomial degree. For every C > 0, there is a sign-valued Boolean function f with ∑_if̂({i}) > C√(deg(f)). Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor. (Lean)

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 C/k fraction of the edges of every cut. Such a tree can be found deterministically in polynomial time, even with binary-encoded parallel-edge multiplicities. (Lean)

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 -2√(d-1) and 2√(d-1). A deterministic algorithm outputs the full adjacency list in polynomial bit time, with exponent depending on d.

For every fixed intersective integer polynomial h of degree k ≥ 2 with positive leading coefficient, proves that a subset of {1,…,N} avoiding nonzero values h(1),h(2),… as differences has size O_h(N^1-c_k), with c_k > 0 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. (Lean)

Proves the Alon–Krivelevich–Sudakov coloring conjecture in correspondence-coloring form: graphs avoiding any fixed subgraph F need O_F(Δ/log Δ) 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 Ω_r(n log d/d). (Lean)