# Do the “Classical” Ramsey Numbers make up a monotone Sequence on the real Line?

Actually I have two questions.

Suppose a graph $G$ has either a complete subgraph $K_n$ or else its complement $G^c$ has a complete subgraph $K_n$, and let $r(n, n)$ denote its classical Ramsey number.

1. Is the sequence

$r(3, 3)$, $r(4, 4)$, $r(5, 5)$, ...

of Ramsey numbers $r(n, n)$ monotone nondecreasing as $n\rightarrow\infty$?

2. Does $|\operatorname{Aut}(K_n)|$ always divide $|\operatorname{Aut}(G)|$ or otherwise does $|\operatorname{Aut}(K_n)|$ divide $|\operatorname{Aut}(G^c)|$?

-
For the second question, $G$ and its complement have the same automorphism group. You can construct an example $G$ with no non-trivial automorphisms. – Yuval Filmus Aug 1 '12 at 12:23
This question/answer has been cited in arxiv.org/abs/1208.4618 – user16299 Aug 26 '12 at 1:56

It’s clear that the sequence is non-decreasing: if $G$ is a graph on $r(n+1,n+1)$ vertices, then either $G$ or its complement contains $K_{n+1}$ as a subgraph, so certainly either $G$ or its complement contains $K_n$ as a subgraph. Thus, $r(n+1,n+1)\ge r(n,n)$.
It is in fact strictly increasing. If $G$ is any graph with $r(n+1,n+1)-2$ vertices, then adjoin an isolated vertex $v$ and a fully-connected vertex $w$ to form $G'$ (doesn't matter how $v$ and $w$ are connected). If $G'$ contains a $K_{n+1}$, then $G$ contains a $K_n$, and likewise for the complements. (It's impossible for $v$ and $w$ to both be in the clique/anticlique, at least for large enough $n$). – Erick Wong Jun 26 '12 at 5:58