Skip to main content
4 of 5
added 2 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

One very promising 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.$ No graph on $42$ vertices could be a Paley graph and there are at least $656$ known with $\alpha=\omega=4.$ The Paley Graph on $37$ vertices has $\alpha=\omega=4$ but the Paley Graph on $41$ vertices has $\alpha=\omega=5.$

So Paley graphs are perhaps not the absolute best but they are easily described explicit (self dual, vertex transitive) graphs that seem quite good. As far as I know, the largest know graph with $\alpha \lt 6$ and $\omega \lt 6$ is the Paley Graph on $101$ vertices.

A final quote:

Paley graphs are quasi-random (Chung et al. 1989): the number of times each possible constant-order graph occurs as a subgraph of a Paley graph is (in the limit for large q) the same as for random graphs, and large sets of vertices have approximately the same number of edges as they would in random graphs.

LATER It occurs to me that a random circulant graph with edge density $\frac12$ might be a better choice in some ways. On one hand the chance of $\{{1,2,3\cdots,k\}}$ being a clique in that model is $\frac1{2^k}$ but, due to the multiplicative nature of quadratic residues, in the Paley graph this just requires the primes up to $k$ to be residues hence it is $\frac1{2^{\ln k}}=\frac1{k^{\ln2}}.$ On the other hand, if we somehow knew that the expected value of $\alpha \omega$ is less than $1000 (\log n)^2,$ that wouldn't give us any explicit graph.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104