Graph Ramsey number

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.