Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Theorem 1 of Yuan, Anti-Ramsey numbers for paths (arXiv:2102.00807v3, p. 1; the title as the arXiv record gives it, where the PDF prints the singular The anti-Ramsey number for paths), states that for n≥k≥5n\ge k\ge5 and ℓ=⌊(k−1)/2⌋\ell=\lfloor(k-1)/2\rfloor,

AR(n,Pk)=max⁡{(k−22)+1, (ℓ−12)+(ℓ−1)(n−ℓ+1)+ϵ},\mathrm{AR}(n,P_k)=\max\Bigl\{\binom{k-2}{2}+1,\ \binom{\ell-1}{2}+(\ell-1)(n-\ell+1)+\epsilon\Bigr\},

with ϵ=1\epsilon=1 for odd kk and ϵ=2\epsilon=2 for even kk, where AR(n,G)\mathrm{AR}(n,G) is the largest number of colors in an edge-coloring of KnK_n with no rainbow copy of GG. This is the path question of Problem 1105 answered yes, term for term; in the 1975 parameters k=2t+3+ϵ0k=2t+3+\epsilon_0 it is Conjecture 2 of Erdős, Simonovits and Sós, whose announced proofs never appeared. The proof reduces to connected Turán numbers for paths and uses stability theorems of Füredi, Kostochka, Luo and Verstraëte, stated in Section 2 as Corollary 5 (odd k≥9k\ge9) and Corollary 6 (even k≥6k\ge6), which hold for every number of vertices, so the range is the full n≥k≥5n\ge k\ge5. The preprint qualifies these inputs itself: the Remark after Corollary 6 (p. 3) says that case (d) of Corollary 6, the equality case e(G)=h(n,k−1,ℓ−1)e(G)=h(n,k-1,\ell-1), is not proved in the two cited papers, that "We can prove this with a little more effort", and that it follows easily from the stability results of Ma and Yuan (arXiv:2010.13667); footnote 1 (p. 2) asserts, without proof, that the cited Theorem 2.3 for 22-connected graphs without long cycles extends to connected PkP_k-free graphs. The even-kk case therefore rests in part on stability inputs the preprint asserts rather than proves in the sources it cites, a gap the author declares and the acceptance below does not address.

Covers. The path half: the exact formula for all n≥k≥5n\ge k\ge5. The refereed Simonovits and Sós 1984 covers paths on at least 1313 vertices for n>ct2n>ct^2 before it, and the cycle half is the accepted Montellano-Ballesteros and Neumann-Lara 2005.

Depends on. Nothing in this wiki; the proof's inputs are the cited Turán and stability theorems, not held here.

Acceptance. Reviewed: the site's curator, T. F. Bloom, labels the problem PROVED and in the commentary says that Yuan [Yu21] has announced a proof of the path formula for all n≥k≥5n\ge k\ge5 (page last edited 29 January 2026, accessed 2026-09-18); the curator is independent of the author, and for the path half the label can rest on no other source, since Simonovits and Sós cover only n>ct2n>ct^2. The community database lists the problem as proved as of its last update, 1 February 2026; the thread (two comments of 19 January 2026) concerns a literature identification, and the proof-claim tab is empty. Not refereed: the paper is an arXiv preprint (v1 of 1 February 2021, the date the page is named by; v3 of 9 February 2021, the latest version) with no journal reference on its listing, no Crossref record and no published version among its seven citing records (2026-09-18).

Read depth. Theorem 1, the definitions and the quoted Turán inputs (pp. 1--2 of v3), and footnote 1, Corollaries 5--6 and the Remark of Section 2 (pp. 2--3), are checked; the proof is not checked. Nothing here is independent review.