Wiki
Wiki

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

Updated


Claim. Problem 129 asks, with R(n;k,r)R(n;k,r) the least NN such that every rr-coloring of the edges of KNK_N has a set of nn vertices missing KkK_k in some color, for a constant C=C(r)>1C=C(r)>1 with R(n;3,r)<CnR(n;3,r)<C^{\sqrt n}. Girão's observation, written into the site's commentary by its curator, is that this is false as written, because R(n;3,2)≥CnR(n;3,2)\ge C^n for an absolute constant C>1C>1: color the edges of KNK_N red or blue independently and uniformly at random. Any nn vertices span ≫n2\gg n^2 pairwise edge-disjoint triangles, each red with probability 1/81/8 independently of the others, so the probability that the set has no red triangle is at most (7/8)cn2(7/8)^{cn^2}, and the same for blue; a union bound over the (Nn)≤(eN/n)n\binom Nn\le(eN/n)^n sets and the two colors leaves a coloring in which every nn-set contains a triangle of each color once N≤CnN\le C^n. Hence R(n;3,2)≥CnR(n;3,2)\ge C^n, and no C(2)nC(2)^{\sqrt n} exceeds an exponential in nn for large nn, which already refutes the statement. The site credits Girão with this case r=2r=2 and no more. The extension to every rr, the same argument with probability r−3r^{-3} for each color and a union bound over the rr colors, is not Girão's: the thread's comment of 28 February 2026 runs it for every rr through Steiner triple systems, in a construction its poster attributes to GPT-5.2, and the problem page's Current assessment recomputes the union bound with explicit constants for r=2r=2 and for every r≥3r\ge3, an authored check that warrants nothing here.

Scope. Full: the problem page's Statement is the site's wording, and the disproof settles it. The disproof says nothing about the question Erdős intended: the site's commentary and its information box record that the original source is ambiguous and that no intended form is known, and Erdős's 1997 item 2 states the conjecture in the site's form and no other. The site's label stays OPEN for that unidentified question, not for the question the site prints.

Depends on. Nothing in this wiki; the argument is the site's own first-moment bound.

Standing. Claimed, not accepted. The site's curator, T. F. Bloom, records the observation in the problem's commentary, credits Girão by name and in the page's acknowledgment line, and on 28 February 2026 replied in the thread that the Steiner-triple-system argument posted that day is the construction already discussed in the remarks; but Bloom keeps the problem's label OPEN, for the question Bloom takes Erdős to have intended, and the commentary Bloom wrote is the observation's only posting: Girão posted nothing on the site, the proof-claim tab is empty, and the thread, linked above as the problem's discussion and not as a posting of Girão's, holds a third party's restatement and the curator's reply. The curator therefore published the claim rather than reviewing a claim published by another, Bloom's credit is not an independent review, and no reviewed evidence is listed. No paper states the disproof and nothing is refereed. A refereed note, or a review by someone independent of the claimant, would be needed to accept it.

Postings and dating. The site's commentary carries no date and the page shows no last-edited date. As of 2026-10-07 the site's history view shows the remark already present in its earliest listed revision, of 20 October 2025, and that date names this page; the thread's comment of 24 August 2025, whose author writes that the problem still puzzles them, suggests the remark is older. The thread comment of 28 February 2026 and the curator's reply of the same day are the dated confirmations.