The classical Hadwiger-Nelson problem asks for the chromatic number of the unit distance graph of the Euclidean plane. Over the years, this problem has been considered for a variety of other normed spaces, with higher-dimensional Euclidean space $\mathbb{R}^d$ being perhaps the most natural and well-studied. Alon, Buci\'c, and Sauermann proved that, for a typical norm on $\mathbb{R}^d$, the chromatic number of the unit distance graph is at most $2^d$. We improve this exponential bound to a linear one by showing that the chromatic number of a typical norm on $\mathbb{R}^d$ is at most $2d$ and that this is tight. This shows a stark difference in the behavior compared to the Euclidean case, where there is an exponential lower bound. One of the key ingredients is a certain high-dimensional, matrix generalization of the Lonely runner conjecture, which also allows us to completely settle the so-called view-obstruction conjecture of Schoenberg from 1978 and a more recent covering-radius conjecture of Henze and Malikiosis.
We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^\omega)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $\omega$ is the exponent of matrix multi...
Let $R_\infty(n)$ be the maximal Banach--Mazur distance from an $n$-dimensional real normed space to $\ell_\infty^n$. We prove that $R_\infty(n)\ge cn^{2/3}(\log(2n))^{-10}$. Together with the upper bound of Friedland, Naor, and Youssef, this gives $R_\infty(n) = n^{2/3+o(1)}$. The examples are polars of symmetric Gaus...
We study the complexity of two fundamental problems attached to p-adic lattices: computing an N-orthogonal basis, and deciding whether a given basis is N-orthogonal. When the norm is supplied through an explicit diagonal representation, both problems are polynomial. However, in the black-box model, where the ultrametri...
Pierre Fromonot, Mercedes Haiech, Tristan Vaccon· 0 citations
We present an exposition of an argument, discovered by GPT-6 Pro, that gives an optimal bound for the polynomial Littlewood-Offord problem. Namely, let $F$ be a degree-$d$ multilinear polynomial that contains $r$ degree-$d$ monomials involving disjoint sets of variables. Then, for i.i.d. Rademacher random variables $\x...
Let $B^d$ denote the $d$-dimensional Euclidean ball of unit radius. What is the largest constant $f(B^d) \in [0,1]$ with the property that every finite collection $\mathcal{C}$ of unit balls in $\mathbb{R}^d$ admits a disjoint sub-collection $\mathcal{S}$ occupying at least a fraction $f(B^d)$ of the volume of $\mathca...
In this work we study the maximal ratio $I$ between the white noise integrated over a set and the perimeter of the set, which can be seen as a random isoperimetric problem, and appears in the random-field Ising model (Ding-Wirth) and min-max optimal matching (Leighton-Shor). In the planar case considered here, such a r...
Xiao-Peng Cheng, Felix Otto, Matteo Palmieri· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
