Ramsey Theory — Examples

At vertex $0$ of a red-blue $K_6$, three incident edges share a colour. If they are $01,02,03$ and red, then a red edge among $12,13,23$ closes a red triangle, while the absence of such an edge makes $123$ a blue triangle. Exchanging colours covers the other case.

On $K_5$, colour $01,12,23,34,40$ red and the other edges blue. The red graph is the cycle $0,1,2,3,4,0$; the blue graph is the cycle $0,2,4,1,3,0$. Neither cycle has a triangle. This gives a five-vertex avoidance colouring and, together with step 1.1, verifies both sides of [L1].

On $\{0,\ldots,7\}$ colour $0,1,4,5$ blue and $2,3,6,7$ red. Checking the possible differences $d=1,2,3$ shows that every three-term progression meets both two-point colour blocks. Thus $W(3,2)>8$.

Suppose $\{0,\ldots,8\}$ has an avoiding colouring. Exchange colour names to make $4$ red. The progression $0,4,8$ has a blue endpoint; reflect the interval if necessary to make $0$ blue. If $2$ is red, the progressions $2,3,4$ and $2,4,6$ force $3,6$ blue, making $0,3,6$ blue, a contradiction. Hence $2$ is blue, and $0,1,2$ forces $1$ red.

If $3$ is red, then $1,3,5$ forces $5$ blue, $1,4,7$ forces $7$ blue, $2,5,8$ forces $8$ red, and $4,6,8$ forces $6$ blue; now $5,6,7$ is blue. If $3$ is blue, then $0,3,6$ forces $6$ red, $1,4,7$ forces $7$ blue, and $3,5,7$ forces $5$ red; now $4,5,6$ is red. Both cases contradict avoidance, so every colouring of nine consecutive integers has a monochromatic three-term progression.

Steps 1.1 and 2.1 give the lower and upper bounds, hence $W(3,2)=9$.

For $i<j$, colour $\{i,j\}$ up when $x_i\le x_j$ and down when $x_i>x_j$. By [L1] there is an infinite homogeneous set of indices.

Enumerate that set increasingly. In the up case every earlier selected term is at most every later one, giving a nondecreasing subsequence. In the down case every earlier selected term is greater than every later one, giving a strictly decreasing, hence nonincreasing, subsequence.

For $i<j<k$, colour the triple convex when $(x_j-x_i)/(j-i)<(x_k-x_j)/(k-j)$ and concave when the reverse inequality holds. General position excludes equality, so this is a two-colouring. Apply [L1] with $k=3$.

On the resulting infinite index set, every ordered triple has the same strict slope comparison. In the convex colour every successive secant slope increases, and in the concave colour every such slope decreases.

Increasing secant slopes are exactly the strict convexity inequality for the selected graph, while decreasing slopes give strict concavity. Thus the increasing enumeration of the homogeneous index set is the required subsequence.

Colour $0$ red. For $n\ge1$, colour $n$ red when the unique $m$ with $2^m\le n<2^{m+1}$ is even, and blue when $m$ is odd. Thus consecutive dyadic blocks alternate colours, with every power of two assigned to the block beginning there.

Fix $a\in\mathbb N$ and $d>0$. For every sufficiently large $m$, let $q_m$ be the least $q$ with $a+q d\ge2^m$. Minimality gives $a+q_m d<2^m+d<2^{m+1}$, so the progression meets the $m$th dyadic block. It therefore meets infinitely many blocks of each parity and contains both colours.

No infinite arithmetic progression is monochromatic in this colouring. This does not contradict [L1], which guarantees arbitrarily long finite progressions only. The displayed universal statement is false.

Let $T$ consist of the empty sequence and all finite strictly decreasing sequences of natural numbers. It is prefix closed. For every $n$, the sequence $(n-1,n-2,\ldots,0)$ is a node of length $n$, so every finite level is nonempty.

The root has infinitely many successors, so $T$ is not finitely branching. An infinite branch would be an infinite strictly decreasing sequence of naturals, but its range would have a least element by The well-ordering principle, after which the branch would have to contain a smaller one. Thus no infinite branch exists, and the missing hypothesis relative to [L1] is exactly finite branching.

Every natural $i$ occurs as $c(\{i,i+1\})=i$, so this colouring genuinely has infinitely many colours.

If $a<b<c$, then $c(\{a,b\})=a$ while $c(\{b,c\})=b$, and these colours differ. Hence no set of size at least three is monochromatic, in particular no infinite set is. This refutes the proposed extension and leaves [L1]'s finite-colour conclusion untouched.

The formula $c_0(\{i,j\})=0$ is constant. The formula $c_I(\{i,j\})=\{i,j\}$ is injective because equal two-element subsets are the same unordered pair.

For $i<j$, set $c_L(\{i,j\})=i$ and $c_R(\{i,j\})=j$. Then $c_L(\{i,j\})=c_L(\{k,l\})$ if and only if $i=k$, and $c_R(\{i,j\})=c_R(\{k,l\})$ if and only if $j=l$. Thus all four mutually distinct equality patterns listed in [L1] occur.