{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:24:33Z","timestamp":1786980273416,"version":"build-2736575974"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T00:00:00Z","timestamp":1712188800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T00:00:00Z","timestamp":1712188800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004375","name":"Tel Aviv University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004375","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,8]]},"abstract":"Abstract<\/jats:title>\n \n It is known that many different types of finite random subgraph models undergo quantitatively similar phase transitions around their percolation thresholds, and the proofs of these results rely on isoperimetric properties of the underlying host graph. Recently, the authors showed that such a phase transition occurs in a large class of regular high-dimensional product graphs, generalising a classic result for the hypercube. In this paper we give new isoperimetric inequalities for such regular high-dimensional product graphs, which generalise the well-known isoperimetric inequality of Harper for the hypercube, and are asymptotically sharp for a wide range of set sizes. We then use these isoperimetric properties to investigate the structure of the giant component\n \n \n $$L_1$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in supercritical percolation on these product graphs, that is, when\n \n \n $$p=\\frac{1+\\epsilon }{d}$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n =<\/mml:mo>\n \n \n 1<\/mml:mn>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , where\n d<\/jats:italic>\n is the degree of the product graph and\n \n \n $$\\epsilon >0$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is a small enough constant. We show that typically\n \n \n $$L_1$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has edge-expansion\n \n \n $$\\Omega \\left( \\frac{1}{d\\ln d}\\right) $$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n \n \n 1<\/mml:mn>\n \n d<\/mml:mi>\n ln<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Furthermore, we show that\n \n \n $$L_1$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n likely contains a linear-sized subgraph with vertex-expansion\n \n \n $$\\Omega \\left( \\frac{1}{d\\ln d}\\right) $$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n \n \n 1<\/mml:mn>\n \n d<\/mml:mi>\n ln<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . These results are best possible up to the logarithmic factor in\n d<\/jats:italic>\n . Using these likely expansion properties, we determine, up to small polylogarithmic factors in\n d<\/jats:italic>\n , the likely diameter of\n \n \n $$L_1$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n as well as the typical mixing time of a lazy random walk on\n \n \n $$L_1$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Furthermore, we show the likely existence of a cycle of length\n \n \n $$\\Omega \\left( \\frac{n}{d\\ln d}\\right) $$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n \n \n n<\/mml:mi>\n \n d<\/mml:mi>\n ln<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . These results not only generalise, but also improve substantially upon the known bounds in the case of the hypercube, where in particular the likely diameter and typical mixing time of\n \n \n $$L_1$$<\/jats:tex-math>\n \n \n L<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n were previously only known to be polynomial in\n d<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1007\/s00493-024-00089-0","type":"journal-article","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T08:01:41Z","timestamp":1712217701000},"page":"741-784","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Isoperimetric Inequalities and Supercritical Percolation on High-Dimensional Graphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Sahar","family":"Diskin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joshua","family":"Erde","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihyun","family":"Kang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,4]]},"reference":[{"issue":"2","key":"89_CR1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0893-9659(95)00015-I","volume":"8","author":"R Ahlswede","year":"1995","unstructured":"Ahlswede, R., Bezrukov, S.L.: Edge isoperimetric theorems for integer point arrays. Appl. Math. Lett. 8(2), 75\u201380 (1995)","journal-title":"Appl. Math. Lett."},{"key":"89_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579172","volume":"1","author":"M Ajtai","year":"1981","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: The longest path in a random graph. Combinatorica 1, 1\u201312 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"89_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579276","volume":"2","author":"M Ajtai","year":"1982","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Largest random component of a $$k$$-cube. Combinatorica 2(1), 1\u20137 (1982)","journal-title":"Combinatorica"},{"issue":"3","key":"89_CR4","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1214\/009117904000000414","volume":"32","author":"N Alon","year":"2004","unstructured":"Alon, N., Benjamini, I., Stacey, A.: Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32(3), 1727\u20131745 (2004)","journal-title":"Ann. Probab."},{"issue":"1\u20133","key":"89_CR5","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","volume":"72","author":"N Alon","year":"1988","unstructured":"Alon, N., Chung, F.R.K.: Explicit construction of linear sized tolerant networks. Discret. Math. 72(1\u20133), 15\u201319 (1988)","journal-title":"Discret. Math."},{"issue":"1","key":"89_CR6","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N Alon","year":"1985","unstructured":"Alon, N., Milman, V.D.: $$\\lambda _1$$, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38(1), 73\u201388 (1985)","journal-title":"J. Combin. Theory Ser. B"},{"key":"89_CR7","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 4th edn. Wiley, Hoboken (2016)","edition":"4"},{"issue":"2018","key":"89_CR8","first-page":"1","volume":"7","author":"B Barber","year":"2018","unstructured":"Barber, B., Erde, J.: Isoperimetry in integer lattices. Discret. Anal. 7(2018), 1\u201316 (2018)","journal-title":"Discret. Anal."},{"issue":"12","key":"89_CR9","first-page":"5021","volume":"151","author":"B Barber","year":"2023","unstructured":"Barber, B., Erde, J., Keevash, P., Roberts, A.: Isoperimetric stability in lattices. Proc. Am. Math. Soc. 151(12), 5021\u20135029 (2023)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"89_CR10","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1002\/rsa.20539","volume":"45","author":"I Benjamini","year":"2014","unstructured":"Benjamini, I., Kozma, G., Wormald, N.: The mixing time of the giant component of a random graph. Random Struct. Algorithms 45(3), 383\u2013407 (2014)","journal-title":"Random Struct. Algorithms"},{"key":"89_CR11","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1137\/0115129","volume":"15","author":"AJ Bernstein","year":"1967","unstructured":"Bernstein, A.J.: Maximally connected arrays on the $$n$$-cube. SIAM J. Appl. Math. 15, 1485\u20131489 (1967)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"89_CR12","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/PL00009825","volume":"18","author":"A Beveridge","year":"1998","unstructured":"Beveridge, A., Frieze, A., McDiarmid, C.: Random minimum length spanning trees in regular graphs. Combinatorica 18(3), 311\u2013333 (1998)","journal-title":"Combinatorica"},{"key":"89_CR13","first-page":"59","volume":"3","author":"SL Bezrukov","year":"1994","unstructured":"Bezrukov, S.L.: Isoperimetric problems in discrete spaces. Extremal Probl. Finite Sets 3, 59\u201391 (1994)","journal-title":"Extremal Probl. Finite Sets"},{"key":"89_CR14","first-page":"157","volume":"7","author":"SL Bezrukov","year":"1999","unstructured":"Bezrukov, S.L.: Edge isoperimetric problems on graphs. Graph Theory Combin Biol 7, 157\u2013197 (1999)","journal-title":"Graph Theory Combin Biol"},{"issue":"3","key":"89_CR15","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0304-3975(03)00232-9","volume":"307","author":"SL Bezrukov","year":"2003","unstructured":"Bezrukov, S.L., Els\u00e4sser, R.: Edge-isoperimetric problems for cartesian powers of regular graphs. Theor. Comput. Sci. 307(3), 473\u2013492 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"89_CR16","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0195-6698(88)80014-3","volume":"9","author":"B Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B.: The isoperimetric number of random regular graphs. Eur. J. Combin. 9(3), 241\u2013244 (1988)","journal-title":"Eur. J. Combin."},{"issue":"1","key":"89_CR17","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/rsa.20168","volume":"31","author":"B Bollob\u00e0s","year":"2007","unstructured":"Bollob\u00e0s, B., Janson, S., Riordan, O.: The phase transition in inhomogeneous random graphs. Random Struct. Algorithms 31(1), 3\u2013122 (2007)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"89_CR18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/rsa.3240030106","volume":"3","author":"B Bollob\u00e1s","year":"1992","unstructured":"Bollob\u00e1s, B., Kohayakawa, Y., \u0141uczak, T.: The evolution of random subgraphs of the cube. Random Struct. Algorithms 3(1), 55\u201390 (1992)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"89_CR19","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/BF01275667","volume":"11","author":"B Bollob\u00e1s","year":"1991","unstructured":"Bollob\u00e1s, B., Leader, I.: Edge-isoperimetric inequalities in the grid. Combinatorica 11(4), 299\u2013314 (1991)","journal-title":"Combinatorica"},{"key":"89_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139167383","volume-title":"Percolation","author":"B Bollob\u00e1s","year":"2006","unstructured":"Bollob\u00e1s, B., Riordan, O.: Percolation. Cambridge University Press, Cambridge (2006)"},{"issue":"2","key":"89_CR21","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1002\/rsa.20051","volume":"27","author":"C Borgs","year":"2005","unstructured":"Borgs, C., Chayes, J.T., Hofstad, Rvd, Slade, G., Spencer, J.: Random subgraphs of finite graphs. I: the scaling window under the triangle condition. Random Struct. Algorithms 27(2), 137\u2013184 (2005)","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"89_CR22","doi-asserted-by":"crossref","first-page":"1886","DOI":"10.1214\/009117905000000260","volume":"33","author":"C Borgs","year":"2005","unstructured":"Borgs, C., Chayes, J.T., Hofstad, Rvd, Slade, G., Spencer, J.: Random subgraphs of finite graphs. II: the lace expansion and the triangle condition. Ann. Probab. 33(5), 1886\u20131944 (2005)","journal-title":"Ann. Probab."},{"key":"89_CR23","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1017\/S0305004100032680","volume":"53","author":"SB Broadbent","year":"1957","unstructured":"Broadbent, S.B., Hammersley, J.M.: Percolation processes. I: crystals and mazes. Proc. Camb. Philos. Soc. 53, 629\u2013641 (1957)","journal-title":"Proc. Camb. Philos. Soc."},{"issue":"1","key":"89_CR24","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0012-365X(01)00432-0","volume":"254","author":"TA Carlson","year":"2002","unstructured":"Carlson, T.A.: The edge-isoperimetric problem for discrete tori. Discret. Math. 254(1), 33\u201349 (2002)","journal-title":"Discret. Math."},{"key":"89_CR25","doi-asserted-by":"crossref","unstructured":"Cheeger, J.: A lower bound for the smallest eigenvalue of the Laplacian. In: Problems in Analysis: A Symposium in Honor of Salomon Bochner (Princeton, 1969), pp. 195\u2013199. Princeton: Princeton University Press (1970)","DOI":"10.1515\/9781400869312-013"},{"issue":"2","key":"89_CR26","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1017\/S0963548397003350","volume":"7","author":"FRK Chung","year":"1998","unstructured":"Chung, F.R.K., Tetali, P.: Isoperimetric inequalities for Cartesian products of graphs. Combin. Probab. Comput. 7(2), 141\u2013148 (1998)","journal-title":"Combin. Probab. Comput."},{"key":"89_CR27","unstructured":"Condon, P., Espuny D\u00edaz, A., Gir\u00e3o, A., K\u00fchn, D., Osthus, D.: Hamiltonicity of random subgraphs of the hypercube. Mem. Am. Math. Soc. (to appear)"},{"key":"89_CR28","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.ejc.2013.06.004","volume":"35","author":"J Ding","year":"2014","unstructured":"Ding, J., Lubetzky, E., Peres, Y.: Anatomy of the giant component: the strictly supercritical regime. Eur. J. Combin. 35, 155\u2013168 (2014)","journal-title":"Eur. J. Combin."},{"key":"89_CR29","doi-asserted-by":"crossref","unstructured":"Diskin, S., Erde, J., Kang, M., Krivelevich, M.: Percolation on high-dimensional product graphs. arXiv Preprint (2022). arXiv:2007.02891","DOI":"10.1017\/S0963548323000469"},{"key":"89_CR30","unstructured":"Diskin, S., Erde, J., Kang, M., Krivelevich, M.: Percolation on irregular high-dimensional product graphs. Combin. Probab. Comput. (to appear)"},{"key":"89_CR31","unstructured":"Diskin, S., Krivelevich, M.: Expansion in supercritical random subgraphs of expanders and its consequences. arXiV Preprint (2022). arXiv:2205.04852"},{"key":"89_CR32","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1214\/22-AOP1592","volume":"51","author":"J Erde","year":"2023","unstructured":"Erde, J., Kang, M., Krivelevich, M.: Expansion in supercritical random subgraphs of the hypercube and its consequences. Ann. Probab. 51, 127\u2013156 (2023)","journal-title":"Ann. Probab."},{"key":"89_CR33","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl. 5, 17\u201361 (1960)","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"issue":"3\u20134","key":"89_CR34","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/s00440-006-0003-8","volume":"137","author":"N Fountoulakis","year":"2007","unstructured":"Fountoulakis, N., Reed, B.A.: Faster mixing and small bottlenecks. Probab. Theory Relat. Fields 137(3\u20134), 475\u2013486 (2007)","journal-title":"Probab. Theory Relat. Fields"},{"issue":"1","key":"89_CR35","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/rsa.20210","volume":"33","author":"N Fountoulakis","year":"2008","unstructured":"Fountoulakis, N., Reed, B.A.: The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Struct. Algorithms 33(1), 68\u201386 (2008)","journal-title":"Random Struct. Algorithms"},{"key":"89_CR36","volume-title":"Introduction to random graphs","author":"A Frieze","year":"2016","unstructured":"Frieze, A., Karo\u0144ski, M.: Introduction to random graphs. Cambridge University Press, Cambridge (2016)"},{"issue":"1","key":"89_CR37","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1002\/rsa.10100","volume":"24","author":"A Frieze","year":"2004","unstructured":"Frieze, A., Krivelevich, M., Martin, R.: The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Struct. Algorithms 24(1), 42\u201350 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"89_CR38","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"key":"89_CR39","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03981-6","volume-title":"Percolation","author":"G Grimmett","year":"1999","unstructured":"Grimmett, G.: Percolation. Springer, Berlin (1999)"},{"key":"89_CR40","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. SIAM J. Appl. Math. 12, 131\u2013135 (1964)","journal-title":"SIAM J. Appl. Math."},{"key":"89_CR41","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0021-9800(66)80059-5","volume":"1","author":"LH Harper","year":"1966","unstructured":"Harper, L.H.: Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1, 385\u2013393 (1966)","journal-title":"J. Combin. Theory"},{"key":"89_CR42","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511616679","volume-title":"Global Methods for Combinatorial Isoperimetric Problems","author":"LH Harper","year":"2004","unstructured":"Harper, L.H.: Global Methods for Combinatorial Isoperimetric Problems, vol. 90. Cambridge University Press, Cambridge (2004)"},{"key":"89_CR43","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0012-365X(76)90058-3","volume":"14","author":"S Hart","year":"1976","unstructured":"Hart, S.: A note on the edges of the $$n$$-cube. Discret. Math. 14, 157\u2013163 (1976)","journal-title":"Discret. Math."},{"issue":"2","key":"89_CR44","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s00220-006-0152-8","volume":"270","author":"M Heydenreich","year":"2007","unstructured":"Heydenreich, M., van der Hofstad, R.: Random graph asymptotics on high-dimensional tori. Commun. Math. Phys. 270(2), 335\u2013358 (2007)","journal-title":"Commun. Math. Phys."},{"issue":"3\u20134","key":"89_CR45","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s00440-009-0258-y","volume":"149","author":"M Heydenreich","year":"2011","unstructured":"Heydenreich, M., van der Hofstad, R.: Random graph asymptotics on high-dimensional tori II: volume, diameter and mixing time. Probab. Theory Relat. Fields 149(3\u20134), 397\u2013415 (2011)","journal-title":"Probab. Theory Relat. Fields"},{"key":"89_CR46","doi-asserted-by":"crossref","unstructured":"Heydenreich, M., van der Hofstad, R.: Progress in High-Dimensional Percolation and Random Graphs. CRM Short Courses. Springer\/Centre de Recherches Math\u00e9matiques, Cham, Montreal (2017)","DOI":"10.1007\/978-3-319-62473-0"},{"issue":"4","key":"89_CR47","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. (N.S.) 43(4), 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc. (N.S.)"},{"key":"89_CR48","first-page":"313","volume":"25","author":"F Juh\u00e1sz","year":"1981","unstructured":"Juh\u00e1sz, F.: On the spectrum of a random graph. Algebraic Methods Graph Theory 25, 313\u2013316 (1981)","journal-title":"Algebraic Methods Graph Theory"},{"key":"89_CR49","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-2730-9","volume-title":"Percolation Theory for Mathematicians","author":"H Kesten","year":"1982","unstructured":"Kesten, H.: Percolation Theory for Mathematicians. Birkh\u00e4user, Boston (1982)"},{"issue":"1","key":"89_CR50","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1137\/17M1128721","volume":"32","author":"M Krivelevich","year":"2018","unstructured":"Krivelevich, M.: Finding and using expanders in locally sparse graphs. SIAM J. Discret. Math. 32(1), 611\u2013623 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"89_CR51","doi-asserted-by":"crossref","unstructured":"Krivelevich, M.: Expanders\u2014how to find them, and what to find in them. Surveys in Combinatorics 2019. London Mathematical Society Lecture Note Series Book, vol. 456, pp. 115\u2013142. Cambridge University Press, Cambridge (2019)","DOI":"10.1017\/9781108649094.005"},{"issue":"1","key":"89_CR52","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s00493-017-3701-1","volume":"39","author":"M Krivelevich","year":"2019","unstructured":"Krivelevich, M.: Long cycles in locally expanding graphs, with applications. Combinatorica 39(1), 135\u2013151 (2019)","journal-title":"Combinatorica"},{"issue":"4","key":"89_CR53","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1002\/rsa.20114","volume":"29","author":"M Krivelevich","year":"2006","unstructured":"Krivelevich, M., Nachmias, A.: Coloring complete bipartite graphs from random lists. Random Struct. Algorithms 29(4), 436\u2013449 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"89_CR54","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1137\/151002496","volume":"29","author":"M Krivelevich","year":"2015","unstructured":"Krivelevich, M., Reichman, D., Samotij, W.: Smoothed analysis on connected graphs. SIAM J. Discret. Math. 29(3), 1654\u20131669 (2015)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"89_CR55","doi-asserted-by":"crossref","first-page":"2389","DOI":"10.1137\/130942796","volume":"29","author":"VF Lev","year":"2015","unstructured":"Lev, V.F.: Edge-isoperimetric problem for Cayley graphs and generalized Takagi functions. SIAM J. Discret. Math. 29(4), 2389\u20132411 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"89_CR56","doi-asserted-by":"crossref","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2017)","DOI":"10.1090\/mbk\/107"},{"key":"89_CR57","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1080\/00029890.1964.11992272","volume":"71","author":"JH Lindsey","year":"1964","unstructured":"Lindsey, J.H.: Assignment of numbers to vertices. Am. Math. Mon. 71, 508\u2013516 (1964)","journal-title":"Am. Math. Mon."},{"issue":"2\u20133","key":"89_CR58","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/rsa.3240060204","volume":"6","author":"M Molloy","year":"1995","unstructured":"Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2\u20133), 161\u2013179 (1995)","journal-title":"Random Struct. Algorithms"},{"issue":"5\u20136","key":"89_CR59","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1017\/S0963548310000325","volume":"19","author":"O Riordan","year":"2010","unstructured":"Riordan, O., Wormald, N.: The diameter of sparse random graphs. Combin. Probab. Comput. 19(5\u20136), 835\u2013926 (2010)","journal-title":"Combin. Probab. Comput."},{"issue":"1","key":"89_CR60","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S0012-365X(99)00189-2","volume":"213","author":"JP Tillich","year":"2000","unstructured":"Tillich, J.P.: Edge isoperimetric inequalities for product graphs. Discret. Math. 213(1), 291\u2013320 (2000)","journal-title":"Discret. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00089-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00089-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00089-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T13:05:00Z","timestamp":1721826300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00089-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,4]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["89"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00089-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,4]]},"assertion":[{"value":"6 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}