{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T11:39:57Z","timestamp":1773142797060,"version":"3.50.1"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2011,2,17]],"date-time":"2011-02-17T00:00:00Z","timestamp":1297900800000},"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":[[2011,5]]},"abstract":"<jats:p>We show that a set <jats:italic>A<\/jats:italic> \u2282 {0, 1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> with edge-boundary of size at most\n<jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548311000083_eqnU1\"\/><\/jats:disp-formula>\ncan be made into a subcube by at most (2\u03b5\/log<jats:sub>2<\/jats:sub>(1\/\u03b5))|<jats:italic>A<\/jats:italic>| additions and deletions, provided \u03b5 is less than an absolute constant.<\/jats:p><jats:p>We deduce that if <jats:italic>A<\/jats:italic> \u2282 {0, 1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> has size 2<jats:italic><jats:sup>t<\/jats:sup><\/jats:italic> for some <jats:italic>t<\/jats:italic> \u2208 \u2115, and cannot be made into a subcube by fewer than \u03b4|<jats:italic>A<\/jats:italic>| additions and deletions, then its edge-boundary has size at least\n<jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548311000083_eqnU2\"\/><\/jats:disp-formula>\nprovided \u03b4 is less than an absolute constant. This is sharp whenever \u03b4 = 1\/2<jats:italic><jats:sup>j<\/jats:sup><\/jats:italic> for some <jats:italic>j<\/jats:italic> \u2208 {1, 2, .\u00a0.\u00a0., <jats:italic>t<\/jats:italic>}.<\/jats:p>","DOI":"10.1017\/s0963548311000083","type":"journal-article","created":{"date-parts":[[2011,2,17]],"date-time":"2011-02-17T10:39:23Z","timestamp":1297939163000},"page":"363-380","source":"Crossref","is-referenced-by-count":14,"title":["Almost Isoperimetric Subsets of the Discrete Cube"],"prefix":"10.1017","volume":"20","author":[{"given":"DAVID","family":"ELLIS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,2,17]]},"reference":[{"key":"S0963548311000083_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988612"},{"key":"S0963548311000083_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009809"},{"key":"S0963548311000083_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/0112012"},{"key":"S0963548311000083_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00024-6"},{"key":"S0963548311000083_ref13","doi-asserted-by":"publisher","DOI":"10.1214\/009117906000000287"},{"key":"S0963548311000083_ref12","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1080\/00029890.1964.11992272","article-title":"Assignment of numbers to vertices.","volume":"71","author":"Lindsey","year":"1964","journal-title":"Amer. Math. Monthly"},{"key":"S0963548311000083_ref11","unstructured":"[11] Leader I. Personal communication."},{"key":"S0963548311000083_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90058-3"},{"key":"S0963548311000083_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/0115129"},{"key":"S0963548311000083_ref15","unstructured":"[15] Samorodnitsky A. Personal communication."},{"key":"S0963548311000083_ref1","unstructured":"[1] Ben-Or M. and Linial N. (1985) Collective coin flipping, robust voting games, and minima of Banzhaf value. In Proc. 26th IEEE Symposium on the Foundations of Computer Science, pp. 408\u2013416."},{"key":"S0963548311000083_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.03.023"},{"key":"S0963548311000083_ref9","doi-asserted-by":"crossref","unstructured":"[9] Kahn J. , Kalai G. and Linial N. (1988) The influence of variables on boolean functions. In FOCS 1988, pp. 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"S0963548311000083_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008340"},{"key":"S0963548311000083_ref14","unstructured":"[14] Samorodnitsky A. (2009) Edge isoperimetric inequalities in the Hamming cube. Talk given at the IPAM Long Program in Combinatorics, Workshop IV: Analytical Methods in Combinatorics, Additive Number Theory and Computer Science, November 2009."},{"key":"S0963548311000083_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008474"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000083","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T08:47:01Z","timestamp":1556354821000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000083\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,17]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["S0963548311000083"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000083","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,17]]}}}