Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is it true that if the edges of are 2-coloured then there are at most many edges which do not occur in a monochromatic triangle?
Is it true that if the edges of are 2-coloured then there are at most many edges which do not occur in a monochromatic triangle for large ?
Source: erdosproblems.com/639
An accepted solution exists. The statement is true.
The site shows PROVED (LEAN), a label that describes the corrected Statement; the suffix is a catalog label explained under Formalization, with no local kernel credit claimed. The corrected Statement is proved: Theorem 1.1 of Keevash and Sudakov (J. Combin. Theory Ser. B 90 (2004), 41--53, refereed) determines for every , and in particular for all . The site credits the large- case earlier to Erdős, Rousseau and Schelp (unpublished; stated as proved, without proof, in item 10 of [Er97d]) and to Alon's deduction from Pyber's clique-covering theorem, [Py86] Theorem 1 (p. 393; paged at Theorem 1), the deduction itself being reported by [KeSu04] and not printed in [Py86]. The claim page Keevash and Sudakov 2003 records the theorem, its postings and its acceptance evidence, and carries the Lean file behind the site's suffix as a formalization link; the frontmatter standing derives from it. The site's wording, which drops "for large ", is false at by the same theorem, as the Notes record. Read depth: claims checked for Theorem 1.1 and Proposition 2.1; the proof is checked for structure only.
The site's wording quantifies over every and is false for . The smallest failure is : a -coloring of that is not monochromatic has no monochromatic triangle, so all three edges lie in none, and . For every , Theorem 1.1 (Keevash and Sudakov 2004) of Keevash and Sudakov [KeSu04] (p. 42) gives the maximum number of such edges exactly: for , for and for . So the wording fails at (, , and edges against , , and ) and holds for every other ( trivially); the site's commentary prints the same three values. The change appends Erdős's words "for large ", that is, for every beyond some threshold; nothing else changes. The evidence is Erdős's own statement in [Er97d], item 10, printed p. 84 (item 10): "Rousseau, Schelp and I proved that if we color the edges of by two colors then the number of edges which do not occur in a monochromatic triangle is at most for large ." The defect is the site's: its only source key states the bound for large , and the site's wording drops the qualifier. The range of Theorem 1.1 is a theorem's range and is not used as the form. The one published result about the site's wording is the small- part of the same Theorem 1.1 (Keevash and Sudakov, J. Combin. Theory Ser. B 90 (2004), 41--53, doi:10.1016/S0095-8956(03)00075-3), which refutes it at ; it is credited here and counts for nothing. The site's label describes the corrected Statement, and the standing judges it.