Problem 746

Is it true that, almost surely, a random graph on $n$ vertices with $\geq (\tfrac{1}{2}+\epsilon)n\log n$ edges is Hamiltonian?

Source: erdosproblems.com/746

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The statement follows from either of two results: Korshunov's theorem that almost all graphs with $n$ labeled vertices and $k$ edges are Hamiltonian if and only if $k=\tfrac12n(\log n+\log\log n+\varphi(n))$ with $\varphi(n)\to\infty$ (announced in Dokl. Akad. Nauk SSSR 228 (1976), 529--532, in the mathnet.ru copy, no file held; the 1977 paper [Ko77], not held, gave by the author's own account a part of the proof, for $k>6n\log n$ ; the author's complete proof is Theorem 1, p. 171, of his 1985 paper, no file held, paged at Korshunov 1985, Theorem 1), and Komlós and Szemerédi's limit law [KoSz83] (Discrete Math. 43 (1983), 55--63, refereed; Theorem 1, p. 56, paged at Komlós and Szemerédi 1983, Theorem 1): with $\tfrac12n\log n+\tfrac12n\log\log n+c_nn$ edges the probability of a Hamiltonian cycle tends to $0$ , $e^{-e^{-2c}}$ or $1$ as $c_n\to-\infty$ , $c_n\to c$ or $c_n\to\infty$ . Since $(\tfrac12+\epsilon)n\log n$ exceeds $\tfrac12n(\log n+\log\log n)+\omega n$ for every fixed $\omega$ once $n$ is large, either result gives the statement. Pósa's earlier theorem [Po76] (Theorem 3, p. 364: $[c_1n\log n]$ edges for a sufficiently large constant $c_1$ , which the paper does not specify) settles the statement only for $\epsilon\ge c_1-\tfrac12$ , recorded as the partial claim Pósa. The two status-defining papers are attested by Erdős himself in two of his own published problem papers ([Er81], Part VIII, and [Er82e], §1, quoted below), by the site, and by Frieze's annotated bibliography; Korshunov's theorem is taken as printed in the author's 1985 paper, the 1977 text being not held, while [Po76] is read in full and [KoSz83] at its theorems (the library holds no file of either). The two full results are recorded on the claim pages Korshunov and Komlós and Szemerédi, from which the frontmatter standing is derived.

ErRe66: Erdős, P. and Rényi, A., On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar. 17 (1966), 359--368, doi:10.1007/BF01894879 (received 7 September 1965). Theorem 1, p. 360. Library home: Erdős and Rényi 1966 (a Rényi archive scan); paged at Erdős and Rényi 1966, Theorem 1.
Po76: Pósa, L., Hamiltonian circuits in random graphs. Discrete Math. 14 (1976), no. 4, 359--364, doi:10.1016/0012-365X(76)90068-6 (received 26 October 1974). Theorem 3, p. 364. Library home: Pósa 1976 (from the publisher's open-archive scan, all six pages; no file is held; the card carries the row for this problem); paged at Pósa 1976, Theorem 3 and, for the rotation method, at Pósa 1976, Lemma 1.
Ko77: Koršunov, A. D., Solution of a problem of P. Erdős and A. Rényi on Hamiltonian cycles in nonoriented graphs. Diskret. Analiz Vyp. 31 (1977), 17--56, 90 (in Russian); the site's key for the result. The 1977 paper is not held; no online copy located; by the author's account below it gave a part of the proof, for $k>6n\log n$ . The author's complete proof, in English, Korshunov, A new version of the solution of a problem of Erdős and Rényi on Hamiltonian cycles in undirected graphs, Annals of Discrete Mathematics 28 (Random Graphs '83, North-Holland Math. Stud. 118) (1985), 171--180, doi:10.1016/S0304-0208(08)73618-1 (no file held): Theorem 1, p. 171; Theorem 2, p. 172; the comment on the earlier papers, p. 179. Library home: Korshunov 1985 (the theorems, lemmas and comment as printed, the proofs for structure; the card carries the row for this problem); paged at Korshunov 1985, Theorem 1. The 1985 paper is a new text, not a translation of the 1977 paper: it presents "a new proof" and its comment (p. 179) says the 1977 paper gave "a part of proof (for $k>6n\log n$ )" and that "The proof presented above is different from the previous ones". The author's announcement of the result, A. D. Korshunov, Solution of a problem of Erdős and Rényi on Hamiltonian cycles in nonoriented graphs, Dokl. Akad. Nauk SSSR 228 (1976), no. 3, 529--532 (in Russian; presented 22 January 1976; English translation Soviet Math. Dokl. 17 (1976), 760--764, per Frieze), is in the mathnet.ru copy the site's discussion thread links (no file held). Library home of the announcement: Korshunov 1976 (the card carries the row for this problem).
KoSz83: Komlós, János and Szemerédi, Endre, Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math. 43 (1983), no. 1, 55--63, doi:10.1016/0012-365X(83)90021-3 (Crossref record: open-archive license dated 2013; received 13 October 1977, revised 1 December 1980). Theorem 1, p. 56; Theorem 2, p. 57. Library home: Komlós and Szemerédi 1983 (from the publisher's open-archive scan, no file held; pp. 55--57 clause by clause, pp. 58--63 for structure; the card carries the row for this problem); paged at Komlós and Szemerédi 1983, Theorem 1 and Komlós and Szemerédi 1983, Theorem 2.
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; item 5, p. 98. Library home: Erdős 1971 (a scan); the item is paged at Erdős 1971, Item 5 (p. 98).
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; Part VIII, "Two Problems on Random Graphs and Hypergraphs", p. 16 of the retyped copy, which has its own pagination. Library home: Erdős 1981.
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79; §1, p. 69. Library home: Erdős 1982.
ErRe60: Erdős, P. and Rényi, A., On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17--61 (received 28 December 1959). Not cited by the site; the paper that Korshunov's announcement (its reference 2), the reference list of [Er82e] §1 and Frieze's bibliography give as the source of the Erdős--Rényi question, which it poses on p. 60 (§ 10, "Other open problems") as the order of magnitude of $N(n)$ for a Hamilton-line. Library home: Erdős and Rényi 1960 (the Rényi archive's scan, its item 1960-10; the card carries the row for this problem).
Fr21: Frieze, A., Hamilton cycles in random graphs: a bibliography (dated 4 July 2021; 42 pages; an annotated bibliography, not a refereed paper). Cited for its Section 2.1 (p. 2) and its entries [82], [83], [151]--[153] and [190]; not held in the library.

Problem 746

Status

Proof claims

Discussion