{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:34:40Z","timestamp":1772516080753,"version":"3.50.1"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T00:00:00Z","timestamp":1513641600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:p>We use the probabilistic method to obtain versions of the colourful Carath\u00e9odory theorem and Tverberg's theorem with tolerance.<\/jats:p><jats:p>In particular, we give bounds for the smallest integer <jats:italic>N<\/jats:italic> = <jats:italic>N<\/jats:italic>(<jats:italic>t<\/jats:italic>,<jats:italic>d<\/jats:italic>,<jats:italic>r<\/jats:italic>) such that for any <jats:italic>N<\/jats:italic> points in \u211d<jats:sup><jats:italic>d<\/jats:italic><\/jats:sup>, there is a partition of them into <jats:italic>r<\/jats:italic> parts for which the following condition holds: after removing any <jats:italic>t<\/jats:italic> points from the set, the convex hulls of what is left in each part intersect.<\/jats:p><jats:p>We prove a bound <jats:italic>N<\/jats:italic> = <jats:italic>rt<\/jats:italic> + <jats:italic>O<\/jats:italic>(<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548317000591_inline1\"\/><jats:tex-math>$\\sqrt{t}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) for fixed <jats:italic>r<\/jats:italic>,<jats:italic>d<\/jats:italic> which is polynomial in each parameters. Our bounds extend to colourful versions of Tverberg's theorem, as well as Reay-type variations of this theorem.<\/jats:p>","DOI":"10.1017\/s0963548317000591","type":"journal-article","created":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T09:27:00Z","timestamp":1513675620000},"page":"427-440","source":"Crossref","is-referenced-by-count":12,"title":["Robust Tverberg and Colourful Carath\u00e9odory Results via Random Choice"],"prefix":"10.1017","volume":"27","author":[{"given":"PABLO","family":"SOBER\u00d3N","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,12,19]]},"reference":[{"key":"S0963548317000591_ref37","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-41.1.123"},{"key":"S0963548317000591_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02808223"},{"key":"S0963548317000591_ref31","unstructured":"Rolnick D. and Sober\u00f3n P. (2016) Algorithms for Tverberg's theorem via centerpoint theorems. arXiv:1601.03083v2"},{"key":"S0963548317000591_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760885"},{"key":"S0963548317000591_ref28","first-page":"295","volume-title":"ISAAC 2013: International Symposium on Algorithms and Computation","author":"Mulzer","year":"2013"},{"key":"S0963548317000591_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9296-6"},{"key":"S0963548317000591_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542395"},{"key":"S0963548317000591_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.11.040"},{"key":"S0963548317000591_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"S0963548317000591_ref17","unstructured":"Garc\u00eda-Col\u00edn N. (2007) Applying Tverberg type theorems to geometric problems. PhD thesis, University College London."},{"key":"S0963548317000591_ref16","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2000.0490"},{"key":"S0963548317000591_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187879"},{"key":"S0963548317000591_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"S0963548317000591_ref10","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdu049"},{"key":"S0963548317000591_ref9","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.3.550"},{"key":"S0963548317000591_ref7","unstructured":"B\u00e1r\u00e1ny I. Personal communication."},{"key":"S0963548317000591_ref6","first-page":"1","volume-title":"Geometry, Structure and Randomness in Combinatorics","author":"B\u00e1r\u00e1ny","year":"2015"},{"key":"S0963548317000591_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90115-7"},{"key":"S0963548317000591_ref4","unstructured":"Asada M. , Chen R. , Frick F. , Huang F. , Polevy M. , Stoner D. , Tsang L. H. and Wellner Z. (2016) On Reay's relaxed Tverberg conjecture and generalizations of Conway's thrackle conjecture. arXiv:1608.04279"},{"key":"S0963548317000591_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548317000591_ref1","first-page":"9","volume-title":"Theory and Practice of Combinatorics","author":"Ajtai","year":"1982"},{"key":"S0963548317000591_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9379-z"},{"key":"S0963548317000591_ref12","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/516"},{"key":"S0963548317000591_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2427-5"},{"key":"S0963548317000591_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.01.009"},{"key":"S0963548317000591_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9180-4"},{"key":"S0963548317000591_ref36","unstructured":"Tukey J. W. (1975) Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vol. 2, Canadian Mathematical Congress, pp. 523\u2013531."},{"key":"S0963548317000591_ref23","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/4.1.6"},{"key":"S0963548317000591_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397002976"},{"key":"S0963548317000591_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"S0963548317000591_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2969-7"},{"key":"S0963548317000591_ref24","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/072"},{"key":"S0963548317000591_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1434-2"},{"key":"S0963548317000591_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1474-5"},{"key":"S0963548317000591_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9875-x"},{"key":"S0963548317000591_ref8","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-45.2.314"},{"key":"S0963548317000591_ref15","doi-asserted-by":"publisher","DOI":"10.1142\/S021819599600023X"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T20:57:02Z","timestamp":1555275422000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000591\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,19]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["S0963548317000591"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000591","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,19]]}}}