Explicitly known graph families where the product of the size of biggest independent set and biggest clique is "small" Are there explicit constructions of graph families with the following property:
$G_n$ is the graph on $n$ vertices in the family, $\omega(G_n)$ is the size of the biggest clique in the graph $G_n$, $\alpha(G_n)$ is the size of the biggest independent set in $G_n$, then we have
$$\omega(G_n)\alpha(G_n) \leq tn$$
for some $t$ where $t<0.8$.
Observe that,
$t=1$ can be trivially achieved by taking the family with $K_n$ (complete graph on $n$ vertices).
$t=0.8$ can be achieved by taking the family where $G_{5i}$ is the graph with $i$ copies of $C_5$.
 A: Clearly $\alpha$ and $\omega$ must be at least $2$.
There are known explicit families of graphs $G$ for which $\omega = 2$
(so $G$ is triangle-free) and $\alpha \ll n^\theta$ for some $\theta < 1$,
so $t \ll n^{\theta-1} \to 0$.  Erdos (1966) attained this with
$\theta = (3/2) \log_2 (3/2) < 0.88$; according to
https://mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/R4n.html
the current record is $2/3 < 0.67$, by Alon (1994), whose paper
https://www.cs.tau.ac.il/~nogaa/PDFS/r3k1.pdf
also cites the 1966 paper by Erdos and a few later improvements.
Alon constructs his graphs on pages 2-3, proves the triangle-free property
in a paragraph on page 3, and gives the upper bound on $\omega$ in
two further pages (proof of Theorem 2.1).
The optimal bound on $\theta$ is $1/2 + o(1)$,
but this has yet to be attained by explicit graphs.
In the comments Jason Gaitonde reports that there are
explicit "two-source extractors" that yield large graphs with
$t \ll n^{\epsilon-1}$ for all $\epsilon > 0$,
but with both $\alpha \to \infty$ and $\omega \to \infty$;
I think that this must be much more recent work.
References
N. Alon: Explicit Ramsey graphs and orthonormal labelings,
Electronic J. Combinatorics 1 (1994), R12.
P. Erdos: On the construction of certain graphs,
J. Combinatorial Theory 17 (1966), 149--153.
