{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T09:31:46Z","timestamp":1648978306550},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T00:00:00Z","timestamp":1494460800000},"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":[[2017,9]]},"abstract":"<jats:p>A class of graphs is called<jats:italic>bridge-addable<\/jats:italic>if, for each graph in the class and each pair<jats:italic>u<\/jats:italic>and<jats:italic>v<\/jats:italic>of vertices in different components, the graph obtained by adding an edge joining<jats:italic>u<\/jats:italic>and<jats:italic>v<\/jats:italic>must also be in the class. The concept was introduced in 2005 by McDiarmid, Steger and Welsh, who showed that, for a random graph sampled uniformly from such a class, the probability that it is connected is at least 1\/<jats:italic>e<\/jats:italic>.<\/jats:p><jats:p>We generalize this and related results to bridge-addable classes with edge-weights which have an edge-expansion property. Here, a graph is sampled with probability proportional to the product of its edge-weights. We obtain for example lower bounds for the probability of connectedness of a graph sampled uniformly from a relatively bridge-addable class of graphs, where some but not necessarily all of the possible bridges are allowed to be introduced. Furthermore, we investigate whether these bounds are tight, and in particular give detailed results about random forests in complete balanced multipartite graphs.<\/jats:p>","DOI":"10.1017\/s0963548317000128","type":"journal-article","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T12:33:09Z","timestamp":1494505989000},"page":"697-719","source":"Crossref","is-referenced-by-count":0,"title":["Bridge-Addability, Edge-Expansion and Connectivity"],"prefix":"10.1017","volume":"26","author":[{"given":"COLIN","family":"McDIARMID","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KERSTIN","family":"WELLER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,5,11]]},"reference":[{"key":"S0963548317000128_ref11","doi-asserted-by":"crossref","first-page":"P53","DOI":"10.37236\/2596","article-title":"Connectivity for random graphs from a weighted bridge-addable class","volume":"19","author":"McDiarmid","year":"2012","journal-title":"Electron. J. Combin."},{"key":"S0963548317000128_ref12","doi-asserted-by":"crossref","first-page":"P52","DOI":"10.37236\/2793","article-title":"Random graphs from a weighted minor-closed class","volume":"20","author":"McDiarmid","year":"2013","journal-title":"Electron. J. Combin."},{"key":"S0963548317000128_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.007"},{"key":"S0963548317000128_ref16","unstructured":"Moon J. W. (1970) Counting Labelled Trees. From lectures delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver) 1969: Canadian Mathematical Congress, Montreal, Quebec."},{"key":"S0963548317000128_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309009717"},{"key":"S0963548317000128_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548317000128_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33700-8_15"},{"key":"S0963548317000128_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100036173"},{"key":"S0963548317000128_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.12.001"},{"key":"S0963548317000128_ref17","unstructured":"Norine S. (2013) Connectivity of addable classes of forests (draft). http:\/\/www.math.mcgill.ca\/snorin\/papers\/Forests.pdf"},{"key":"S0963548317000128_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548317000128_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548317000128_ref7","unstructured":"Chapuy G. and Perarnau G. (2015) Connectivity in bridge-addable graph classes: The McDiarmid\u2013Steger\u2013Welsh conjecture. arXiv:1504.06344"},{"key":"S0963548317000128_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000272"},{"key":"S0963548317000128_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54423-1_34"},{"key":"S0963548317000128_ref5","unstructured":"Balister P. , Bollob\u00e1s B. and Gerke S. (2010) Connectivity of random addable graphs. In Proc. ICDM 2008, number 13, pp. 127\u2013134."},{"key":"S0963548317000128_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.09.003"},{"key":"S0963548317000128_ref3","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-047-1"},{"key":"S0963548317000128_ref18","first-page":"73","article-title":"Some remarks on the theory of trees.","volume":"4","author":"R\u00e9nyi","year":"1959","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T07:56:26Z","timestamp":1602057386000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000128\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,11]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["S0963548317000128"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000128","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,11]]}}}