I have been stuck on the following problem for a while now. This is question 1 in chapter 10 of The probabilistic method by Alon and Spencer. The question is
Show that there is a graph on $n$ vertices with minimum degree at least $n/2$ in which the size of every dominating set is at least $\Omega (\ln n)$.
I am trying to let $G\sim G(n,p)$, and to then find a $p$ such that both conditions hold for some $p$ with probability $>1/2$, so that with positive probability both conditions hold. I did not get too far, here is what I got
Domination number
Let $G \sim G(n,p)$. Then, for some $t\in \mathbf{N}$, let $Y$ be the event that $G$ contains a dominating set of size less than or equal to $t$. We have \begin{align} \mathbb{P} (Y) &\leq \sum\limits_{S \in \binom{[n]}{t} } \ \bigwedge\limits_{v \notin S} \mathbb{P}( \text{$v$ dominated by $S$ ) }\\ &=\binom{n}{t} ({1-(1-p)^{t}})^{(n-t)}\\ &\leq \binom{n}{t}e^{-(n-t)(1-p)^t } \end{align}
Now, we want $t = \Omega(\ln n)$.
Intermediate note From the above it seems that setting $t=\log_{1-p} n$ would ensure that the above converges to zero, so that almost surely we have only 'large' dominating sets. Then if $1-p$ converges to some constant (or is perhaps appropriately bounded), we have $\log_{1-p} n= \Omega (\ln n)$ so that at least the desired property on the domination number holds.
Minimum degree
Let $q=1-p$. For the minimum degree, I was hoping to get away with the super greedy estimate \begin{align} \mathbb{P}(\delta_G \geq n/2) &= 1-\mathbb{P}(\exists v \text{ s.t. }d(v)<n/2 )\\ &\geq 1- n \mathbb{P}(d(v)<n/2)\\ &= 1 - n \left(\binom{n}{0}q^{n-1} +\binom{n}{1} pq^{n-2} + \binom{n}{2} p^2q^{n-3}+\ldots +\binom{n}{n/2-1} p^{n/2-1}q^{n/2+1}\right). \end{align} However, I believe the above sum in brackets is roughly half of $(p+q)^n = 1$, so that we bound a probability from below by $1- n/2$, which does nothing for us. Perhaps some estimate on the middle term (which is missing) of Newton's Binomium can save the day, but I doubt it.
If someone has any tips on how to advance, I would love to hear them, also pointers towards a wholly different method that can be succesful are welcome. Thanks!
This is a sketch of how I would do it.
A. Put an edge between two vertices with probability [say] $\frac{4}{7}$ i.e., some constant a bit more than $1/2$. Then [for large $n$] probability that there is a vertex in $G$ that has degree less than $n/2$, is at most $e^{-an}$ for some $a \in \Omega(1)$.
B. Now let $S$ be any subset of vertices with size no larger than $\frac{\ln n}{100}$. For any vertex $u$ the probability that there is no vertex in $S$ adjacent to $u$ is $\left(\frac{3}{7}\right)^{|S|}$, which is at least $n^{-\epsilon}$ for some $\epsilon \le \frac{1}{3}$. Thus the probability that $S$ is a dominating set is no more than $(1-n^{\epsilon})^{n} < e^{-\sqrt{n}}$.
C. The number of such $S$ as in B. is no more than $e^{\ln^2 n}$.
D. So the probability that $G$ so constructed has the required minim degree and no dominating set of size less than $\frac{\ln n}{100}$ is at least $1 - e^{-an}-e^{\ln^2 n}e^{-\sqrt{n}} > 1/2$.