The root lattice $A_n$, equipped with its graph distance (equivalently, one half of the ambient $\ell_1$ metric), is isometric to $\mathbb{Z}^n$ with the asymmetric Manhattan metric. We study two extremal problems in this space -- the isodiametric problem, i.e., determining the maximum anticode cardinality, and the (non)existence of linear diameter-perfect codes, i.e., lattice tilings by optimal anticodes -- and solve them in dimension $3$. We show that, for every integer $D\ge 0$, the largest cardinality of a diameter-$D$ subset of $A_3$ is $\binom{D+3}{3}+(D+1)\lfloor D^2/4\rfloor$, and this value is attained by the balanced difference of two discrete simplices. We then prove an integrality-refined simplex-packing obstruction: a sublattice of $\mathbb{Z}^n$ of asymmetric Manhattan distance greater than $D$ induces a lattice packing by $(D+1)\Delta_n$ in $\mathbb{R}^n$. Combining this observation with the exact lattice-packing density of the tetrahedron yields a complete classification in dimension $3$: lattice diameter-perfect codes in $A_3$ exist precisely for $D=1$ and $D=2$. We also give the equivalent statement for perfect $B_h$ sets of cardinality four. Finally, we formulate a conjecture regarding optimal anticodes in arbitrary dimension, and restate it as an intersection problem for uniform multisets.
Let $g_n$ be the largest number of Euclidean balls of diameter $1$ which may be needed to cover a set of diameter $1$ in $\mathbb{R}^n$. We study this problem for finite sets invariant under all coordinate permutations. We prove that the exponential growth rate in this symmetric problem can be characterized exactly as a finite-alphabet squared-error rate-distortion supremum $\alpha_0$. Specialized to the two-point case, i.e., for subsets of Boolean cubes, this gives the explicit lower bound \[g_n\ge (1.160235457\ldots-o(1))^n,\] improving the previous best bound $(2/\sqrt3-o(1))^n$. Using Fix's Gaussian characterization of the rate-distortion problem, we give a numerical three-point construction with exponent base greater than $1.160497831$. Finally, we show that $\alpha_0$ is not attained by any finitely supported distribution.
Andrii Arman, A. Bondarenko, A. Prymak et al.· 0 citations
We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tilde\Omega(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.
For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche--Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.
We prove a nine-distance theorem for Kronecker sequences on flat three-tori. That is, we show that among the first $N$ orbit points, at most nine distinct positive nearest-neighbour distances occur. This proves the conjecture of Haynes and Marklof. An example of Dettmann shows that nine is optimal. More generally, we prove that on a flat $d$-dimensional torus the number of such distances is at most $2^d+1$. The main tool is a new growth theorem for the denominators $q_1<q_2<\cdots$ of best simultaneous approximations in a $d$-dimensional inner-product space, which is of independent interest. We prove that, whenever $q_{n+2^d}$ is defined, either $q_{n+2^d}\ge2q_{n+1}$, or the indices $1,\ldots,2^d$ can be partitioned into disjoint pairs $\{j,k\}$, $j<k$, such that $q_{n+k}=q_n+q_{n+j}$. In particular, $$ q_{n+2^d}\ge \min\{2q_{n+1},q_n+q_{n+2^{d-1}}\}\ge q_n+q_{n+1}. $$
We study $b_d(n)$, the minimum number of points needed to meet the relative interior of every $(d-1)$-simplex spanned by an $n$-point set in general position in $\mathbb{R}^d$. In the plane, this is the parameter from the Blocking Conjecture. We improve the best known general planar lower bound to $ b_2(n)\ge \frac{41}{13}n-O\left(\frac{n}{\log n}\right)$. For $n$ points on the moment curve in even dimension $2r$, we prove that at least $\frac{1}{r!}n^r\log n-O_r(n^r)$ points are needed to pierce the relative interior of all its codimension-one simplices, which exceeds the number of codimension-one faces in a triangulation by a $\log n$ factor. For equally spaced points on the moment curve in odd dimensions, we construct an optimal blocking set whose size equals the maximum number of codimension-one faces in a triangulation.
For a graph $H$ with $3\mid e(H)$, the zero-sum Ramsey number $R(H,\Z_3)$ is the least integer $N$ such that every labeling of the edges of $K_N$ by elements of $\Z_3$ contains a copy of $H$ whose edge labels sum to zero. We determine the last previously unresolved infinite family in the complete-graph case modulo $3$. More precisely, we prove that \(R(K_n,\Z_3)=n+3\) for every $n\ge 10$ satisfying $n\equiv 1\pmod 3$. Consequently, for $k\ge 1$, \(R(K_{9k+7},\Z_3)=9k+10\), resolving a problem of Caro and Mifsud.
Cheng Chi, Jia-Lin He, Fuhong Ma· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
