{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T08:17:18Z","timestamp":1783671438147,"version":"3.55.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T00:00:00Z","timestamp":1779321600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T00:00:00Z","timestamp":1779321600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005187","name":"University of Athens","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005187","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n A graph\n \n \n $$G=(V,E)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is\n geometrically embeddable<\/jats:italic>\n into a normed space\n X<\/jats:italic>\n when there is a mapping\n \n \n $$\\zeta :V\\rightarrow X$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n \u2192<\/mml:mo>\n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that\n \n \n $$\\Vert \\zeta (v)-\\zeta (w)\\Vert _X\\leqslant 1$$<\/jats:tex-math>\n \n \n \n \n \u2016<\/mml:mo>\n \u03b6<\/mml:mi>\n \n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n -<\/mml:mo>\n \u03b6<\/mml:mi>\n \n (<\/mml:mo>\n w<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2016<\/mml:mo>\n <\/mml:mrow>\n X<\/mml:mi>\n <\/mml:msub>\n \u2a7d<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n if and only if\n \n \n $$\\{v,w\\}\\in E$$<\/jats:tex-math>\n \n \n {<\/mml:mo>\n v<\/mml:mi>\n ,<\/mml:mo>\n w<\/mml:mi>\n }<\/mml:mo>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , for all distinct\n \n \n $$v,w\\in V$$<\/jats:tex-math>\n \n \n v<\/mml:mi>\n ,<\/mml:mo>\n w<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Our result is the following universal threshold for the embeddability of trees. Let\n \n \n $$\\Delta \\geqslant 3$$<\/jats:tex-math>\n \n \n \u0394<\/mml:mi>\n \u2a7e<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and let\n N<\/jats:italic>\n be sufficiently large in terms of\n \n \n $$\\Delta $$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Every\n N<\/jats:italic>\n \u2013vertex tree of maximal degree at most\n \n \n $$\\Delta $$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is embeddable into any normed space of dimension at least\n \n \n $$64\\,\\frac{\\log N}{\\log \\log N}$$<\/jats:tex-math>\n \n \n 64<\/mml:mn>\n \n \n \n log<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n \n log<\/mml:mo>\n log<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and complete trees are non-embeddable into any normed space of dimension less than\n \n \n $$\\frac{1}{2}\\,\\frac{\\log N}{\\log \\log N}$$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n \n \n \n log<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n \n log<\/mml:mo>\n log<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In striking contrast, spectral expanders and random graphs are known to be non-embeddable in sublogarithmic dimension. Our result is based on a randomized embedding whose analysis utilizes the recent breakthroughs on Bourgain\u2019s slicing problem.\n <\/jats:p>","DOI":"10.1007\/s00493-026-00216-z","type":"journal-article","created":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T09:22:11Z","timestamp":1779355331000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Universal Threshold for Geometric Embeddings of Trees"],"prefix":"10.1007","volume":"46","author":[{"given":"Dylan J.","family":"Altschuler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pandelis","family":"Dodos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantin","family":"Tikhomirov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantinos","family":"Tyros","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,21]]},"reference":[{"key":"216_CR1","unstructured":"Altschuler, D.J., Tikhomirov, K.: Universal geometric non-embedding of random regular graphs. preprint available at arXiv:2501.09142 (2025)"},{"key":"216_CR2","unstructured":"Altschuler, D.J., Dodos, P., Tikhomirov, K., Tyros, K.: A combinatorial approach to nonlinear spectral gaps. preprint available at arXiv:2410.04394 (2024)"},{"key":"216_CR3","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons (2016)"},{"key":"216_CR4","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.jctb.2005.04.005","volume":"95","author":"Y Bilu","year":"2005","unstructured":"Bilu, Y., Linial, N.: Monotone maps, sphericity and bounded second eigenvalue. J. Combin. Theory Ser. B 95, 283\u2013299 (2005)","journal-title":"J. Combin. Theory Ser. B"},{"key":"216_CR5","unstructured":"Bizeul, P.: The slicing conjecture via small ball estimates. preprint available at arXiv:2501.06854 (2025)"},{"key":"216_CR6","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/BF02766125","volume":"56","author":"J Bourgain","year":"1986","unstructured":"Bourgain, J.: The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math. 56, 222\u2013230 (1986)","journal-title":"Israel J. Math."},{"key":"216_CR7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s00039-021-00558-4","volume":"31","author":"Y Chen","year":"2021","unstructured":"Chen, Y.: An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geom. Funct. Anal. 31, 34\u201361 (2021)","journal-title":"Geom. Funct. Anal."},{"key":"216_CR8","doi-asserted-by":"crossref","unstructured":"Eskenazis, A.: Average distortion embeddings, nonlinear spectral gaps, and a metric John theorem [after Assaf Naor], Ast\u00e9risque No. 438, S\u00e9minaire Bourbaki. Expos\u00e9s, Exp. No. 1188, 295\u2013333 Vol. 2021\/2022, pp. 1181\u20131196 (2022)","DOI":"10.24033\/ast.1189"},{"key":"216_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0195-6698(86)80026-9","volume":"7","author":"P Frankl","year":"1986","unstructured":"Frankl, P., Maehara, H.: Embedding the $$n$$-cube in lower dimensions. European J. Combin. 7, 221\u2013225 (1986)","journal-title":"European J. Combin."},{"key":"216_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P Frankl","year":"1988","unstructured":"Frankl, P., Maehara, H.: The Johnson-Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. B 44, 355\u2013362 (1988)","journal-title":"J. Combin. Theory Ser. B"},{"key":"216_CR11","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1090\/S0273-0979-02-00941-2","volume":"39","author":"RJ Gardner","year":"2002","unstructured":"Gardner, R.J.: The Brunn-Minkowski inequality. Bull. Amer. Math. Soc. 39, 355\u2013405 (2002)","journal-title":"Bull. Amer. Math. Soc."},{"key":"216_CR12","unstructured":"Guan, Q.: A note on Bourgain\u2019s slicing problem. preprint available at arXiv:2412.09075 (2024)"},{"key":"216_CR13","doi-asserted-by":"crossref","unstructured":"Johnson, W.B., Lindenstrauss, J.: Basic concepts in the geometry of Banach spaces. In: Handbook of the Geometry of Banach Spaces, Vol. 1, pp. 1\u201384. Elsevier (2001)","DOI":"10.1016\/S1874-5849(01)80003-6"},{"key":"216_CR14","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.jfa.2006.12.005","volume":"245","author":"B Klartag","year":"2007","unstructured":"Klartag, B.: Power-law estimates for the central limit theorem for convex sets. J. Funct. Anal. 245, 284\u2013310 (2007)","journal-title":"J. Funct. Anal."},{"key":"216_CR15","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1090\/bull\/1869","volume":"62","author":"B Klartag","year":"2025","unstructured":"Klartag, B., Lehec, J.: Isoperimetric inequalities in high-dimensional convex sets. Bull. Amer. Math. Soc. 62, 575\u2013642 (2025)","journal-title":"Bull. Amer. Math. Soc."},{"key":"216_CR16","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1007\/s00039-025-00718-w","volume":"35","author":"B Klartag","year":"2025","unstructured":"Klartag, B., Lehec, J.: Affirmative resolution of Bourgain\u2019s slicing problem using Guan\u2019s bound. Geom. Funct. Anal. 35, 1147\u20131168 (2025)","journal-title":"Geom. Funct. Anal."},{"key":"216_CR17","unstructured":"Klartag, B., Lehec, J.: Thin-shell bounds via parallel coupling. preprint available at arXiv:2507.15495 (2025)"},{"key":"216_CR18","volume-title":"The Concentration of Measure Phenomenon","author":"M Ledoux","year":"2001","unstructured":"Ledoux, M.: The Concentration of Measure Phenomenon, vol. 89. American Mathematical Society (2001)"},{"key":"216_CR19","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02785579","volume":"114","author":"J Matou\u0161ek","year":"1999","unstructured":"Matou\u0161ek, J.: On embedding trees into uniformly convex Banach spaces. Israel J. Math. 114, 221\u2013237 (1999)","journal-title":"Israel J. Math."},{"key":"216_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10240-013-0053-2","volume":"119","author":"M Mendel","year":"2014","unstructured":"Mendel, M., Naor, A.: Nonlinear spectral calculus and super-expanders. Publ. Math. Inst. Hautes \u00c9tud. Sci. 119, 1\u201395 (2014)","journal-title":"Publ. Math. Inst. Hautes \u00c9tud. Sci."},{"key":"216_CR21","doi-asserted-by":"crossref","unstructured":"Moser, W., Pach, J.: Recent developments in combinatorial geometry. New Trends in Discrete and Comput. Geom. 281\u2013302 (1993)","DOI":"10.1007\/978-3-642-58043-7_12"},{"key":"216_CR22","first-page":"1","volume":"2","author":"A Naor","year":"2014","unstructured":"Naor, A.: Comparison of metric spectral gaps. Anal. Geom. Metr. Spaces 2, 1\u201352 (2014)","journal-title":"Anal. Geom. Metr. Spaces"},{"key":"216_CR23","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(89)90142-8","volume":"74","author":"J Reiterman","year":"1989","unstructured":"Reiterman, J., R\u00f6dl, V., \u0160i\u0148ajov\u00e1, E.: Geometrical embeddings of graphs. Discrete Math. 74, 291\u2013319 (1989)","journal-title":"Discrete Math."},{"key":"216_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(92)90002-F","volume":"56","author":"J Reiterman","year":"1992","unstructured":"Reiterman, J., R\u00f6dl, V., \u0160i\u0148ajov\u00e1, E.: On embedding of graphs into Euclidean spaces of small dimension. J. Combin. Theory Ser. B 56, 1\u20138 (1992)","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-026-00216-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-026-00216-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-026-00216-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T07:50:45Z","timestamp":1783669845000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-026-00216-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,21]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["216"],"URL":"https:\/\/doi.org\/10.1007\/s00493-026-00216-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,21]]},"assertion":[{"value":"25 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"20"}}