Skip to main content
1 of 5
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

One place to look is at Paley Graphs which are self dual (so $\alpha=\omega$.) This answer to a question suggests that, based on prime $n \lt 10000,$ it might be that $\alpha \omega =O(log^4 n).$ Although it been the subject of a fair amount of research, all that is known for sure is that $\log n \lt \alpha=\omega \le \sqrt{n}.$ The upper bound can, evidently, be reduced to $\sqrt{n}-1$ infinitely often.

Any other circulant graphs could be considered and those with degree $\frac{n-1}{2}$ (so edge density $\frac12$) do seem optimal. A pentagon is a circulant graph (in fact a Paley Graph) and the tensor product of circulant graphs is a circulant graph.

Any graph of $R(3,3)=6$ vertices or more has $\max(\alpha,\omega) \ge 3.$ In general, one less than a Ramsey number $R(s,s)-1$ is the largest size for a graph with $\max(\alpha,\omega) \lt s.$

$R(4,4)-1=17$ and among all graphs on 17 vertices (regular or not) the Paley Graph on $17$ vertices is the unique example with $\alpha \lt 4$ and $\omega \lt 4.$

No larger Ramsey numbers are known although $42 \lt R(5,5) \le 49.$

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104