Ramsey theorem

Every sufficiently large graph contains either a prescribed clique or a prescribed independent set.

The diagonal Ramsey number $R(t)$ is the least $n$ such that every red-blue edge-colouring of $K_n$ contains a monochromatic $K_t$.

The off-diagonal recursionwith $R(1,t)=R(s,1)=1$ givesIn particular, $R(t)\le \left(\genfrac{}{}{0ex}{}{2t-2}{t-1}\right)<2^{2t}$.

In a red-blue edge colouring of $K_n$, let $d_v$ be the red degree of vertex $v$ and let $M$ be the number of monochromatic triangles. Every nonmonochromatic triangle has exactly two vertices at which its two incident edges have different colors, soSince $d_v(n-1-d_v)\le \lfloor (n-1{)}^2/4\rfloor$, this identity gives a lower bound for $M$.

For a finite graph $G$, its two-colour Ramsey number $R(G)$ is the least $n$ such that every red-blue colouring of $K_n$ contains a monochromatic copy of $G$. It exists because a monochromatic clique on $|V(G)|$ vertices contains a copy of $G$.

Sampling $G(n,p)$ and deleting one vertex per triangle and per independent $t$-set gives $R(3,t)>n-\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3-\left(\genfrac{}{}{0ex}{}{n}{t}\right)(1-p{)}^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Choosing $n$ of order $(t/\log t{)}^{3/2}$ and $p$ of order $\log t/t$ makes the forbidden configurations inexpensive enough to prove the corresponding lower bound.

The Ramsey number $r(G,H)$ is the least $n$ such that every red-blue colouring of $K_n$ contains a red copy of $G$ or a blue copy of $H$.

If $P_t$ denotes a path of length $t$, thenfor $s\ge 2$ and $t\ge 1$.

For the star $K_{1,t}$,The parity distinction follows from the handshake lemma applied to a hypothetical $(t-1)$-regular colour class on $2t-1$ vertices.

The paw graph is a triangle with one pendant edge.

The paw graph $H$ has $R(H)=7$. A colouring of $K_6$ with two disjoint red triangles and all cross-edges blue avoids a monochromatic paw. In $K_7$, a monochromatic triangle exists; avoiding a paw forces all its edges to the other four vertices into the opposite colour, which then forces those four internal edges into the triangle's colour and creates a paw.

The diagonal $r$-uniform hypergraph Ramsey number $R^{(r)}(k)$ is the least $N$ such that every red-blue colouring of the $r$-element subsets of an $N$-element set has a monochromatic $k$-element set.

Let $K_4^{(3)-}$ be the three-uniform hypergraph with three of the four possible edges on four vertices. Every $K_4^{(3)-}$-free three-uniform hypergraph on $N$ vertices has an independent set of size at leastEquivalently, $r(K_4^{(3)-},K_k^{(3)})\le k^{Ck}$.

For every colouring of the $r$-element subsets of an infinite set, there is an infinite increasing sequence $X$ and a coordinate set $I\subseteq \{1,\dots ,r\}$ such that two increasing $r$-tuples from $X$ have the same colour exactly when they agree in every coordinate indexed by $I$.

A homogeneous linear equation is partition regular when every finite colouring of the positive integers admits a solution whose coordinates all have one colour.