Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Theorem 7 and its following remark, printed p. 345, physical p. 5 of the published paper. The source credits the argument to S. Burr.

Let C2C_2 be the four vertices of a unit square. Then

R(C2,6,2) is true.(1)R(C_2,6,2)\ \text{is true}. \tag{1}

The graph lemma

Every red-blue coloring of the edges of K6K_6 has a monochromatic 44-cycle. To prove this, choose a vertex vv with at least three incident edges of one color, say red.

If vv has at least four red neighbors, the red edges among any four of them form a matching: two sharing a vertex would combine with vv to make a red 44-cycle. The complement of a matching on four vertices contains a blue 44-cycle, a contradiction. Thus, in the only remaining case, vv has exactly three red neighbors a,b,ca,b,c and two blue neighbors x,yx,y.

The red edges among a,b,ca,b,c again form a matching, so after relabeling ab,bcab,bc are blue. Each of x,yx,y has at most one red neighbor among a,b,ca,b,c, since two would make a red 44-cycle through vv. Hence each has at least two blue neighbors there. If they have two common blue neighbors, those four vertices form a blue 44-cycle. Otherwise their blue-neighbor sets are, after relabeling, {a,b}\{a,b\} and {b,c}\{b,c\}. Then

v,x,b,y,v(2)v,x,b,y,v \tag{2}

is a blue 44-cycle. This proves the lemma.

Euclidean realization

Let e1,…,e6e_1,\ldots,e_6 be the standard basis of R6\mathbb R^6. For every edge {i,j}\{i,j\} of K6K_6, put

pij=ei+ej2.(3)p_{ij}=\frac{e_i+e_j}{\sqrt2}. \tag{3}

A two-coloring of R6\mathbb R^6 colors these fifteen points and hence the edges of K6K_6. Let ij,jk,kℓ,ℓiij,jk,k\ell,\ell i be a monochromatic 44-cycle. Then

pij, pjk, pkℓ, pℓi(4)p_{ij},\ p_{jk},\ p_{k\ell},\ p_{\ell i} \tag{4}

are monochromatic. Consecutive differences in (4) have two nonzero coordinates, each of magnitude 1/21/\sqrt2, so have length 11. Consecutive side vectors use disjoint coordinate pairs and are orthogonal; opposite side vectors are negatives. Thus (4) is a unit square, proving (1).

The planar counterexample in the source

Color (s,t)∈R2(s,t)\in\mathbb R^2 by the parity of ⌊t⌋\lfloor t\rfloor. Suppose a unit square with orthonormal side vectors u,wu,w were monochromatic. Along each edge the vertical change has absolute value at most 11, so equal parities at its endpoints force the two floor values to be equal. Connectivity forces all four vertical coordinates into one half-open unit interval, whose diameter is strictly below 11. On the other hand their vertical span is

∣u2∣+∣w2∣≥u22+w22=1,(5)|u_2|+|w_2|\ge\sqrt{u_2^2+w_2^2}=1, \tag{5}

because u,wu,w are orthonormal. This contradiction proves R(C2,2,2)R(C_2,2,2) false, including points on stripe boundaries. The paper's 1973 remark that dimensions 3,4,53,4,5 were then undecided is historical context, not a current-status claim.