{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:46:40Z","timestamp":1773820000726,"version":"3.50.1"},"reference-count":19,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4332,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1994,12]]},"abstract":"Abstract<\/jats:title>The n<\/jats:italic>\u2010dimensional cube Q<\/jats:italic>n<\/jats:italic><\/jats:sup> is the graph whose vertices are the subsets of {1,\u2026n<\/jats:italic>}, with two vertices adjacent if and only if their symmetric difference is a singleton. Clearly Q<\/jats:italic>n<\/jats:italic><\/jats:sup> has diameter and radious n<\/jats:italic>. Write M<\/jats:italic> = n<\/jats:italic>2n\u20101<\/jats:sup> = e<\/jats:italic>(Q<\/jats:italic>n<\/jats:italic><\/jats:sup>) for the size of Q<\/jats:italic>n<\/jats:italic><\/jats:sup>. Let Q<\/jats:italic> = (Q<\/jats:italic>t<\/jats:italic><\/jats:sub>)o<\/jats:sub>M<\/jats:sup> be a random Q<\/jats:italic>n<\/jats:italic><\/jats:sup>\u2010process. Thus Q<\/jats:italic>t<\/jats:italic><\/jats:sup> is a spanning subgraph of Q<\/jats:italic>n<\/jats:italic><\/jats:sup> of size t<\/jats:italic>, and Q<\/jats:italic>t<\/jats:italic><\/jats:sub> is obtained from Q<\/jats:italic>t<\/jats:italic>\u20131<\/jats:sub> by the random addition of an edge of Q<\/jats:italic>n<\/jats:italic><\/jats:sup> not in Q<\/jats:italic>t<\/jats:italic>\u20131<\/jats:sub>, Let t<\/jats:italic>(k<\/jats:italic>)<\/jats:sup> = \u03c4(Q<\/jats:italic>;\u03b4\u2a7ek<\/jats:italic>) be the hitting time of the property of having minimal degree at least k<\/jats:italic>. We show that the diameter d<\/jats:italic>t<\/jats:italic><\/jats:sub> = diam (Q<\/jats:italic>t<\/jats:italic><\/jats:sub>) of Q<\/jats:italic>t<\/jats:italic><\/jats:sub> in almost every Q\u0303 behaves as follows: d<\/jats:italic>t<\/jats:italic><\/jats:sub> starts infinite and is first finite at time t<\/jats:italic>(1)<\/jats:sup>, it equals n<\/jats:italic> + 1 for t<\/jats:italic>(1)<\/jats:sup> \u2a7d t<\/jats:italic>(2)<\/jats:sup> and d<\/jats:italic>t<\/jats:italic><\/jats:sub>, = n<\/jats:italic> for t<\/jats:italic> \u2a7e t<\/jats:italic>(2)<\/jats:sup>. We also show that the radius of Q<\/jats:italic>t<\/jats:italic><\/jats:sub>, is first finite for t<\/jats:italic> = t<\/jats:italic>(1)<\/jats:sup>, when it assumes the value n<\/jats:italic>. These results are deduced from detailed theorems concerning the diameter and radius of the almost surely unique largest component of Q<\/jats:italic>t<\/jats:italic><\/jats:sub>, for t<\/jats:italic> = \u03a9(M<\/jats:italic>). \u00a9 1994 John Wiley & Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240050503","type":"journal-article","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T21:24:52Z","timestamp":1180733092000},"page":"627-648","source":"Crossref","is-referenced-by-count":8,"title":["On the diameter and radius of randon subgraphs of the cube"],"prefix":"10.1002","volume":"5","author":[{"given":"B.","family":"Bollob\u00e1s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Kohayakawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"\u0141uczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579276","article-title":"Largest random component of a k\u2010cube","volume":"2","author":"Ajtai M.","year":"1982","journal-title":"Combinastorica"},{"key":"e_1_2_1_3_2","first-page":"xvi + 447","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"1985"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010107"},{"key":"e_1_2_1_5_2","unstructured":"B.Bollob\u00e1s andY.Kohayakawa On Richardson's model on the Hypercube manuscript."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030106"},{"key":"e_1_2_1_7_2","unstructured":"B.Bollob\u00e1s Y.Kohayakawa andT.\u0141uczak On the evolution of random Boolean functions inExtremal Problems for Finite Sets P. Frankl Z. F\u00fcredi G. Katona D. Mikl\u00f3s Eds. 1994 pp.137\u2013156."},{"key":"e_1_2_1_8_2","unstructured":"B.Bollob\u00e1s Y.Kohayakawa andT.\u0141uczak Connectivity properties of random subgraphs of the cuibe to appear."},{"key":"e_1_2_1_9_2","first-page":"710","article-title":"On extremen metric characteristics of a random graph I. Asymptotic estimates","volume":"19","author":"Burtin Yu. D.","year":"1974","journal-title":"Math. Notes"},{"key":"e_1_2_1_10_2","first-page":"83","article-title":"On extreme metric characteristics of a random graph. II. Limit distributions","volume":"20","author":"Burtin Yu. D.","year":"1975","journal-title":"Math. Notes"},{"key":"e_1_2_1_11_2","series-title":"Annals of Discrete Mathematics 33","first-page":"17","volume-title":"Random Graphs '85","author":"Dyer M. E.","year":"1987"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005440"},{"key":"e_1_2_1_13_2","first-page":"42","article-title":"Maximum matchings and connected components of random subgraphs of the n\u2010cube (in Russian","volume":"48","author":"Kostochka A. V.","year":"1989","journal-title":"Methods Discrete Anal. Study Boolean Function Graphs"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010304"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70621-6"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040207"},{"key":"e_1_2_1_17_2","first-page":"505","volume-title":"Topics in Combinatorics and Graphs Theory, Oberwolfach 1990","author":"Mahrhold K.","year":"1990"},{"key":"e_1_2_1_18_2","first-page":"91","article-title":"Metric properties of almost all Boolean functions (in Russian)","volume":"10","author":"Sapozhenko A. A.","year":"1967","journal-title":"Diskretny Anal."},{"key":"e_1_2_1_19_2","unstructured":"A. A.SapozhenkoandK.Weber On the diameter of random subgraphs of then\u2010cube inContemporary Methods in Graph Theory R. Bodendiek Ed. Wissenschaftsverlag 1990 pp.507\u2013524."},{"key":"e_1_2_1_20_2","first-page":"111","article-title":"Geometric structure of random Boolean functions (in Russina)","volume":"35","author":"Toman E.","year":"1979","journal-title":"Problemy Kibernet."}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240050503","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240050503","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T03:41:09Z","timestamp":1698118869000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240050503"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1002\/rsa.3240050503"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240050503","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}