Assume we are given numbers $n,k\in\mathbb{N}$. We want to construct a graph $G=([n],E)$ such that its independence number satisfies $\alpha (G)<k$. Denote $s=|E|$, the number of edges in this graph.


We want to construct a graph $G$ with the minimum possible $s^\*(n,k)$. How can one determine this number? Are there graphs which are easy to construct and have optimal $s$ or close to it?


One can further ask: what happens if we let $G\_t=([n],E)$ be a hypergraph, that is, $E\subseteq 2^{[n]}$ and $\forall e\in E:|e|=t$ for $t\geq 2$ (note the equality in edge size).



Constructing graphs with independence number $\alpha (G)<k$
This is [Turán's theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem) (for a complement graph).


