The minimum of alpha times omega for vertex-transitive graphs

Question

Definitions: For a graph $G$ we denote the independence number by $\alpha(G)$ and the clique number by $\omega(G)$. A graph is vertex-transitive if for every pair of vertices $x,y \in V(G)$ there is an automorphism that takes $x$ to $y$.

Question: What is the order of magnitude of the minimum of $\alpha(G)\times \omega(G)$ for vertex-transitive graphs?

Motivation/Additional information: I was thinking about a conjecture of János Körner. Let us say that two permutations have a flip if there are two coordinates that contain the same two elements in both permutations but the order of the two elements is different. Körner conjectures that the maximal size of a set of permutations where each pair have a flip is only exponential in the length of the permutations. One way to look at this problem is as follows. Define a graph $H$ where the vertices are the permutations, and we connect two vertices if the corresponding permutations have a flip. Then we have $|V(H)|=m!$. Körner conjectures that $\omega(H)$ is only exponential in $m$. Josef Cibulka determined the order of magnitude of the independence number of this graph: $\alpha(H) \sim m^ \frac{m}{2} $ (The construction is very nice, he calls a "flip" a "reverse", the paper can be found here https://pdfs.semanticscholar.org/aa5f/7de6b1727bb7618d6674f2aa848bf69335c6.pdf). The following inequality holds for all vertex transitive graphs, hence also for $H$: $$\alpha(H) \times \omega(H) \leq |V(H)|.$$
If the conjecture of Körner is true then $\alpha(H) \times \omega(H) \sim m^{\frac{m}{2}-o(m)}$ and $|V(H)|\sim m^m$. If we normalize the number of vertices of $H$ to be $n$ (as usual), we have a vertex transitive graph where $\alpha \times \omega$ is as small as $n^{\frac{1}{2}-o(1)}$. But I could not construct such a graph.

For not necessarily vertex transitive graphs $\alpha(G)\times \omega(G)$ can be as small as $\log(n)^2$, an example is an Erdős-Rényi random graph for $p=1/2$. (I am not sure whether this is indeed the minimum for general graphs, but this is not relevant for the conjecture that I am interested in.)

I could construct vertex-transitive graphs where $\alpha \times \omega \sim n^{c-o(1)}$ for $c \in (1/2,1)$ as follows: The pentagon has $\alpha \times \omega=4$ and $n=5$. We can blow up a graph as follows. If $G$ has $n$ vertices, take $n$ vertex disjoint copies of $G$. Fix an arbitrary pairing of these vertex disjoint copies with the vertices of the original graph. And if two vertex disjoint copies have their pairs connected in $G$, then add every edge between these disjoint copies. It is easy to see that if $G'$ is the blowup of $G$, then $\alpha(G')=\alpha(G)^2$ and $\omega(G')=\omega(G)^2$ and $|V(G')|=|V(G)|^2$ and if $G$ was vertex-transitive, $G'$ is also. Thus blowing up the pentagon many times we get a sequence of graphs where (after normalizing the number of vertices) we have $\alpha \times \omega \sim n^{0.8613}$.

Answer 1

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.