Combinatorics
-
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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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…
-
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 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…
-
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 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 -2\sqrt{d-1} and…
-
0 votes 0 replies 0 views
Paper The circulant Hadamard and Barker-sequence conjectures
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…
-
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 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 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…
37 posts