Combinatorics
-
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 Counterexamples to Sidorenko’s conjecture and the forcing conjecture
Disproves Sidorenko's conjecture with a connected bipartite pattern on 35 vertices and 66 edges that occurs less frequently than in a random graph of the same edge density. The same pattern disproves the forcing…
-
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 The higher-dimensional Erdős distinct-distances conjecture
For every fixed d ≥ 3, any n ≥ 2 distinct points in ℝd determine at least cdn^{2/d} distinct distances, with cd\gt 0 depending only on dimension. This matches the integer-grid order and resolves the…
-
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 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…
37 posts