A343606 Row n gives the lexicographically earliest edge coloring of the complete graph K_n with no monochromatic triangle.

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, 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, 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

Offset: 0

Author

M. F. Hasler, Jun 23 2021

Keywords

• nonn
• tabf

Comments

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.

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).

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).

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.

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.

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.)

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.

Can one or the other of the following conjectures be (dis)proved?

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?

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.

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.

Examples

			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.
Starting with n = 2, the graph K_n has a positive number n(n-1)/2 of edges:
   n | Coloring of edges (1,2) = AB, (1,3) = AC, (2,3) = BC, ..., (n-1,n) = YZ
  ---+------------------------------------------------------------------------
   2 | 0      (The only non-diagonal element, in row/col. 2 of the color matrix.)
   3 | 0; 0, 1       (Rows 2 and 3 of the subdiagonal part of the color matrix.)
   4 | 0; 0, 1; 1, 0, 0      (Rows 2, 3 and 4 below the diagonal of that matrix.)
   5 | 0; 0, 1; 1, 0, 1; 1, 1, 0, 0
   6 | 0; 0, 1; 0, 1, 2; 0, 2, 1, 1; 1, 0, 0, 0, 0
   7 | 0; 0, 1; 0, 1, 2; 0, 2, 1, 1; 1, 0, 0, 0, 0; 1, 0, 0, 0, 0, 2
   8 | ...; 2, 0, 0, 0, 0, 1, 1                           (where ... = row 7)
   9 | ...; 2, 0, 0, 0, 0, 1, 2; 2, 0, 0, 0, 0, 2, 1, 1
  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
  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
     |                         ; 2, 2, 2, 1, 0, 2, 1, 0, 0, 1
The graph K_2 consists of only one edge with color 0.
The graph K_3 is a triangle, two edges get color 0, the third one color 1.
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.
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.
		

Crossrefs

Length of row n is A000217(n-1).

Total number of elements in rows 0 through n is A000292(n-1).

Number of distinct colors in row n is A343607(n).

Programs

PARI

row(n)={ local(C=vector(n*(n-1)/2), k, i=matrix(n, n, i, j, if(i= k, if(C[k]++