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
    This question/answer has been cited in http://arxiv.org/abs/1208.46182012-08-26

1 Answers 1

1

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

  • 0
    @Graphth Did you notice the (first) question was already answered?2012-08-31