{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:24:29Z","timestamp":1740461069782,"version":"3.37.3"},"reference-count":36,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T00:00:00Z","timestamp":1729036800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,1]]},"abstract":"Abstract<\/jats:title>Given an \n$n\\times n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> symmetric matrix \n$W\\in [0,1]^{[n]\\times [n]}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, let \n${\\mathcal G}(n,W)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the random graph obtained by independently including each edge \n$jk\\in \\binom{[n]}{2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with probability \n$W_{jk}=W_{kj}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Given a degree sequence \n$\\textbf{d}=(d_1,\\ldots, d_n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, let \n${\\mathcal G}(n,\\textbf{d})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> denote a uniformly random graph with degree sequence \n$\\textbf{d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We couple \n${\\mathcal G}(n,W)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n${\\mathcal G}(n,\\textbf{d})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> together so that asymptotically almost surely \n${\\mathcal G}(n,W)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a subgraph of \n${\\mathcal G}(n,\\textbf{d})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where \n$W$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is some function of \n$\\textbf{d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Let \n$\\Delta (\\textbf{d})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> denote the maximum degree in \n$\\textbf{d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our coupling result is optimal when \n$\\Delta (\\textbf{d})^2\\ll \\|\\textbf{d}\\|_1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, that is, \n$W_{ij}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is asymptotic to \n${\\mathbb P}(ij\\in{\\mathcal G}(n,\\textbf{d}))$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for every \n$i,j\\in [n]$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also have coupling results for \n$\\textbf{d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> that are not constrained by the condition \n$\\Delta (\\textbf{d})^2\\ll \\|\\textbf{d}\\|_1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. For such \n$\\textbf{d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> our coupling result is still close to optimal, in the sense that \n$W_{ij}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is asymptotic to \n${\\mathbb P}(ij\\in{\\mathcal G}(n,\\textbf{d}))$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for most pairs \n$ij\\in \\binom{[n]}{2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548324000300","type":"journal-article","created":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T06:21:09Z","timestamp":1729059669000},"page":"115-130","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Embedding theorems for random graphs with specified degrees"],"prefix":"10.1017","volume":"34","author":[{"given":"Pu","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ohapkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,10,16]]},"reference":[{"key":"S0963548324000300_ref5","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1002\/rsa.20401","article-title":"Sir epidemics on random graphs with a fixed degree sequence","volume":"41","author":"Bohman","year":"2012","journal-title":"Random Struct. Algor."},{"key":"S0963548324000300_ref21","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.aim.2015.09.002","article-title":"Enumeration of graphs with a heavy-tailed degree sequence","volume":"287","author":"Gao","year":"2016","journal-title":"Adv. Math."},{"key":"S0963548324000300_ref26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0963548322000049","article-title":"Sandwiching biregular random graphs","volume":"32","author":"Klimo\u0161ov\u00e1","year":"2023","journal-title":"Combin. Probab. Comput."},{"volume-title":"Exponential random graph models for social networks: theory, methods, and applications","year":"2013","author":"Lusher","key":"S0963548324000300_ref29"},{"key":"S0963548324000300_ref32","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF01275671","article-title":"Asymptotic enumeration by degree sequence of graphs with degrees \n\n\n\n$o(n^{1\/2})$","volume":"11","author":"McKay","year":"1991","journal-title":"Combinatorica."},{"key":"S0963548324000300_ref20","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1002\/rsa.21123","article-title":"Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity","volume":"62","author":"Gao","year":"2023","journal-title":"Random Struct. Algor."},{"key":"S0963548324000300_ref33","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1177\/1548512912450370","article-title":"A random graph generation algorithm for the analysis of social networks","volume":"11","author":"Morris","year":"2014","journal-title":"J. Def. Model. Simul."},{"key":"S0963548324000300_ref35","doi-asserted-by":"crossref","DOI":"10.1017\/9781316795552","volume-title":"Random graphs and complex networks","author":"Van Der Hofstad","year":"2024"},{"key":"S0963548324000300_ref22","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1002\/rsa.20189","article-title":"Distribution of subgraphs of random regular graphs","volume":"32","author":"Gao","year":"2008","journal-title":"Random Struct. Algor."},{"key":"S0963548324000300_ref36","doi-asserted-by":"crossref","unstructured":"[36] Wormald, N. C. , et al. (1999) Models of random regular graphs, London mathematical society lecture note series, 239\u2013298.","DOI":"10.1017\/CBO9780511721335.010"},{"key":"S0963548324000300_ref23","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: first steps","volume":"5","author":"Holland","year":"1983","journal-title":"Soc. Networks."},{"key":"S0963548324000300_ref25","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.aim.2003.10.007","article-title":"Sandwiching random graphs: universality between random graph models","volume":"188","author":"Kim","year":"2004","journal-title":"Adv. Math."},{"key":"S0963548324000300_ref31","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/S0195-6698(13)80042-X","article-title":"Asymptotic enumeration by degree sequence of graphs of high degree","volume":"11","author":"McKay","year":"1990","journal-title":"Eur. J. Combin."},{"key":"S0963548324000300_ref30","first-page":"15","article-title":"Asymptotics for symmetric 0-1 matrices with prescribed row sums","volume":"19","author":"McKay","year":"1985","journal-title":"Ars. Combin."},{"key":"S0963548324000300_ref28","unstructured":"[28] Liebenau, A. and Wormald, N. (2017) Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, arXiv preprint arXiv: 1702.08373."},{"key":"S0963548324000300_ref24","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1002\/rsa.20754","article-title":"Complex martingales and asymptotic enumeration","volume":"52","author":"Isaev","year":"2018","journal-title":"Random Struct. Algor."},{"key":"S0963548324000300_ref6","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","article-title":"A probabilistic proof of an asymptotic formula for the number of labelled regular graphs","volume":"1","author":"Bollob\u00e1s","year":"1980","journal-title":"Eur. J. Combin."},{"key":"S0963548324000300_ref34","doi-asserted-by":"crossref","first-page":"026118","DOI":"10.1103\/PhysRevE.64.026118","article-title":"Random graphs with arbitrary degree distributions and their applications","volume":"64","author":"Newman","year":"2001","journal-title":"Phys. Rev. E."},{"key":"S0963548324000300_ref3","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1002\/rsa.20409","article-title":"The number of graphs and a random graph with a given degree sequence","volume":"42","author":"Barvinok","year":"2013","journal-title":"Random Struct. Algor."},{"key":"S0963548324000300_ref1","doi-asserted-by":"crossref","first-page":"1854","DOI":"10.1137\/19M1296069","article-title":"Hamiltonicity of random graphs in the stochastic block model","volume":"35","author":"Anastos","year":"2021","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548324000300_ref16","doi-asserted-by":"crossref","first-page":"475","DOI":"10.4007\/annals.2021.194.2.2","article-title":"Thresholds versus fractional expectation-thresholds","volume":"194","author":"Frankston","year":"2021","journal-title":"Ann. Math."},{"key":"S0963548324000300_ref13","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1017\/S0963548301005090","article-title":"Random regular graphs of non-constant degree: connectivity and hamiltonicity","volume":"11","author":"Cooper","year":"2002","journal-title":"Combin. Probab. Comput."},{"key":"S0963548324000300_ref19","unstructured":"[19] Gao, P. , Isaev, M. and McKay, B. D. (2023), Kim-vu\u2019s sandwich conjecture is true for all $ d\\ge \\log ^4 n$ , arXiv preprint arXiv:2011.09449."},{"key":"S0963548324000300_ref14","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1016\/j.jctb.2016.09.003","article-title":"Embedding the Erd\u0151s\u2013R\u00e9nyi hypergraph into the random regular hypergraph and Hamiltonicity","volume":"122","author":"Dudek","year":"2017","journal-title":"J. Combin. Theory, Ser. B."},{"key":"S0963548324000300_ref8","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1214\/10-AAP728","article-title":"Random graphs with a given degree sequence","volume":"21","author":"Chatterjee","year":"2011","journal-title":"Ann. Appl. Probab."},{"key":"S0963548324000300_ref27","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1002\/rsa.1013","article-title":"Random regular graphs of high degree","volume":"18","author":"Krivelevich","year":"2001","journal-title":"Random Struct. Algor."},{"key":"S0963548324000300_ref17","doi-asserted-by":"crossref","unstructured":"[17] Gao, P. , Isaev, M. and McKay, B. D. (2020) Sandwiching random regular graphs between binomial random graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM. pp. 690\u2013701.","DOI":"10.1137\/1.9781611975994.42"},{"key":"S0963548324000300_ref11","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1137\/050630106","article-title":"The volume of the giant component of a random graph with given expected degrees","volume":"20","author":"Chung","year":"2006","journal-title":"Siam. J. Discrete Math."},{"key":"S0963548324000300_ref10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/PL00012580","article-title":"Connected components in random graphs with given expected degree sequences","volume":"6","author":"Chung","year":"2002","journal-title":"Ann. Comb."},{"key":"S0963548324000300_ref9","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung","year":"2002","journal-title":"Proc. Natl. Acad. Sci."},{"key":"S0963548324000300_ref12","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1080\/15427951.2004.10129089","article-title":"The spectra of random graphs with given expected degrees","volume":"1","author":"Chung","year":"2004","journal-title":"Internet Math."},{"key":"S0963548324000300_ref2","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.aim.2009.12.001","article-title":"On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries","volume":"224","author":"Barvinok","year":"2010","journal-title":"Adv. Math."},{"key":"S0963548324000300_ref4","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","article-title":"The asymptotic number of labeled graphs with given degree sequences","volume":"24","author":"Bender","year":"1978","journal-title":"J. Combin. Theory, Ser. A."},{"key":"S0963548324000300_ref18","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00440-022-01157-6","article-title":"Sandwiching dense random regular graphs between binomial random graphs","volume":"184","author":"Gao","year":"2022","journal-title":"Probab. Theory Rel."},{"volume-title":"Random graphs","year":"1998","author":"Bollob\u00e1s","key":"S0963548324000300_ref7"},{"key":"S0963548324000300_ref15","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/rsa.20215","article-title":"The order of the largest complete minor in a random graph","volume":"33","author":"Fountoulakis","year":"2008","journal-title":"Random Struct. Algor."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T09:51:36Z","timestamp":1740390696000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000300\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,16]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["S0963548324000300"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000300","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,10,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}