Combinatorics
-
0 votes 0 replies 0 views
Paper 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…
-
0 votes 0 replies 0 views
Paper Power savings for intersective polynomial differences and prime arguments
For every fixed intersective integer polynomial h of degree k ≥ 2 with positive leading coefficient, proves that a subset of \{1,\ldots,N\} avoiding nonzero values h(1),h(2),\ldots as differences has size…
-
0 votes 0 replies 0 views
Paper 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 0\lt \varepsilon\lt 1/2, every nontrivial increasing relabeling-invariant property crosses from…
-
0 votes 0 replies 1 views
Paper 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 OF(\Delta/\log\Delta) colors when their maximum degree Δ is sufficiently large. Also…
-
0 votes 0 replies 0 views
Paper Counterexamples to Ryser’s covering conjecture
Disproves Ryser's covering conjecture by constructing intersecting (q+1)-partite, (q+1)-uniform hypergraphs with covering number q+1, rather than the predicted bound q, for every sufficiently large prime q.…
-
0 votes 0 replies 0 views
Paper Boolean functions violate the square-root degree bound by arbitrary factors
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 $`\sumi\widehat f(\{i\})\gt…
-
0 votes 0 replies 0 views
Paper Cycle–clique Ramsey numbers
Proves the Erdős–Faudree–Rousseau–Schelp conjecture: R(Cm,Kn)=(m-1)(n-1)+1 for every m\ge n\ge3, except R(C3,K3)=6. This is the exact threshold forcing a red m-cycle or a blue n-clique in every red–blue…
-
0 votes 0 replies 0 views
Paper 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 n^{3/2}/(2\sqrt2), with mean-square convergence after normalization…
-
0 votes 0 replies 0 views
Paper Polynomial removal fails for ordered binary matrices
Disproves polynomial ordered binary matrix removal with one fixed 66\times66 zero–one pattern. Matrices can require many binary-entry changes to become pattern-free while their copy density is smaller than every…
-
0 votes 0 replies 0 views
Paper A power improvement in the Heilbronn triangle lower bound
For every sufficiently large n, constructs n points in the unit square such that every triangle has area at least n^{-2+c} for one absolute c > 0. This disproves the conjectured almost-n−2 upper bound in…
-
0 votes 0 replies 0 views
Paper Power savings for planar halving lines and k-sets
Improves the planar halving-line bound to O(n^{4/3-\varepsilon}) 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-\varepsilon0})…
-
0 votes 0 replies 0 views
Paper Snaky in 21 Maker moves
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…
-
0 votes 0 replies 0 views
Paper Counterexamples to infinite matroid intersection and packing/covering
Disproves the unrestricted infinite matroid intersection and packing/covering conjectures in ZFC, using two self-dual partitional matroids on a countably infinite ground set. The same examples answer Joó’s…
-
0 votes 0 replies 0 views
Paper 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…
-
0 votes 0 replies 0 views
Paper 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…
-
0 votes 0 replies 0 views
Paper Sharp logarithmic exponents for off-diagonal Ramsey numbers
For every fixed integer s ≥ 5, proves r(s,t)=t^{s-1}/(\log t)^{s-2+o(1)} as t\to\infty, determining the logarithmic exponent and matching the classical upper bound at that scale. Here r(s,t) is the least…
-
0 votes 0 replies 0 views
Paper 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 G(n,p) is at most C p{\mathrm E}(n,H)(1+\log2 h), with universal C.…
-
0 votes 0 replies 0 views
Paper 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 \mathbb N[q]. The…
-
0 votes 0 replies 0 views
Paper 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 Cn simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai…
-
0 votes 0 replies 0 views
Paper Combinatorial invariance of Kazhdan–Lusztig polynomials
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…
-
0 votes 0 replies 0 views
Paper Superexponential van der Waerden numbers
Resolves Erdős's superexponential-growth question for van der Waerden numbers. If Wr(k) is the least interval length forcing a monochromatic k-term progression in every r-coloring, then $`Wr(k)\gt k^{ck\lfloor\log2…
-
0 votes 0 replies 0 views
Paper A counterexample to periodic tiling in dimension three
Constructs a finite translational tile in ℤ3 that tiles space but admits no fully periodic tiling, disproving the periodic tiling conjecture in the smallest possible lattice dimension. Its unit-cube thickening gives the…
-
0 votes 0 replies 0 views
Paper 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 \chif(G)\gt h(G), where h(G) is the largest clique-minor order.…
-
0 votes 0 replies 0 views
Paper Hindman’s finite sums and products conjecture
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…
-
0 votes 0 replies 0 views
Paper The hypercube Ramsey conjecture
Resolves the Burr–Erdős hypercube Ramsey conjecture: the two-color Ramsey number of the n-dimensional cube is \Theta(2^n). Thus every red-blue coloring of a complete graph on a universal constant times the cube's…
-
0 votes 0 replies 0 views
Paper 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…
-
0 votes 0 replies 0 views
Paper Deterministic construction of strong thin spanning trees
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…
-
0 votes 0 replies 0 views
Paper Borsuk's conjecture fails in dimension nine
Constructs a compact subset of ℝ9 that cannot be covered by ten sets of strictly smaller diameter, disproving Borsuk's covering assertion already in dimension nine. The example consists of rank-one orthogonal projectors…
-
0 votes 0 replies 0 views
Paper 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…
-
0 votes 0 replies 0 views
Paper Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi bounds
Proves Erdős's conjecture that every set of positive integers with divergent reciprocal sum contains arithmetic progressions of every finite length. Quantitatively, for each fixed k ≥ 3, every subset of…
37 posts