On the weighted hard-core model and Rado's covering problem for congruent Euclidean balls
2026-08-10 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a problem about collections of same-sized balls (round shapes) in space and how big a non-overlapping subset of these balls can be in comparison to the whole group. The classical known result said you can always find a disjoint subcollection with volume at least 3^(-d) times the total volume, where d is the dimension. The authors improve this by giving a better bound that nearly doubles this fraction, and for very high dimensions, they show an even stronger improvement that grows roughly with d times 3^(-d). This means their results allow finding larger disjoint subsets than previously guaranteed, especially in higher dimensions.
Euclidean unit ballVitali covering lemmacongruent Euclidean ballspairwise disjoint subcollectioncombinatorial argumentgeometric estimatehigh dimensional geometryhard-core modelvolume ratio
Authors
Chengfei Xie, Gennian Ge
Abstract
Let $B^d$ denote the Euclidean unit ball in $\mathbb{R}^d$ and $f(B^d)$ denote the largest constant $c$ such that every finite collection of congruent Euclidean balls contains a pairwise disjoint subcollection whose total volume is at least $c$ times the volume of the union of the original collection. The classical Vitali covering lemma gives $f(B^d)\geq3^{-d}$. In this paper, we establish two improvements. First, by a purely combinatorial argument, we prove that $$ f(B^d)\geq \frac{2}{3^d + 2^d} $$ for every integer $d \geq1$. This improves the Vitali bound by a factor tending to $2$ as d tends to infinity. Second, using a weighted hard-core model together with a weighted geometric estimate for intersections of Euclidean balls, we show that, for all sufficiently large $d$, $$ f(B^d)\geq \left( \log\frac{3}{1+\sqrt3} -O\left(\frac{\log d}{d}\right) \right)d\,3^{-d}. $$ Thus, the classical lower bound is improved by a factor of order $d$.