Continuous quantitative Helly-type results

Fernandez Vidal, Tomás; Galicer, Daniel; Merzbacher, Mariano

doi:10.1090/proc/15844

Continuous quantitative Helly-type results
HTML articles powered by AMS MathViewer

by Tomás Fernandez Vidal, Daniel Galicer and Mariano Merzbacher PDF

Proc. Amer. Math. Soc. 150 (2022), 2181-2193 Request permission

Abstract:

Brazitikos’ results on quantitative Helly-type theorems (for the volume and for the diameter) rely on the work of Srivastava on sparsification of John’s decompositions. We change this tool by a stronger recent result due to Friedland and Youssef which, together with an appropriate selection in the accuracy of the approximation, allows us to obtain Helly-type versions which are sensitive to the number of convex sets involved.

References

Víctor Hugo Almendra-Hernández, Gergely Ambrus, and Matthew Kendall, Quantitative Helly-type theorems via sparse approximation, Preprint, arXiv:2108.05745, 2021.
David Alonso-Gutiérrez, On the isotropy constant of random convex sets, Proc. Amer. Math. Soc. 136 (2008), no. 9, 3293–3300. MR 2407095, DOI 10.1090/S0002-9939-08-09487-2
Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman, Asymptotic geometric analysis. Part I, Mathematical Surveys and Monographs, vol. 202, American Mathematical Society, Providence, RI, 2015. MR 3331351, DOI 10.1090/surv/202
Keith Ball, Volume ratios and a reverse isoperimetric inequality, J. London Math. Soc. (2) 44 (1991), no. 2, 351–359. MR 1136445, DOI 10.1112/jlms/s2-44.2.351
I. Bárány and Z. Füredi, Approximation of the sphere by polytopes having few vertices, Proc. Amer. Math. Soc. 102 (1988), no. 3, 651–659. MR 928998, DOI 10.1090/S0002-9939-1988-0928998-8
Imre Bárány and Gil Kalai, Helly-type problems, Bull. Amer. Math. Soc., DOI 10.1090/bull/1753.
Imre Bárány, Meir Katchalski, and János Pach, Quantitative Helly-type theorems, Proc. Amer. Math. Soc. 86 (1982), no. 1, 109–114. MR 663877, DOI 10.1090/S0002-9939-1982-0663877-X
I. Bárány, M. Katchalski, and János Pach, Helly’s theorem with volumes, Amer. Math. Monthly 91 (1984), no. 6, 362–365. MR 750523, DOI 10.2307/2322144
Alexander Barvinok, Thrifty approximations of convex bodies by polytopes, Int. Math. Res. Not. IMRN 16 (2014), 4341–4356. MR 3250035, DOI 10.1093/imrn/rnt078
Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava, Twice-Ramanujan sparsifiers, SIAM J. Comput. 41 (2012), no. 6, 1704–1721. MR 3029269, DOI 10.1137/090772873
Silouanos Brazitikos, Brascamp-Lieb inequality and quantitative versions of Helly’s theorem, Mathematika 63 (2017), no. 1, 272–291. MR 3610015, DOI 10.1112/S0025579316000255
Silouanos Brazitikos, Quantitative Helly-type theorem for the diameter of convex sets, Discrete Comput. Geom. 57 (2017), no. 2, 494–505. MR 3602863, DOI 10.1007/s00454-016-9840-0
Bernd Carl and Alain Pajor, Gel′fand numbers of operators with values in a Hilbert space, Invent. Math. 94 (1988), no. 3, 479–504. MR 969241, DOI 10.1007/BF01394273
Gábor Damásdi, Viktória Földvári, and Márton Naszódi, Colorful Helly-type theorems for the volume of intersections of convex bodies, J. Combin. Theory Ser. A 178 (2021), 105361.
Jesús A. De Loera, Reuben N. La Haye, David Rolnick, and Pablo Soberón, Quantitative combinatorial geometry for continuous parameters, Discrete Comput. Geom. 57 (2017), no. 2, 318–334. MR 3602856, DOI 10.1007/s00454-016-9857-4
Travis Dillon and Pablo Soberón, A mélange of diameter Helly-type theorems, SIAM J. Discrete Math. 35 (2021), no. 3, 1615–1627. MR 4287348, DOI 10.1137/20M1365119
Omer Friedland and Pierre Youssef, Approximating matrices and convex bodies, Int. Math. Res. Not. IMRN 8 (2019), 2519–2537. MR 3942169, DOI 10.1093/imrn/rnx206
E. D. Gluskin, Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces, Mat. Sb. (N.S.) 136(178) (1988), no. 1, 85–96 (Russian); English transl., Math. USSR-Sb. 64 (1989), no. 1, 85–96. MR 945901, DOI 10.1070/SM1989v064n01ABEH003295
Eduard Helly, Über mengen konvexer körper mit gemeinschaftlichen punkte, Jahresber. Dtsch. Math.-Ver. 32 (1923), 175–176.
Grigory Ivanov and Márton Naszódi, A quantitative Helly-type theorem: containment in a homothet, Preprint, arXiv:2103.04122, 2021.
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava, Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem, Ann. of Math. (2) 182 (2015), no. 1, 327–350. MR 3374963, DOI 10.4007/annals.2015.182.1.8
Márton Naszódi, Proof of a conjecture of Bárány, Katchalski and Pach, Discrete Comput. Geom. 55 (2016), no. 1, 243–248. MR 3439267, DOI 10.1007/s00454-015-9753-3
Sherry Sarkar, Alexander Xue, and Pablo Soberón, Quantitative combinatorial geometry for concave functions, J. Combin. Theory Ser. A 182 (2021), Paper No. 105465, 33. MR 4243367, DOI 10.1016/j.jcta.2021.105465
Nikhil Srivastava, On contact points of convex bodies, Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2050, Springer, Heidelberg, 2012, pp. 393–412. MR 2985307, DOI 10.1007/978-3-642-29849-3_{2}5