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

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

  • 1
    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$).2012-06-26
  • 0
    @ErickWong That would be an answer then, not a comment. Answer the question.2012-08-31
  • 0
    @Graphth Did you notice the (first) question was already answered?2012-08-31