|
%I #44 Mar 31 2024 19:04:21
%S 0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,1,0,1,2,0,2,1,1,1,0,0,0,
%T 0,0,0,1,0,1,2,0,2,1,1,1,0,0,0,0,1,0,0,0,0,2,0,0,1,0,1,2,0,2,1,1,1,0,
%U 0,0,0,1,0,0,0,0,2,2,0,0,0,0,1,1,0,0,1,0,1,2,0,2,1,1,1,0,0,0,0,1,0,0,0,0,2,2,0,0,0,0,1,1,2,0,0,0,0,1,1
%N Row n gives the lexicographically earliest edge coloring of the complete graph K_n with no monochromatic triangle.
%C The complete graph K_n has (n-1) + (n-2) + ... + 1 = n(n-1)/2 edges connecting the n vertices to each other. We associate a color to each edge such that there is no monochromatic triangle, i.e., no three vertices i < j < k such that the tree edges (i,j), (i,k) and (j,k) all have the same color.
%C For each n, consider the smallest possible number k of colors allowing such an edge-coloring. This table lists in row n, of length n(n-1)/2, the lexicographic earliest such coloring, i.e., the colors (between 0 and k-1) of edges AB = (1,2), AC = (1,3), BC = (2,3), ..., AZ = (1,n), ..., YZ = (n-1,n).
%C This is the lower left part (read by rows) or the upper right part (read by columns) of the symmetric n X n matrix where the element with indices (i,j) gives the color of the edge (i,j).
%C We conjecture that the rows converge to a limit in the sense that an increasingly long initial segment will always remain constant for all subsequent rows: for all k >= 0 there is n such that a(m,j) = a(n,j) for all m >= n and 1 <= j <= k.
%C Obviously, the first element a(n,1) = 0 for all n >= 2, and the first three elements will always be a(n, 1..3) = (0, 0, 1) for all n >= 3.
%C It seems that for n = 6 and n = 7, too, we have a(m,k) = a(n,k) for all m >= n and 1 <= k <= n(n-1)/2. Are there other row indices with this property? (This is of course much stronger than the requirement of convergence.)
%C Let us call min-color any solution that uses the minimum number of colors for the respective n. The restriction of any row n to the length of an earlier row m < n is always a solution for m, but not necessarily min-color: For n = 5 we have a solution using only 2 colors, but the lex earliest solutions for n >= 6 use 3 colors among the edges between the first 4 vertices. However, the lex earliest solution for n = 5, using only 2 colors, can be extended to solutions for all n >= 6. But the lex earliest solution for n = 4 cannot be extended to a min-color solution for n = 5.
%C Can one or the other of the following conjectures be (dis)proved?
%C Conjecture 1: For any n there is a min-color solution that can be extended to a min-color solution for all larger m > n?
%C Conjecture 2 (implies conjecture 1): For any n there is a min-color solution that can be restricted to a min-color solution for any smaller m < n.
%C Since Conjecture 2 does not make any assumption about the lexicographical order, it is independent of the convergence of the rows of this sequence mentioned above.
%e Rows n = 0 and n = 1 have length n(n-1)/2 = 0, since the empty graph K_0 and the singleton graph K_1 have no edges.
%e Starting with n = 2, the graph K_n has a positive number n(n-1)/2 of edges:
%e n | Coloring of edges (1,2) = AB, (1,3) = AC, (2,3) = BC, ..., (n-1,n) = YZ
%e ---+------------------------------------------------------------------------
%e 2 | 0 (The only non-diagonal element, in row/col. 2 of the color matrix.)
%e 3 | 0; 0, 1 (Rows 2 and 3 of the subdiagonal part of the color matrix.)
%e 4 | 0; 0, 1; 1, 0, 0 (Rows 2, 3 and 4 below the diagonal of that matrix.)
%e 5 | 0; 0, 1; 1, 0, 1; 1, 1, 0, 0
%e 6 | 0; 0, 1; 0, 1, 2; 0, 2, 1, 1; 1, 0, 0, 0, 0
%e 7 | 0; 0, 1; 0, 1, 2; 0, 2, 1, 1; 1, 0, 0, 0, 0; 1, 0, 0, 0, 0, 2
%e 8 | ...; 2, 0, 0, 0, 0, 1, 1 (where ... = row 7)
%e 9 | ...; 2, 0, 0, 0, 0, 1, 2; 2, 0, 0, 0, 0, 2, 1, 1
%e 10 | ...; 2, 0, 0, 0, 0, 1, 2; 2, 0, 0, 0, 1, 2, 1, 1; 2, 2, 1, 1, 0, 2, 1, 1, 0
%e 11 | ...; 2, 0, 0, 0, 1, 1, 2; 2, 0, 0, 0, 2, 2, 1, 1; 2, 2, 1, 2, 0, 2, 1, 1, 0
%e | ; 2, 2, 2, 1, 0, 2, 1, 0, 0, 1
%e The graph K_2 consists of only one edge with color 0.
%e The graph K_3 is a triangle, two edges get color 0, the third one color 1.
%e The graph K_4 is a square with its two diagonals; the edges AB, AC, BC, AD, BD and CD get colors 0, 0, 1, 1, 0 and 0, respectively.
%e The given solution for n = 5 can be extended to a solution for n = 6 by appending [0, 1, 2, 0, 2]. This solution comes lexicographically later because edges AD, BD, CD (row 4/col. 4 of the "color matrix") are colored (1, 0, 1) instead of (0, 1, 2), but uses only 2 colors for all edges not adjacent to the last vertex F.
%o (PARI) row(n)={ local(C=vector(n*(n-1)/2), k, i=matrix(n, n, i, j, if(i<j, k++)), bad()=for(a=1,n, for(b=a+1,n, k=C[i[a,b]]; for(c=b+1,n, C[i[a,c]] != k || C[i[b,c]] != k || return(i[b,c])))), c=1); while(k=bad(), until(!k-- || C[k] >= k, if(C[k]++<c, while(k<#C, C[k++]=0); next(2))); C*=0; c++); C}
%Y Length of row n is A000217(n-1).
%Y Total number of elements in rows 0 through n is A000292(n-1).
%Y Number of distinct colors in row n is A343607(n).
%K nonn,tabf
%O 0,26
%A _M. F. Hasler_, Jun 23 2021
|
