{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T07:11:37Z","timestamp":1721113897937},"reference-count":24,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T00:00:00Z","timestamp":1668816000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["NSERCRGPIN\u201004173\u20102019"],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2023,7]]},"abstract":"Abstract<\/jats:title>Given a graphical degree sequence , let denote a uniformly random graph on vertex set where vertex has degree for every . We give upper and lower bounds on the joint probability of an arbitrary set of edges in , and we link these probability estimates to the corresponding probabilities in the configuration model. Then we show that many existing results of in the literature can be significantly improved with simpler proofs, by applying this new probabilistic tool. One example we give concerns the chromatic number of . In another application, we use these joint probabilities to study the connectivity of . Under some rather mild condition on \u2014in particular, if where is the maximum component of \u2014we fully characterize the connectivity phase transition of . We also give sufficient conditions for being connected when is unrestricted.<\/jats:p>","DOI":"10.1002\/rsa.21123","type":"journal-article","created":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T14:17:20Z","timestamp":1668867440000},"page":"911-934","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity"],"prefix":"10.1002","volume":"62","author":[{"given":"Pu","family":"Gao","sequence":"first","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo Waterloo Ontario Canada"}]},{"given":"Yuval","family":"Ohapkin","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo Waterloo Ontario Canada"}]}],"member":"311","published-online":{"date-parts":[[2022,11,19]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20409"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005090"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005254"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02066689"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1177159"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000177"},{"key":"e_1_2_7_10_1","volume-title":"On random regular graphs with non\u2010constant degree","author":"Frieze A.","year":"1988"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008388"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90070-E"},{"key":"e_1_2_7_13_1","doi-asserted-by":"crossref","unstructured":"P.Gao M.Isaev andB. D.McKay Sandwiching random regular graphs between binomial random graphs Proc. 14th Annu. ACM\u2010SIAM Symp. Discr. Algor. SIAM 2020 pp. 690\u2013701.","DOI":"10.1137\/1.9781611975994.42"},{"key":"e_1_2_7_14_1","unstructured":"P.Gao R.van derHofstad A.Southwell andC.Stegehuis Counting triangles in power\u2010law uniform random graphs.arXiv preprint arXiv:1812.04289 2018."},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20754"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20911"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0757-1"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.09.032"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1013"},{"key":"e_1_2_7_20_1","unstructured":"T.Luczak Sparse random graphs with a given degree sequence Proc. Symp. Random Graphs Poznan 1989 pp. 165\u2013182."},{"key":"e_1_2_7_21_1","unstructured":"B. D.McKay Subgraphs of random graphs with specified degrees 1981."},{"key":"e_1_2_7_22_1","first-page":"225","article-title":"Asymptotics for 0\u20101 matrices with prescribed line sums","author":"McKay B. D.","year":"1984","journal-title":"Enum. Des."},{"key":"e_1_2_7_23_1","doi-asserted-by":"crossref","unstructured":"B. D.McKay Subgraphs of dense random graphs with specified degrees.arXiv preprint arXiv:1002.3018 2010.","DOI":"10.1017\/S0963548311000034"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003526"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80021-4"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21123","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.21123","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T01:22:43Z","timestamp":1692494563000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.21123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,19]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1002\/rsa.21123"],"URL":"https:\/\/doi.org\/10.1002\/rsa.21123","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,19]]},"assertion":[{"value":"2021-03-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}