A343608 a(n) = [n/5]*[n/5 - 1]*(3n - 10[n/5 + 1])/6, where [.] = floor: upper bound for minimum number of monochromatic triangles in a 3-edge-colored complete graph K_n.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 8, 11, 14, 17, 20, 26, 32, 38, 44, 50, 60, 70, 80, 90, 100, 115, 130, 145, 160, 175, 196, 217, 238, 259, 280, 308, 336, 364, 392, 420, 456, 492, 528, 564, 600, 645, 690, 735, 780, 825, 880, 935, 990, 1045, 1100, 1166

Offset: 0

Author

M. F. Hasler, Jun 25 2021

Keywords

• nonn

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

Examples

			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.
		

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.

Programs

PARI

apply( {A343608(n)=n\5*(n\5-1)*(n-10+n%5*2)/6}, [1..55])

Formula

a(n) = A144679(n-11) = r*A000292(q-1) + (5-r)*A000292(q-2) = q(q - 1)(n + 2r - 10)/6, where A000292(q-2) = binomial(q,3), r = n mod 5 and q = (n-r)/5, for sufficiently large n, according to Cummings et al., Corollary 3.

Extensions

Definition corrected following an observation by Rob Pratt, Jun 28 2021