|
%I #35 Jul 01 2021 23:45:25
%S 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,
%T 80,90,100,115,130,145,160,175,196,217,238,259,280,308,336,364,392,
%U 420,456,492,528,564,600,645,690,735,780,825,880,935,990,1045,1100,1166
%N 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.
%C 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.
%C 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.
%C 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.
%C 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
%H James Cummings, Daniel Král', Florian Pfender, Konrad Sperfeld, Andrew Treglown, Michael Young, <a href="https://doi.org/10.1016/j.jctb.2013.05.002">Monochromatic triangles in three-coloured graphs</a>, Journal of Combinatorial Theory B 103 no. 4 (2013) 489-503 (also: arXiv:1206.1987).
%H Al Zimmermann, <a href="http://azspcs.com/Contest/Clique">Programming Contest: Monochromatic Triangles</a>, June 2021.
%F 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.
%e 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.
%o (PARI) apply( {A343608(n)=n\5*(n\5-1)*(n-10+n%5*2)/6}, [1..55])
%K nonn
%O 0,13
%A _M. F. Hasler_, Jun 25 2021
%E Definition corrected following an observation by _Rob Pratt_, Jun 28 2021
|
