Status
On this page
Status
Topics
Status
On this page
Status
Topics
If is a random graph on vertices, including each edge with probability , then almost surely contains a copy of (the -dimensional hypercube with vertices and many edges).
Source: erdosproblems.com/578
An accepted solution exists. The statement is true.
Proved, on the site's account and the publisher's abstract of Riordan's paper: the site labels the problem PROVED, its label for a question answered in the affirmative, and credits the solution to Riordan [Ri00], noting that he proved it for every edge probability above and that the count of -cubes is asymptotically normal; the abstract of Combin. Probab. Comput. 9 (2000), no. 2, 125--148 (refereed), as deposited in the publisher's Crossref record, states that for a random graph on vertices with edges selected independently with a fixed probability , "as , almost surely has a spanning subgraph isomorphic to" the -dimensional hypercube , answering a question of Bollobás. The article's text is not held (routes below): the theorem's number and page, its exact quantifiers and its proof were not read, and this page rests on an abstract identified as such and on the site's acceptance. No source read here attests Riordan's theorem itself; Chung's survey, written before it, attests the conjecture and the earlier partial result of Alon and Füredi (edge density above ). The community database records the problem as proved. The label is kept on that evidence, named for what it is. The claim page Riordan 2000 records the result as accepted on the refereed venue and the site's acceptance, and the frontmatter standing is derived from it.