Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 
 

 

Sets of unit vectors with small subset sums


Author: Konrad J. Swanepoel
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
Published electronically: January 20, 2016
MathSciNet review: 3471088
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We say that a family $ \{\mathbold {x}_i \,\vert \, i\in [m]\}$ of vectors in a Banach space $ X$ satisfies the $ k$-collapsing condition if $ \Vert\sum _{i\in I}\mathbold {x}_i\Vert\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\mathbold {x}_i=\mathbold {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 [Enhancements On Off] (What's this?)

  • [1] Noga Alon, Problems and results in extremal combinatorics. I, Discrete Math. 273 (2003), no. 1-3, 31-53. EuroComb'01 (Barcelona). MR 2025940 (2005a:05208), https://doi.org/10.1016/S0012-365X(03)00227-9
  • [2] Noga Alon, Perturbed identity matrices have high rank: proof and applications, Combin. Probab. Comput. 18 (2009), no. 1-2, 3-15. MR 2497372 (2010d:15001), https://doi.org/10.1017/S0963548307008917
  • [3] 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 (2009d:68122), https://doi.org/10.1002/rsa.20184
  • [4] N. Alon and P. Pudlák, Equilateral sets in $ l^n_p$, Geom. Funct. Anal. 13 (2003), no. 3, 467-482. MR 1995795 (2004h:46011), https://doi.org/10.1007/s00039-003-0418-7
  • [5] 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 (99f:52002), https://doi.org/10.2977/prims/1195164788
  • [6] 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, https://doi.org/10.1145/1993636.1993705
  • [7] E. J. Cockayne, On the Steiner problem, Canad. Math. Bull. 10 (1967), 431-450. MR 0215750 (35 #6585)
  • [8] Bruno Codenotti, Pavel Pudlák, and Giovanni Resta, Some structural properties of low-rank matrices related to computational complexity, Selected papers in honor of Manuel Blum (Hong Kong, 1998), Theoret. Comput. Sci. 235 (2000), no. 1, 89-107. MR 1765967 (2001e:05078), https://doi.org/10.1016/S0304-3975(99)00185-1
  • [9] 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 0318841 (47 #7387)
  • [10] Ronald A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007), no. 4-6, 918-925. MR 2371999 (2008k:94014), https://doi.org/10.1016/j.jco.2007.04.002
  • [11] 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.
  • [12] 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 (57 #10594)
  • [13] 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 (93d:52009)
  • [14] Mohammad Ghomi, Optimal smoothing for convex polytopes, Bull. London Math. Soc. 36 (2004), no. 4, 483-492. MR 2069010 (2005b:52021), https://doi.org/10.1112/S0024609303003059
  • [15] S. Gołąb, Some metric problems in the geometry of Minkowski (Polish. French summary), Prace Akademii Górniczej w Krakowie 6 (1932), 1-79.
  • [16] 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 (45 #6661)
  • [17] 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 (10,719b)
  • [18] B. S. Kašin, The diameters of octahedra, Uspehi Mat. Nauk 30 (1975), no. 4(184), 251-252 (Russian). MR 0397375 (53 #1234)
  • [19] 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 (56 #13307)
  • [20] 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 (82j:05073), https://doi.org/10.1016/S0195-6698(81)80006-6
  • [21] 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 (84b:60019), https://doi.org/10.1007/BF00535724
  • [22] 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 (88b:60025)
  • [23] 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 (2005d:46017), https://doi.org/10.1090/conm/342/06135
  • [24] 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 (2009a:05071), https://doi.org/10.1017/S0963548307008619
  • [25] 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 (95i:58051)
  • [26] Horst Martini, Konrad J. Swanepoel, and Gunter Weiß, The geometry of Minkowski spaces--a survey. I, Expo. Math. 19 (2001), no. 2, 97-142; Errata, Expo. Math. 19 (2001), 364. MR 1835964 (2002h:46015a), https://doi.org/10.1016/S0723-0869(01)80025-6
  • [27] Herbert Robbins, A remark on Stirling's formula, Amer. Math. Monthly 62 (1955), 26-29. MR 0069328 (16,1020e)
  • [28] Gideon Schechtman and Adi Shraibman, Lower bounds for local versions of dimension reductions, Discrete Comput. Geom. 41 (2009), no. 2, 273-283. MR 2471875 (2010d:51037), https://doi.org/10.1007/s00454-008-9068-8
  • [29] A. F. Sidorenko and B. S. Stechkin, Extremal geometric constants, Mat. Zametki 29 (1981), no. 5, 691-709, 798 (Russian). MR 621295 (83b:52008)
  • [30] 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 (90f:26027)
  • [31] K. J. Swanepoel, Extremal problems in Minkowski space related to minimal networks, Proc. Amer. Math. Soc. 124 (1996), no. 8, 2513-2518. MR 1327047 (96j:52014), https://doi.org/10.1090/S0002-9939-96-03370-9
  • [32] 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 (2000g:05054), https://doi.org/10.1007/PL00009431
  • [33] Konrad J. Swanepoel, Sets of unit vectors with small pairwise sums, Quaest. Math. 23 (2000), no. 3, 383-388. MR 1809945 (2002a:46013), https://doi.org/10.2989/16073600009485985
  • [34] 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 (2005j:46009)
  • [35] Konrad J. Swanepoel, The local Steiner problem in finite-dimensional normed spaces, Discrete Comput. Geom. 37 (2007), no. 3, 419-442. MR 2301527 (2008b:52003), https://doi.org/10.1007/s00454-006-1298-z
  • [36] Konrad J. Swanepoel, Upper bounds for edge-antipodal and subequilateral polytopes, Period. Math. Hungar. 54 (2007), no. 1, 99-106. MR 2310370 (2008k:52020), https://doi.org/10.1007/s-10998-007-1099-0

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 52A37, 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41

Retrieve articles in all journals with MSC (2010): 52A37, 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41


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

DOI: https://doi.org/10.1090/tran/6601
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
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society