0
$\begingroup$

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)|$?

  • 1
    For the second question, $G$ and its complement have the same automorphism group. You can construct an example $G$ with no non-trivial automorphisms.2012-08-01
  • 1
    This question/answer has been cited in http://arxiv.org/abs/1208.46182012-08-26

1 Answers 1