Problem 900

There is a function $f:(1/2,\infty)\to \mathbb{R}$ such that $f(c)\to 0$ as $c\to 1/2$ and $f(c)\to 1$ as $c\to \infty$ and every random graph with $n$ vertices and $cn$ edges has (with high probability) a path of length at least $f(c)n$ .

Source: erdosproblems.com/900

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The status-defining source is Theorem 2 of Ajtai, Komlós and Szemerédi, The longest path in a random graph, Combinatorica 1 (1981), 1--12 (refereed; the version of record): "The random (undirected) graph $G'_{n,\beta n}$ with $n$ vertices and $\beta n$ edges, $\beta>1/2$ , almost surely contains a path of length $cn$ , $c=c(\beta)$ ", together with its Corollary, that for any prescribed path fraction $c<1$ the exponential-rate bound holds for a large enough edge coefficient, its transfer sentence to the undirected model and its Remark 2 relating the fixed-edge and independent-edge models. The existence of a function $f$ with the two limits follows from these three statements by the deduction written under Status support, this page's own and not the paper's, which defines no single $f$ . Acceptance evidence: refereed publication; Erdős's own report of the proof in his 1982 collection ("All these conjectures were proved by Ajtai, Komlós and Szemerédi"); the site; the community database. Read depth: claims checked for Theorem 2, the Exponential rate, the Corollary and Remarks 1 and 2; the proofs (pp. 4--12) were not read. The result and its acceptance evidence are recorded on the claim page Ajtai--Komlós--Szemerédi, from which the frontmatter standing is derived.

AKS81: Ajtai, Miklós and Komlós, János and Szemerédi, Endre, The longest path in a random graph. Combinatorica 1 (1981), no. 1, 1--12, doi:10.1007/BF02579172 (Crossref; issued March 1981; received 12 September 1979). Theorem 2, the Exponential rate, the Corollary and Remark 1, printed p. 2; Remark 2, pp. 2--3. Library home: Ajtai and Szemerédi 1981; paged at Ajtai and Szemerédi 1981, Theorem 2 (p. 2).
Er78: Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29--40; Section 3, printed p. 32. Library home: Erdős 1978.
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, printed p. 69. Library home: Erdős 1982.
Er75: Erdős, P., Problems and results on finite and infinite graphs. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague (1975), 183--192; Section VII, printed p. 188. Not a site key; [AKS81]'s reference [4] for the conjecture. Library home: Erdős 1975, whose read status and Bears on row for this problem record the passage at claims checked.
FdlV79: Fernandez de la Vega, W., Sur la plus grande longueur des chemins élémentaires de graphes aléatoires. Preprint, Laboratoire d'informatique pour les Sciences de l'Homme, C.N.R.S. (1979), as [AKS81]'s reference [3] gives it. The theorem [AKS81] quote in Remark 1: for $p=1-e^{-d/n}$ , $G_{n,p}$ almost surely contains a path of length $(1-2.21/d)n$ . The journal paper of the same year on the subject is Fernandez de la Vega, W., Long paths in random graphs. Studia Sci. Math. Hungar. 14 (1979), 335--340 (zbMATH Zbl 0444.05052), which [AKS81] do not cite. Neither is held.

Problem 900

Status

Proof claims

Discussion