Let $f(n)$ be smallest value such that for every graph $G$ on $n$ vertices, either $G$ or complement of $G$ contains a matching that covers $f(n)$ vertices. What's the best bound on $f(n)$?
I can get $f(n)$ is at least $n/2$ by simple greedy. $f(n)$ is at most $2n/3$ by $K_n$ - a clique of size $2n/3$.
I am also interested in generalization to $k$ uniform hypergraph :)
It turns out that the correct answer is $2n/3$. It can be proved by considering chromatic number of Kneser hypergraphs. The $k$ uniform case (generalized to $t$ coloring) is formally proved in the paper by Noga Alon.