A343606 -id:A343606 - cp's OEIS frontend

A343607 Minimal number of colors required for an edge-coloring of the complete graph K_n with no monochromatic triangle.

0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Offset: 0

M. F. Hasler, Jun 25 2021

The complete graph K_n has n(n-1)/2 edges (i,j), 1 <= i < j <= n, connecting the n vertices to each other. A triangle is a subgraph of edges {(i,j), (i,k), (j,k)} with i < j < k; monochromatic means that all edges have the same color.
The edge-colorings are obviously not required to be proper, i.e., adjacent edges may have the same color.
Corollary 3 of Cummings et al. (2013) gives a formula for an upper bound on M_3(K_3,n), the minimal number of monochromatic triangles in a 3-colored K_n, which is positive iff n >= 11 (which, if tight, would mean a(n) > 3 for n > 10). However, the paper only claims that the bound is tight for all sufficiently large n. We have indeed 3-edge-colorings up to n = 16 with no monochromatic triangle. It is known that a(n) > 3 iff n = 17, cf. A343606.
Rows of A343606 give the lexicographic earliest edge-colorings of K_n without monochromatic triangles using the minimum number of colors a(n).

			For n = 0 and n = 1, the empty graph K_0 and the singleton graph K_1 don't have any edge, so zero colors are needed.
For n = 2 we have one edge, so one color is needed.
For n = 3 we have a triangle, so we need a second color for the third edge.
For n = 4 (square + diagonals) and n = 5 (pentagon + diagonals forming a pentagram) two colors are still enough: one can use one color for the "circumference", i.e., edges (i,i+1), and the other color for the diagonals.
For n >= 6, a third color is needed.

James Cummings, Daniel Král', Florian Pfender, Konrad Sperfeld, Andrew Treglown and Michael Young, Monochromatic triangles in three-coloured graphs, Journal of Combinatorial Theory B 103 no. 4 (2013) 489-503 (also: arXiv:1206.1987).
Wikipedia, Monochromatic triangle.

Cf. A343606 (gives corresponding colorings), A000217 (triangular numbers - row lengths of A343606), A003323.

A343607(n)=if(n>1, vecmax(color(n))+1, 0) \\ using the helper function:
{M343607=List([[]]); color(n, i=matrix(n,n,r,c,r+c--*c--/2), C, k)= C|| C = if(#M343607 >= n, M343607[n], n>2, color(n-1,i)); k|| k=if(n>3, vecmax(C)+1, n-1); C=Vec(C, n*(n-1)/2); my(bad(C)= for(a=1,n-2, my(c=C[i[a,n]]); for(b=a+1, n-1, C[i[a,b]] !=c || C[i[b,n]] !=c || return( i[b,n] ))), C0=C, j); while(j=bad(C), until(j-- < i[1,n], if(C[j]++ < k, while(j<#C, C[j++]=0); next(2))); while(C[j]++ >= k, C[j]=0; j--); C=Vec(color(n-1,i,C[1..-n]),#C); if(C[1..n] != C0[1..n], k++; C=C0)); #M343607= 13. Changing 1..n to 1..2-2*n is much faster but yields suboptimal solution for n >= 12 (using 4 instead of 3 required colors).

a(n) = max { A343606(n,k)+1; k >= 1 } U { 0 }.

a(n) = min {k >= 0; A003323(k) > n}. - Pontus von Brömssen, Aug 01 2021

More terms from Pontus von Brömssen, Jul 21 2021

A343626 Decimal expansion of the Prime Zeta modulo function P_{3,1}(6) = Sum 1/p^6 over primes p == 1 (mod 3).

Original entry on oeis.org

0, 0, 0, 0, 0, 8, 7, 3, 0, 0, 1, 1, 0, 2, 3, 1, 9, 8, 1, 6, 7, 0, 1, 2, 0, 4, 2, 7, 7, 9, 1, 4, 5, 2, 3, 1, 9, 4, 9, 5, 6, 1, 0, 7, 9, 7, 6, 4, 5, 3, 9, 1, 8, 3, 6, 9, 8, 9, 7, 1, 7, 7, 1, 3, 8, 1, 3, 6, 2, 9, 8, 3, 2, 9, 4, 5, 3, 8, 7, 6, 4, 9, 6, 9, 9, 3, 6, 1, 8, 5, 8, 6, 2, 3, 2, 9, 3, 3, 4, 5

Offset: 0

M. F. Hasler, Apr 23 2021

The Prime Zeta modulo function at 6 for primes of the form 3k+1 is Sum_{primes in A002476} 1/p^6 = 1/7^6 + 1/13^6 + 1/19^6 + 1/31^6 + ...

The complementary Sum_{primes in A003627} 1/p^6 is given by P_{3,2}(6) = A085966 - 1/3^6 - (this value here) = 0.015689614727130461563527666... = A343606.

			P_{3,1}(6) = 8.7300110231981670120427791452319495610797645391837...*10^-8

R. J. Mathar, Table of Dirichlet L-series and Prime Zeta Modulo Functions for Small Moduli, arXiv:1008.2547 [math.NT], 2010-2015, p.21.
OEIS index to entries related to the (prime) zeta function.

Cf. A175645, A343624 - A343629 (P_{3,1}(3..9): same for 1/p^n, n=3..9), A343606 (P_{3,2}(6): same for p==2 (mod 3)), A086036 (P_{4,1}(6): same for p==1 (mod 4)).

Cf. A085966 (PrimeZeta(6)), A002476 (primes of the form 3k+1).

With[{s=6}, Do[Print[N[1/2 * Sum[(MoebiusMu[2*n + 1]/(2*n + 1)) * Log[(Zeta[s + 2*n*s]*(Zeta[s + 2*n*s, 1/6] - Zeta[s + 2*n*s, 5/6])) / ((1 + 2^(s + 2*n*s))*(1 + 3^(s + 2*n*s)) * Zeta[2*(1 + 2*n)*s])], {n, 0, m}], 120]], {m, 100, 500, 100}]] (* adopted from Vaclav Kotesovec's code in A175645 *)

s=0; forprimestep(p=1, 1e8, 3, s+=1./p^6); s \\ For illustration: primes up to 10^N give 5N+2 (= 42 for N=8) correct digits.

A343626_upto(N=100)={localprec(N+5);digits((PrimeZeta31(6)+1)\.1^N)[^1]} \\ cf. A175644 for PrimeZeta31

cp's OEIS Frontend

A343607 Minimal number of colors required for an edge-coloring of the complete graph K_n with no monochromatic triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A343626 Decimal expansion of the Prime Zeta modulo function P_{3,1}(6) = Sum 1/p^6 over primes p == 1 (mod 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI