Combinatorics
-
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 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 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 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 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 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 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 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 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 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 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 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 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 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 1 views
Paper Planar distinct distances and unit-distance bounds
Proves the weak pinned Erdős 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. A complementary theorem…
-
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.…
18 posts