OFFSET
0,13
COMMENTS
Consider the complete graph K_n whose n(n-1)/2 edges are colored with 3 distinct colors as to minimize the number of monochromatic triangles, i.e., subgraphs isomorphic to K_3 having all edges of the same color.
Cummings et al. show that this minimum number of monochromatic triangles M_3(K_3,n) is given by a(n) for sufficiently large n.
For the actual minimum numbers, we currently only know M_3(K_3,n) = 0 for n < 17, and M_3(K_3, 17) = 5.
Known examples for n>17, where the actual minimum value is below this upper bound: M_3(K_3, 18) <= 10 < 14 = a(18), M_3(K_3, 19) <= 15 < 17 = a(19), M_3(K_3, 21) <= 25 < 26 = a(21). For n>21, the current best known minimum values match the upper bound. - Dmitry Kamenetsky, Jul 01 2021
LINKS
James Cummings, Daniel Král', Florian Pfender, Konrad Sperfeld, Andrew Treglown, Michael Young, Monochromatic triangles in three-coloured graphs, Journal of Combinatorial Theory B 103 no. 4 (2013) 489-503 (also: arXiv:1206.1987).
Al Zimmermann, Programming Contest: Monochromatic Triangles, June 2021.
FORMULA
EXAMPLE
a(17) = [17/5]*[17/5 - 1]*(3*17 - 10[17/5 + 1])/6 = 3*2*11/6 = 11, which is the number of monochromatic triangles obtained by coloring the edges of the complete graph K_17 as follows: edges (i,j) with mod(j-i,5) in {1,4} get color 1, edges (i,j) with mod(j-i,5) in {2,3} get color 2, and edges (i,j) with mod(j-i,5) = 0 get color 3. The minimum number of monochromatic triangles in an edge-coloring of K_17 with 3 colors turns out to be 5 <= 11.
PROG
(PARI) apply( {A343608(n)=n\5*(n\5-1)*(n-10+n%5*2)/6}, [1..55])
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Jun 25 2021
EXTENSIONS
Definition corrected following an observation by Rob Pratt, Jun 28 2021
STATUS
approved