Sets of unit vectors with small subset sums
HTML articles powered by AMS MathViewer
- by Konrad J. Swanepoel PDF
- Trans. Amer. Math. Soc. 368 (2016), 7153-7188 Request permission
Abstract:
We say that a family $\{\mathbfit {x}_i \,\vert \, i\in [m]\}$ of vectors in a Banach space $X$ satisfies the $k$-collapsing condition if $\|\sum _{i\in I}\mathbfit {x}_i\|\leq 1$ for all $k$-element subsets $I\subseteq \{1,2,\dots ,m\}$. Let $\overline {\mathcal {C}}(k,d)$ denote the maximum cardinality of a $k$-collapsing family of unit vectors in a $d$-dimensional Banach space, where the maximum is taken over all spaces of dimension $d$. Similarly, let $\overline {\mathcal {CB}}(k,d)$ denote the maximum cardinality if we require in addition that $\sum _{i=1}^m\mathbfit {x}_i=\mathbfit {o}$. The case $k=2$ was considered by FĂŒredi, Lagarias and Morgan (1991). These conditions originate in a theorem of Lawlor and Morgan (1994) on geometric shortest networks in smooth finite-dimensional Banach spaces. We show that $\overline {\mathcal {CB}}(k,d)=\max \{k+1,2d\}$ for all $k,d\geq 2$. The behaviour of $\overline {\mathcal {C}}(k,d)$ is not as simple, and we derive various upper and lower bounds for various ranges of $k$ and $d$. These include the exact values $\overline {\mathcal {C}}(k,d)=\max \{k+1,2d\}$ in certain cases.
We use a variety of tools from graph theory, convexity and linear algebra in the proofs: in particular the HajnalâSzemerĂ©di Theorem, the BrunnâMinkowski inequality, and lower bounds for the rank of a perturbation of the identity matrix.
References
- Noga Alon, Problems and results in extremal combinatorics. I, Discrete Math. 273 (2003), no. 1-3, 31â53. EuroCombâ01 (Barcelona). MR 2025940, DOI 10.1016/S0012-365X(03)00227-9
- Noga Alon, Perturbed identity matrices have high rank: proof and applications, Combin. Probab. Comput. 18 (2009), no. 1-2, 3â15. MR 2497372, DOI 10.1017/S0963548307008917
- Noga Alon, Toshiya Itoh, and Tatsuya Nagatani, On $(\epsilon ,k)$-min-wise independent permutations, Random Structures Algorithms 31 (2007), no. 3, 384â389. MR 2352287, DOI 10.1002/rsa.20184
- N. Alon and P. PudlĂĄk, Equilateral sets in $l^n_p$, Geom. Funct. Anal. 13 (2003), no. 3, 467â482. MR 1995795, DOI 10.1007/s00039-003-0418-7
- Keith Ball, An elementary introduction to modern convex geometry, Flavors of geometry, Math. Sci. Res. Inst. Publ., vol. 31, Cambridge Univ. Press, Cambridge, 1997, pp. 1â58. MR 1491097, DOI 10.2977/prims/1195164788
- Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff, Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes [extended abstract], STOCâ11âProceedings of the 43rd ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 519â528. MR 2932002, DOI 10.1145/1993636.1993705
- E. J. Cockayne, On the Steiner problem, Canad. Math. Bull. 10 (1967), 431â450. MR 215750, DOI 10.4153/CMB-1967-041-8
- Bruno Codenotti, Pavel PudlĂĄk, and Giovanni Resta, Some structural properties of low-rank matrices related to computational complexity, Theoret. Comput. Sci. 235 (2000), no. 1, 89â107. Selected papers in honor of Manuel Blum (Hong Kong, 1998). MR 1765967, DOI 10.1016/S0304-3975(99)00185-1
- Jean-Pierre Deschaseaux, Une caractĂ©risation de certains espaces vectoriels normĂ©s de dimension finie par leur constante de Macphail, C. R. Acad. Sci. Paris SĂ©r. A-B 276 (1973), A1349âA1351 (French). MR 318841
- Ronald A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007), no. 4-6, 918â925. MR 2371999, DOI 10.1016/j.jco.2007.04.002
- P. ErdĆs, Problem 9, in: Theory of Graphs and Its Applications (M. Fiedler, ed.), Proceedings of the Symposium held in Smolenice in June 1963, Publishing House of the Czechoslovak Academy of Sciences, Prague, 1964, p. 159.
- C. Franchetti and G. F. Votruba, Perimeter, Macphail number and projection constant in Minkowski planes, Boll. Un. Mat. Ital. B (5) 13 (1976), no. 2, 560â573 (English, with Italian summary). MR 0470850
- Z. FĂŒredi, J. C. Lagarias, and F. Morgan, Singularities of minimal surfaces and networks and related extremal problems in Minkowski space, Discrete and computational geometry (New Brunswick, NJ, 1989/1990) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991, pp. 95â109. MR 1143291, DOI 10.1090/dimacs/006/06
- Mohammad Ghomi, Optimal smoothing for convex polytopes, Bull. London Math. Soc. 36 (2004), no. 4, 483â492. MR 2069010, DOI 10.1112/S0024609303003059
- S. GoĆÄ b, Some metric problems in the geometry of Minkowski (Polish. French summary), Prace Akademii GĂłrniczej w Krakowie 6 (1932), 1â79.
- A. Hajnal and E. SzemerĂ©di, Proof of a conjecture of P. ErdĆs, Combinatorial theory and its applications, II (Proc. Colloq., BalatonfĂŒred, 1969) North-Holland, Amsterdam, 1970, pp. 601â623. MR 0297607
- Fritz John, Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, N. Y., 1948, pp. 187â204. MR 0030135
- B. S. KaĆĄin, The diameters of octahedra, Uspehi Mat. Nauk 30 (1975), no. 4(184), 251â252 (Russian). MR 0397375
- G. O. H. Katona, Inequalities for the distribution of the length of a sum of random vectors, Teor. Verojatnost. i Primenen. 22 (1977), no. 3, 466â481 (Russian, with English summary). MR 0455067
- G. O. H. Katona, Sums of vectors and TurĂĄnâs problem for $3$-graphs, European J. Combin. 2 (1981), no. 2, 145â154. MR 622080, DOI 10.1016/S0195-6698(81)80006-6
- G. O. H. Katona, âBestâ estimations on the distribution of the length of sums of two random vectors, Z. Wahrsch. Verw. Gebiete 60 (1982), no. 3, 411â423. MR 664426, DOI 10.1007/BF00535724
- G. O. H. Katona, Probabilistic inequalities from extremal graph results (a survey), Random graphs â83 (PoznaĆ, 1983) North-Holland Math. Stud., vol. 118, North-Holland, Amsterdam, 1985, pp. 159â170. MR 860591
- Gyula O. H. Katona, Richard Mayer, and Wojbor A. Woyczynski, Length of sums in a Minkowski space, Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, 2004, pp. 113â118. MR 2065257, DOI 10.1090/conm/342/06135
- H. A. Kierstead and A. V. Kostochka, A short proof of the Hajnal-SzemerĂ©di theorem on equitable colouring, Combin. Probab. Comput. 17 (2008), no. 2, 265â270. MR 2396352, DOI 10.1017/S0963548307008619
- Gary Lawlor and Frank Morgan, Paired calibrations applied to soap films, immiscible fluids, and surfaces or networks minimizing other norms, Pacific J. Math. 166 (1994), no. 1, 55â83. MR 1306034
- Horst Martini, Konrad J. Swanepoel, and Gunter WeiĂ, The geometry of Minkowski spacesâa survey. I, Expo. Math. 19 (2001), no. 2, 97â142. MR 1835964, DOI 10.1016/S0723-0869(01)80025-6
- Herbert Robbins, A remark on Stirlingâs formula, Amer. Math. Monthly 62 (1955), 26â29. MR 69328, DOI 10.2307/2308012
- Gideon Schechtman and Adi Shraibman, Lower bounds for local versions of dimension reductions, Discrete Comput. Geom. 41 (2009), no. 2, 273â283. MR 2471875, DOI 10.1007/s00454-008-9068-8
- A. F. Sidorenko and B. S. Stechkin, Extremal geometric constants, Mat. Zametki 29 (1981), no. 5, 691â709, 798 (Russian). MR 621295
- A. F. Sidorenko and B. S. Stechkin, A class of extremal geometric constants and their applications, Mat. Zametki 45 (1989), no. 3, 101â107, 128 (Russian). MR 1001701
- K. J. Swanepoel, Extremal problems in Minkowski space related to minimal networks, Proc. Amer. Math. Soc. 124 (1996), no. 8, 2513â2518. MR 1327047, DOI 10.1090/S0002-9939-96-03370-9
- K. J. Swanepoel, Vertex degrees of Steiner minimal trees in $l^d_p$ and other smooth Minkowski spaces, Discrete Comput. Geom. 21 (1999), no. 3, 437â447. MR 1672996, DOI 10.1007/PL00009431
- Konrad J. Swanepoel, Sets of unit vectors with small pairwise sums, Quaest. Math. 23 (2000), no. 3, 383â388. MR 1809945, DOI 10.2989/16073600009485985
- Konrad J. Swanepoel, Equilateral sets in finite-dimensional normed spaces, Seminar of Mathematical Analysis, Colecc. Abierta, vol. 71, Univ. Sevilla Secr. Publ., Seville, 2004, pp. 195â237. MR 2117069
- Konrad J. Swanepoel, The local Steiner problem in finite-dimensional normed spaces, Discrete Comput. Geom. 37 (2007), no. 3, 419â442. MR 2301527, DOI 10.1007/s00454-006-1298-z
- Konrad J. Swanepoel, Upper bounds for edge-antipodal and subequilateral polytopes, Period. Math. Hungar. 54 (2007), no. 1, 99â106. MR 2310370, DOI 10.1007/s-10998-007-1099-0
Additional Information
- Konrad J. Swanepoel
- Affiliation: Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, United Kingdom
- Email: k.swanepoel@lse.ac.uk
- Received by editor(s): February 9, 2014
- Received by editor(s) in revised form: September 10, 2014
- Published electronically: January 20, 2016
- Additional Notes: An extended version of this paper is available at arXiv:1210.0366
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 7153-7188
- MSC (2010): Primary 52A37; Secondary 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41
- DOI: https://doi.org/10.1090/tran/6601
- MathSciNet review: 3471088