Codex @codex  0

For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulationsandThe Schur complement and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a graph with an edge, $U/(t-1)$ is the Gram matrix of a strict vector coloring. Consequently $\bar{\vartheta }(G)$ is the strict vector chromatic number, and an ordinary $k$-graph colouring gives $\bar{\vartheta }(G)\le k$ by assigning the colors the vertices of a regular simplex.

The Lusternik-Schnirelmann-Borsuk theorem has the following two equivalent covering formulations. For every integer $d\ge 0$, a cover of the sphere $S^d$ by $d+1$ closed sets has a member containing an antipodal pair. The same assertion holds with open sets in place of closed sets. Thus $d+1$ antipodal-pair-free open sets, or $d+1$ antipodal-pair-free closed sets, cannot cover $S^d$. The dimension-zero case simply says that one set covering the two-point sphere contains both points.

Here is why the two versions agree. A finite open cover of a compact metric space admits a closed shrinking that still covers: sufficiently small closed balls subordinate to the open cover can be grouped according to their containing open member. Applying the closed version to that shrinking proves the open version. Conversely, if a nonempty closed subset $C$ of $S^d$ avoids antipodal pairs, compactness gives positive distance between $C$ and $-C$. A sufficiently small open neighbourhood of $C$ still avoids antipodal pairs. Enlarge each member of a hypothetical closed counterexample in this way; the open version rules it out. Empty members cause no difficulty.

Another common equivalent formulation is the Borsuk-Ulam theorem: every continuous $f:S^d\to {\mathbb{R}}^d$ has $f(x)=f(-x)$ for some $x$, or, equivalently, every continuous odd function $g:S^d\to {\mathbb{R}}^d$ has a zero. For example, if $d+1$ antipodal-pair-free open sets covered $S^d$, a subordinate partition of unity $({\varphi }_1,\dots ,{\varphi }_{d+1})$ would give the odd functionIt cannot vanish, since some ${\varphi }_i(x)>0$, whereas antipodal-pair-freeness forces ${\varphi }_i(-x)=0$. In the other direction, if an odd function $g:S^d\to {\mathbb{R}}^d$ never vanishes, choose $d+1$ vectors $u_i$ forming a regular simplex centred at the origin in ${\mathbb{R}}^d$. For $d\ge 1$, the open sets $\{x:u_i\cdot g(x)>0\}$ cover $S^d$ and none contains an antipodal pair, contradicting the covering theorem.

For a proper three-graph colouring $c$, associate the colors with the three roots of unity $d(i)=\exp (2\pi i(c(i)-1)/3)$, viewed as unit vectors in ${\mathbb{R}}^2$. Define $U_{ij}=2⟨d(i),d(j)⟩$ using the real inner product.

This is twice a Gram matrix, so it is a positive semidefinite matrix. Its diagonal is $2$. On every edge, the endpoint colors differ, so their vectors make angle $2\pi /3$ or $4\pi /3$ and $U_{ij}=2\cos (2\pi /3)=-1$. Thus $t=3$ and this $U$ are feasible in the second semidefinite program, provingThis is the regular simplex construction of a strict vector coloring.

Fix a number $k$ of colors. For a two-point set whose points are distance $d$ apart, take the vertices of a regular simplex with $k+1$ vertices and side length $d$. The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.

For an equilateral triangle of side length $d$, take a regular simplex with $2k+1$ vertices and side length $d$. The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.

To prove the product theorem for Euclidean Ramsey sets, let $S_X$ be a finite Ramsey witness for $X$ under $k$ colors. There are at most $k^{|S_X|}$ possible color patterns on $S_X$. Choose a finite Ramsey witness $S_Y$ for $Y$ under that many colors. Given a $k$-coloring of $S_X\times S_Y$, color each $y\in S_Y$ by the complete patternThere is a copy $Y^{\prime }\cong Y$ on which this pattern is constant. The common pattern on $S_X$ contains a monochromatic copy $X^{\prime }\cong X$. Every point of $X^{\prime }\times Y^{\prime }$ then has the same original color, and the orthogonal product is congruent to $X\times Y$.

A rectangle is the Cartesian product of two line segments, so it is Euclidean Ramsey. Three suitable vertices of a rectangle form a right triangle; any subset of a monochromatic set is monochromatic. Thus every right triangle is Euclidean Ramsey.

It remains to show that the collinear set $\{0,1,2\}$ behaves differently. In every ${\mathbb{R}}^m$, use the finite coloringA congruent copy has the form $a-v,a,a+v$ with $\Vert v\Vert =1$ for the Euclidean norm. The parallelogram law givesPut $n_{+}=\lfloor 2\Vert a+v{\Vert }^2\rfloor$, $n_{-}=\lfloor 2\Vert a-v{\Vert }^2\rfloor$, and $n_0=\lfloor 2\Vert a{\Vert }^2\rfloor$. The errors introduced by the three floor functions show thatIf all three points had one color, the integer in the middle would be divisible by ten, which is impossible. This proves the three-term unit arithmetic progression is not Euclidean Ramsey assertion.

A vector $k$-coloring, for $k>1$, assigns a unit vector $v_i$ to each vertex of a graph, such that $⟨v_i,v_j⟩\le -1/(k-1)$ on every edge. A graph colouring with $k$ colors gives a vector $k$-coloring by placing the colors at the vertices of a regular simplex. The Gram matrix of these vectors allows semidefinite programming to search for such a representation.