Problem 76

Is it true that in any $2$ -colouring of the edges of $K_n$ there must exist at least

(1+o(1))\frac{n^2}{12}

many edge-disjoint monochromatic triangles?

Source: erdosproblems.com/76

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. Theorem 1.2 of Gruslys and Letzter, arXiv:2008.05311v2 (14 August 2020), states exactly the question's conclusion: "Every $2$ -coloured $K_n$ contains a collection of $n^2/12+o(n^2)$ pairwise edge-disjoint monochromatic triangles." The status-defining source is an arXiv paper; the site's curator accepted it, recording in the commentary that the answer is yes by Gruslys and Letzter [GrLe20], and that acceptance is the label's evidence; on it the claim page records the result as accepted, with no refereed version, and the frontmatter standing is derived from it. The proof's two ingredients external to the paper, Theorem 2.11 (proved in a companion preprint) and the computer-search certificates behind Lemma 2.8, are not held. Read depth: claims checked for Theorem 1.2 and the statements around it; the proof is not reviewed here.

GrLe20: Gruslys, V. and Letzter, S., Monochromatic triangle packings in red-blue graphs. arXiv:2008.05311 (v1 12 August 2020; v2 14 August 2020, the version cited, 37 pages). Conjecture 1.1 and footnote 1, p. 1; Theorems 1.2 and 1.3, p. 2; Theorem 2.3, p. 4; Lemma 2.8, p. 6; Theorem 2.11, p. 7; Section 8, p. 30. Library home: Gruslys and Letzter 2020.
GrLe20b: Gruslys, V. and Letzter, S., Fractional triangle decompositions in almost complete graphs. arXiv:2008.05313 (v2 14 August 2020, 21 pages); the companion paper proving [GrLe20]'s Theorem 2.11. Not held.
Er95: Erdős, P., Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas 2 (1995), 165--186; item 8 of Part II, p. 11 of the author typescript. Library home: Erdős 1995.
Er97d: Erdős, P., Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81--85; item 14, p. 84, the resolving paper's "Problem 14". Library home: Erdős 1997 (the item is paged on Erdős 1997, Item 14 (p. 84)). Keevash and Sudakov's 2004 paper says of it that Erdős "conjectured that here also it is best to take one of the colors to be a complete bipartite graph, which will give $n^2/12+o(n^2)$ edge disjoint monochromatic triangles" (J. Combin. Theory Ser. B 90 (2004), p. 42; the paper is a source of Problem 639).
Va99: Some of Paul's favorite problems, booklet (Budapest, July 1999); item 3.54. Library home: Various 1999.
EFGJL01: Erdős, P., Faudree, R. J., Gould, R. J., Jacobson, M. S. and Lehel, J., Edge disjoint monochromatic triangles in 2-colored graphs. Discrete Math. 231 (2001), 135--141. The bound $3n^2/55+o(n^2)$ and the source OEIS A060407 names; not held, quoted second-hand from [GrLe20] p. 1.
KeSu04b: Keevash, P. and Sudakov, B., Packing triangles in a graph and its complement. J. Graph Theory 47 (2004), 203--216. The bound $n^2/12.89+o(n^2)$ ; not held, quoted second-hand from [GrLe20] p. 1.
HaRö01: Haxell, P. and Rödl, V., Integer and fractional packings in dense graphs. Combinatorica 21 (2001), 13--38. The transference the proof uses ([GrLe20] Theorem 2.1); not held.
OEIS: Sequence A060407, The On-Line Encyclopedia of Integer Sequences, "Maximal number of pairwise edge-disjoint monochromatic $K_3$ 's in a $K_n$ for any 2-coloring of the edges of $K_n$ ", values $0,0,0,1,2,2,3,4,6$ for $n=3,\ldots,11$ , citing [EFGJL01] (record accessed).

Problem 76

Status

Proof claims

Discussion