{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T02:12:12Z","timestamp":1777342332174,"version":"3.51.4"},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T00:00:00Z","timestamp":1600819200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T00:00:00Z","timestamp":1600819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2434"],"award-info":[{"award-number":["GRK 2434"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,9]]},"abstract":"Abstract<\/jats:title>We consider the question of the largest possible combinatorial diameter among pure dimensional and strongly connected $$(d-1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n d<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-dimensional simplicial complexes on n<\/jats:italic> vertices, denoted $$H_s(n, d)$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Using a probabilistic construction we give a new lower bound on $$H_s(n, d)$$<\/jats:tex-math>\n \n \n H<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that is within an $$O(d^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> factor of the upper bound. This improves on the previously best known lower bound which was within a factor of $$e^{\\varTheta (d)}$$<\/jats:tex-math>\n \n e<\/mml:mi>\n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the upper bound. We also make a similar improvement in the case of pseudomanifolds.<\/jats:p>","DOI":"10.1007\/s00454-020-00248-2","type":"journal-article","created":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T13:02:55Z","timestamp":1600866175000},"page":"687-700","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Randomized Construction of Complexes with Large Diameter"],"prefix":"10.1007","volume":"66","author":[{"given":"Francisco","family":"Criado","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4666-0218","authenticated-orcid":false,"given":"Andrew","family":"Newman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,23]]},"reference":[{"key":"248_CR1","series-title":"Wiley Series in Discrete Mathematics and Optimization","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley, Hoboken (2016)"},{"issue":"2","key":"248_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0012-365X(92)90047-J","volume":"102","author":"L Caccetta","year":"1992","unstructured":"Caccetta, L., Smyth, W.F.: Graphs of maximum diameter. Discrete Math. 102(2), 121\u2013141 (1992)","journal-title":"Discrete Math."},{"issue":"3","key":"248_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00454-017-9888-5","volume":"58","author":"F Criado","year":"2017","unstructured":"Criado, F., Santos, F.: The maximum diameter of pure simplicial complexes and pseudo-manifolds. Discrete Comput. Geom. 58(3), 643\u2013649 (2017)","journal-title":"Discrete Comput. Geom."},{"key":"248_CR4","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on $3$-chromatic hypergraphs and some related questions. In: Infinite and Finite Sets (Keszthely 1973), vol. 2. Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 10, pp. 609\u2013627. North-Holland, Amsterdam (1975)"},{"key":"248_CR5","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1307\/mmj\/1028999370","volume":"12","author":"JW Moon","year":"1965","unstructured":"Moon, J.W.: On the diameter of a graph. Mich. Math. J. 12, 349\u2013351 (1965)","journal-title":"Mich. Math. J."},{"key":"248_CR6","unstructured":"Newman, A.: A lower bound on the number of homotopy types of simplicial complexes on $n$ vertices (2018). arXiv:1804.06787"},{"issue":"2","key":"248_CR7","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00454-018-9987-y","volume":"62","author":"A Newman","year":"2019","unstructured":"Newman, A.: Small simplicial complexes with prescribed torsion in homology. Discrete Comput. Geom. 62(2), 433\u2013460 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"248_CR8","unstructured":"Norris, J.R.: Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 2. Cambridge University Press, Cambridge (1998)"},{"issue":"1","key":"248_CR9","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012)","journal-title":"Ann. Math."},{"issue":"3","key":"248_CR10","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/s11750-013-0295-7","volume":"21","author":"F Santos","year":"2013","unstructured":"Santos, F.: Recent progress on the combinatorial diameter of polytopes and simplicial complexes. TOP 21(3), 426\u2013460 (2013)","journal-title":"TOP"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00248-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00248-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00248-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T01:14:57Z","timestamp":1632359697000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00248-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,23]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["248"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00248-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,23]]},"assertion":[{"value":"12 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}