{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T05:57:58Z","timestamp":1771480678093,"version":"3.50.1"},"reference-count":20,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,2,7]],"date-time":"2007-02-07T00:00:00Z","timestamp":1170806400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2007,10]]},"abstract":"Abstract<\/jats:title>While it is exponentially unlikely that a sparse random graph or hypergraph is connected, with probability 1 \u2212 o<\/jats:italic>(1) such a graph has a \u201cgiant component\u201d that, given its numbers of edges and vertices, is a uniformly distributed connected graph. This simple observation allows us to estimate the number of connected graphs, and more generally the number of connected d<\/jats:italic>\u2010uniform hypergraphs, on n<\/jats:italic> vertices with ((d<\/jats:italic> \u2212 1)\u22121<\/jats:sup> + \u03b5<\/jats:italic>)n<\/jats:italic> \u2264 m<\/jats:italic> = o<\/jats:italic>(n<\/jats:italic>lnn<\/jats:italic>) edges, where \u03b5<\/jats:italic> > 0 is arbitrarily small but independent of n<\/jats:italic>. We also estimate the probability that a binomial random hypergraph H<\/jats:italic>d<\/jats:italic><\/jats:sub>(n<\/jats:italic>,p<\/jats:italic>) is connected, and determine the expected number of edges of H<\/jats:italic>d<\/jats:italic><\/jats:sub>(n<\/jats:italic>,p<\/jats:italic>) given that it is connected. This extends prior work of Bender et al. (Random Struct Algorithm 1 (1990), 127\u2013169) on the number of connected graphs. While Bender et al. (1990) is based on a recursion relation satisfied by the number of connected graphs, so that the argument is to some extent enumerative, we present a purely probabilistic approach. \u00a9 2007 Wiley Periodicals, Inc. Random Struct., 2007<\/jats:p>","DOI":"10.1002\/rsa.20160","type":"journal-article","created":{"date-parts":[[2007,2,7]],"date-time":"2007-02-07T17:40:15Z","timestamp":1170870015000},"page":"288-329","source":"Crossref","is-referenced-by-count":20,"title":["Counting connected graphs and hypergraphs via the probabilistic method"],"prefix":"10.1002","volume":"31","author":[{"given":"Amin","family":"Coja\u2010Oghlan","sequence":"first","affiliation":[]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[]},{"given":"Vishal","family":"Sanwalani","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,2,7]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_3_2","unstructured":"T.Andriamampianina V.Ravelomanana Enumeration of connected uniform hypergraphs Proceedings of FPSAC Messina Italy 2005."},{"key":"e_1_2_1_4_2","unstructured":"N.Arora J.Spencer Generating random connected graphs Preprint (2005)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300004302"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010202"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030208"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_2_1_9_2","volume-title":"Introduction to probability theory and its applications","author":"Feller W.","year":"1968"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","first-page":"R34","DOI":"10.37236\/1787","article-title":"Airy phenomena and analytic combinatorics of connected graphs","volume":"11","author":"Flajolet P.","year":"2004","journal-title":"Electron J Combinator"},{"key":"e_1_2_1_11_2","article-title":"Counting connected graphs asymptotically","author":"van der Hofstad R.","journal-title":"Eur J Combinator"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070406"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040303"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00464-2"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00076-3"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010203"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004400050149"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010306"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.005"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579445"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20160","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T13:01:01Z","timestamp":1697547661000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,7]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1002\/rsa.20160"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20160","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2,7]]}}}