Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?
An $m\times m$ adjacency matrix requires $m^2$ bits, and $m=\sqrt{n}$ is just the solution to $m^2 = |\langle G\rangle| = n$.

The point of the $\Omega$ is that a reasonable encoding doesn't have fewer than $\sqrt{n}$ vertices in a description of length&nbsp;$n$.  For example "Write out the $k\times k$ adjacency matrix followed by $2^k$ zeroes" isn't "reasonable" and a string of length&nbsp;$n$ would encode a graph with only about $\log n$ vertices.