Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved bounds for Hadwigers covering problem via thin-shell estimates
310
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A central problem in discrete geometry, known as Hadwigers covering problem, asks what the smallest natural number $Nleft(nright)$ is such that every convex body in ${mathbb R}^{n}$ can be covered by a union of the interiors of at most $Nleft(nright)$ of its translates. Despite continuous efforts, the best general upper bound known for this number remains as it was more than sixty years ago, of the order of ${2n choose n}nln n$. In this note, we improve this bound by a sub-exponential factor. That is, we prove a bound of the order of ${2n choose n}e^{-csqrt{n}}$ for some universal constant $c>0$. Our approach combines ideas from previous work by Artstein-Avidan and the second named author with tools from Asymptotic Geometric Analysis. One of the key steps is proving a new lower bound for the maximum volume of the intersection of a convex body $K$ with a translate of $-K$; in fact, we get the same lower bound for the volume of the intersection of $K$ and $-K$ when they both have barycenter at the origin. To do so, we make use of measure concentration, and in particular of thin-shell estimates for isotropic log-concave measures. Using the same ideas, we establish an exponentially better bound for $Nleft(nright)$ when restricting our attention to convex bodies that are $psi_{2}$. By a slightly different approach, an exponential improvement is established also for classes of convex bodies with positive modulus of convexity.
rate research
Read More
In the Metric Capacitated Covering (MCC) problem, given a set of balls $mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of the points in $P$ to the balls in $mathcal{B}$ such that each point is assigned to a ball that contains it and each ball is assigned with at most $U$ points. MCC achieves an $O(log |P|)$-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(log |P|)$ even with $beta < 3$ factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an $O(1)$-approximation for the problem with $6.47$ factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound $3$ and the upper bound $6.47$. In this current work, we show that it is possible to obtain an $O(1)$-approximation with only $4.24$ factor expansion of the balls. We also show a similar upper bound of $5$ for a more generalized version of MCC for which the best previously known bound was $9$.
Hadwiger conjectured in 1943 that for every integer $t ge 1$, every graph with no $K_t$ minor is $(t-1)$-colorable. Kostochka, and independently Thomason, proved every graph with no $K_t$ minor is $O(t(log t)^{1/2})$-colorable. Recently, Postle improved it to $O(t (log log t)^6)$-colorable. In this paper, we show that every graph with no $K_t$ minor is $O(t (log log t)^{5})$-colorable.
We present an alternative approach to some results of Koldobsky on measures of sections of symmetric convex bodies, which allows us to extend them to the not necessarily symmetric setting. We prove that if $K$ is a convex body in ${mathbb R}^n$ with $0in {rm int}(K)$ and if $mu $ is a measure on ${mathbb R}^n$ with a locally integrable non-negative density $g$ on ${mathbb R}^n$, then begin{equation*}mu (K)leq left (csqrt{n-k}right )^kmax_{Fin G_{n,n-k}}mu (Kcap F)cdot |K|^{frac{k}{n}}end{equation*} for every $1leq kleq n-1$. Also, if $mu $ is even and log-concave, and if $K$ is a symmetric convex body in ${mathbb R}^n$ and $D$ is a compact subset of ${mathbb R}^n$ such that $mu (Kcap F)leq mu (Dcap F)$ for all $Fin G_{n,n-k}$, then begin{equation*}mu (K)leq left (ckL_{n-k}right )^{k}mu (D),end{equation*} where $L_s$ is the maximal isotropic constant of a convex body in ${mathbb R}^s$. Our method employs a generalized Blaschke-Petkantschin formula and estimates for the dual affine quermassintegrals.
In this paper, we study the asymptotic thin-shell width concentration for random vectors uniformly distributed in Orlicz balls. We provide both asymptotic upper and lower bounds on the probability of such a random vector $X_n$ being in a thin shell of radius $sqrt{n}$ times the asymptotic value of $n^{-1/2}left(mathbb Eleft[| X_n|_2^2right]right)^{1/2}$ (as $ntoinfty$), showing that in certain ranges our estimates are optimal. In particular, our estimates significantly improve upon the currently best known general Lee-Vempala bound when the deviation parameter $t=t_n$ goes down to zero as the dimension $n$ of the ambient space increases. We shall also determine in this work the precise asymptotic value of the isotropic constant for Orlicz balls. Our approach is based on moderate deviation principles and a connection between the uniform distribution on Orlicz balls and Gibbs measures at certain critical inverse temperatures with potentials given by Orlicz functions, an idea recently presented by Kabluchko and Prochno in [The maximum entropy principle and volumetric properties of Orlicz balls, J. Math. Anal. Appl. {bf 495}(1) 2021, 1--19].
For fixed functions $G,H:[0,infty)to[0,infty)$, consider the rotationally invariant probability density on $mathbb{R}^n$ of the form [ mu^n(ds) = frac{1}{Z_n} G(|s|_2), e^{ - n H( |s|_2)} ds. ] We show that when $n$ is large, the Euclidean norm $|Y^n|_2$ of a random vector $Y^n$ distributed according to $mu^n$ satisfies a Gaussian thin-shell property: the distribution of $|Y^n|_2$ concentrates around a certain value $s_0$, and the fluctuations of $|Y^n|_2$ are approximately Gaussian with the order $1/sqrt{n}$. We apply this thin shell property to the study of rotationally invariant random simplices, simplices whose vertices consist of the origin as well as independent random vectors $Y_1^n,ldots,Y_p^n$ distributed according to $mu^n$. We show that the logarithmic volume of the resulting simplex exhibits highly Gaussian behavior, providing a generalizing and unifying setting for the objects considered in Grote-Kabluchko-Thale [Limit theorems for random simplices in high dimensions, ALEA, Lat. Am. J. Probab. Math. Stat. 16, 141--177 (2019)]. Finally, by relating the volumes of random simplices to random determinants, we show that if $A^n$ is an $n times n$ random matrix whose entries are independent standard Gaussian random variables, then there are explicit constants $c_0,c_1in(0,infty)$ and an absolute constant $Cin(0,infty)$ such that [sup_{ s in mathbb{R}} left| mathbb{P} left[ frac{ log mathrm{det}(A^n) - log(n-1)! - c_0 }{ sqrt{ frac{1}{2} log n + c_1 }} < s right] - int_{-infty}^s frac{e^{ - u^2/2} du}{ sqrt{ 2 pi }} right| < frac{C}{log^{3/2}n}, ] sharpening the $1/log^{1/3 + o(1)}n$ bound in Nguyen and Vu [Random matrices: Law of the determinant, Ann. Probab. 42 (1) (2014), 146--167].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
