Wiki
Wiki

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

Updated


Claim. The Theorem (p. 259) of J. W. Moon, Disjoint triangles in chromatic graphs, Math. Mag. 39 (1966), no. 5, 259--261. Write μ(Gn)\mu(G_n) for the largest number of vertex-disjoint monochromatic triangles in a two-coloring GnG_n of the edges of KnK_n. Then [13n]−1≤μ(Gn)≤[13n][\tfrac13n]-1\le\mu(G_n)\le[\tfrac13n] for every GnG_n, and μ(Gn)=[13n]\mu(G_n)=[\tfrac13n] when n≡2(mod3)n\equiv2\pmod3 and n≥8n\ge8. The closing remark (p. 261) says that the lower bound is attained whenever n≥3n\ge3 and the second part does not apply, and prints no example. In the leftover count of Problem 1015, where f(n,3)f(n,3) is the maximum of n−3μ(Gn)n-3\mu(G_n), this gives f(n,3)≤4f(n,3)\le4 for every nn other than 55 (at most 33 for n≡0n\equiv0 and 44 for n≡1(mod3)n\equiv1\pmod3 by the first part, and 22 for n≡2(mod3)n\equiv2\pmod3, n≥8n\ge8, by the second), and f(n,3)=2f(n,3)=2 for n≡2(mod3)n\equiv2\pmod3, n≥8n\ge8. Math. Mag. 39, no. 5, is the November--December issue, so the page's day is a placeholder.

Covers. The case t=3t=3, f(3)=4f(3)=4, the site's value. The upper bound is Moon's theorem. Moon leaves to the reader the colorings that attain 44 for n≡1(mod3)n\equiv1\pmod3; the k=3k=3 case of the Figure 6 coloring of Burr, Erdős and Spencer (1975), their claim page, supplies them. Nothing for t≥4t\ge4 or for the two closing questions.

Depends on. Nothing in this wiki; the theorem rests on the paper's own case analysis of K8K_8 and the fact that every two-coloring of K6K_6 has a monochromatic triangle.

Acceptance. Refereed journal publication in Mathematics Magazine 39 (1966), no. 5, 259--261, which is the refereed evidence. The site's label SOLVED rests on Burr, Erdős and Spencer, so the curator's credit of f(3)=4f(3)=4 to Moon is not listed as reviewed. The proof (pp. 259--261) is followed on the library's result page, with the claims about its Figures 2--4 taken as printed; nothing here is independently reviewed.