Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be the smallest such that if the edges of are -coloured then there is a set of vertices which does not contain a copy of in at least one of the colours. Prove that there is a constant such that
Source: erdosproblems.com/129
A full solution has been claimed but not yet accepted. The statement is false.
Open on the site, which explains the label by the ambiguity of the original source: the OPEN describes the question Erdős intended, which the site cannot identify, not the question the site prints. The Statement asks for a constant with and fails for every , and the site says so: its commentary credits Girão with the observation that a random coloring gives for some . Take a uniformly random red-blue coloring of and a fixed set of vertices: contains edge-disjoint triangles, each monochromatic red with probability independently, so the probability that has no red triangle is at most , and the same for blue; summing over the sets and the two colors, the expected number of -sets missing a triangle in some color is at most once for a suitable absolute , so some coloring has every -set containing both a red and a blue triangle, and . The thread's Steiner-triple-system version extends the argument to an exponential lower bound for every , and no exceeds an exponential in for large . The failure holds for every and every large , not only at boundary values, and the bound is Erdős's own print in [Er97b], so the Statement is judged as printed. The claim page Girão's observation records the disproof and its postings as a pending claim: the curator wrote its only posting and keeps the problem OPEN, so there is no independent review. The frontmatter standing is claimed, through that full claim.