A Ramsey Type Problem

Abstract

Ramsey’s Theorem implies that for any graph $H$ there is a least integer $r=r(H)$ such that if $G$ is any graph of order at least $r$ then either $G$ or its complement contains $H$ as a subgraph. For $n<r$ and $0\le e\le \frac{1}{2}n(n-1)$, let $f(e)=1$ {if every graph $G$ of order $n$ and size $e$ is such that either $G$ or $\overline{G}$ contains $H$,} and let $f(e)=0$ {otherwise.} This associates with the pair $(H,n)$ a binary sequence $S(H,n)$. By an interval of $S(H,n)$ we mean a maximal string of equal terms. We show that there exist infinitely many pairs $(H,n)$ for which $S(H,n)$ has seven intervals.