Given a graph $G$, the domination number $\gamma(G)$ is the size of the smallest dominating set in $V(G)$.
I’m still working on this problem so I’d like to ask for comments on my approach below, and possibly some hints. Also I find myself frequently stuck when studying probabilistic method problems, since even the lecture content employs a lot of seemingly random tricks but not a “big picture” theory, so some ideas on how to think about these kinds of problems would be appreciated.
Let $\gamma = \gamma(G(n,p))$. We want to show that \begin{align} &\text{lim}_{n \to \infty} \mathbb{P}(\gamma = \Omega(p^{-1}\text{log}(np))) = 1 \\ \text{i.e. } &\text{lim}_{n \to \infty}\mathbb{P}(\gamma \geq kp^{-1}\text{log}(np)) = 1, \text{for some constant $k$} \\ \text{i.e. } &\text{lim}_{n \to \infty} \mathbb{P}(\exists S \subset V(G), |S| < kp^{-1}\text{log}(np), S \text{ is a dominating set}) = 0 \end{align}
Let $S$ be an arbitrary set of vertices, $|S| < kp^{-1}\text{log}(np)$. $S$ is not a dominating set if there exists $u \in (V \setminus S)$ s.t. $\forall s \in S, \{s,u\} \notin E(G)$.
Now for some $u \in G$ $$\mathbb{P}(\text{$u$ is not dominated by $S$}) = \left(1 - \frac{|S|}{n} \right)(1 - p)^{|S|},$$ i.e. $u$ is not in $S$ and none of the vertices in $S$ is a neighbour of $u$.
From here I can do a few other calculations, and I was thinking of using the union bounds twice to arrive at the lim statement. Unfortunately the assumption that $p = \omega(n^{-1/2})$ doesn’t help with this approach.