Section 7.2.2.2: Satisfiability

Exercise 240. [HM23] Choose integers $f_{ij} \in {1, \ldots, m}$ uniformly at random, for $1 \le i \le 5$ and $0 \le j \le m$, and let $G_0$ be the bipartite graph with edges $a_j — b_k$ if and only if $k \in {f_{1j}, \ldots, f_{5j}}$. Show that $\Pr(G_0$ satisfies the strong expansion condition $(108)) \ge 1/2$.

Verified: no
Solve time: 3m29s

---

Solution

Let

$$ A={a_0,\ldots,a_m},\qquad B={b_1,\ldots,b_m}. $$

Condition (108) is the strong expansion requirement that every nonempty subset $A'\subseteq A$ with

$$ |A'|\le \frac{m}{3000} $$

has strictly more than $|A'|$ vertices of $B$ with exactly one neighbor in $A'$. For $A'\subseteq A$, let $\partial A'$ denote this set of vertices of $B$.

We prove that

$$ \Pr\left(\exists A'\subseteq A,\ 1\le |A'|\le \frac{m}{3000},\ |\partial A'|<|A'|\right)\le \frac12 . $$

The complement is precisely the desired expansion condition.

If $m<3000$, then there is no nonempty integer $s$ satisfying $s\le m/3000$, so the condition is vacuous. Hence assume $m\ge3000$.

Fix a subset $A'\subseteq A$ of size

$$ |A'|=s,\qquad 1\le s\le \frac{m}{3000}. $$

The $5s$ choices made by the vertices of $A'$ are independent uniform choices from the $m$ vertices of $B$. Suppose that

$$ |\partial A'|<s . $$

Let $u$ be the number of vertices of $B$ that receive at least one of the $5s$ choices, and let $q=|\partial A'|$ be the number of vertices that receive exactly one choice. The remaining $u-q$ occupied vertices receive at least two choices each. Therefore

$$ 5s\ge q+2(u-q)=2u-q . $$

Since $q<s$,

$$ 2u<5s+s=6s, $$

and hence

$$ u<3s . $$

Thus every bad set $A'$ has all of its $5s$ random choices contained in fewer than $3s$ vertices of $B$.

For a fixed $A'$, the probability of this event is at most

$$ \left(\sum_{r=0}^{3s-1}\binom mr\right) \left(\frac{3s}{m}\right)^{5s}. $$

We use the standard estimate, valid for $k\le m/2$,

$$ \sum_{r=0}^{k-1}\binom mr\le \left(\frac{em}{k}\right)^k . $$

Indeed, the left side is at most $2^m\Pr(X<k)$ for a suitable binomial variable $X$, or equivalently it follows from the usual binomial coefficient bound and monotonicity of the terms when $k\le m/2$. Here $k=3s$, and since

$$ 3s\le \frac m{1000}, $$

the hypothesis holds. Consequently,

$$ \sum_{r=0}^{3s-1}\binom mr \le \left(\frac{em}{3s}\right)^{3s}. $$

Therefore, for a fixed $A'$,

$$ \Pr(|\partial A'|<s) \le \left(\frac{em}{3s}\right)^{3s} \left(\frac{3s}{m}\right)^{5s}. $$

Simplifying,

$$ \left(\frac{em}{3s}\right)^{3s} \left(\frac{3s}{m}\right)^{5s}

\left( e^3\frac{(3s)^2}{m^2} \right)^s

\left( \frac{9e^3s^2}{m^2} \right)^s . $$

Now apply the union bound over all subsets $A'$ of size $s$. There are

$$ \binom{m+1}{s} $$

such subsets, and

$$ \binom{m+1}{s} \le \left(\frac{e(m+1)}s\right)^s . $$

Hence

$$ \Pr(\exists A'\subseteq A,\ |A'|=s,\ |\partial A'|<s) \le \left(\frac{e(m+1)}s\right)^s \left(\frac{9e^3s^2}{m^2}\right)^s . $$

Combining the factors gives

$$ \Pr(\exists A'\subseteq A,\ |A'|=s,\ |\partial A'|<s) \le \left( \frac{9e^4s(m+1)}{m^2} \right)^s . $$

Because

$$ s\le \frac m{3000}, $$

we obtain

$$ \frac{9e^4s(m+1)}{m^2} \le \frac{9e^4}{3000}\frac{m+1}{m}. $$

Since $m\ge3000$,

$$ \frac{m+1}{m}\le\frac{3001}{3000}, $$

and therefore

$$ \frac{9e^4s(m+1)}{m^2} \le \frac{9e^4\cdot3001}{3000^2}. $$

Let

$$ c=\frac{9e^4\cdot3001}{3000^2}. $$

Numerically,

$$ c<0.165 . $$

Thus for every admissible $s$,

$$ \Pr(\exists A'\subseteq A,\ |A'|=s,\ |\partial A'|<s) \le c^s . $$

Finally, summing over all possible values of $s$,

$$ \Pr(\exists A'\subseteq A,\ 1\le |A'|\le m/3000,\ |\partial A'|<|A'|) \le \sum_{s\ge1}c^s . $$

Using the geometric series,

$$ \sum_{s\ge1}c^s=\frac{c}{1-c}, $$

and with $c<0.165$,

$$ \frac{c}{1-c} < \frac{0.165}{0.835} < 0.198 < \frac12 . $$

Therefore the probability that there exists a subset violating the strong expansion condition is less than $1/2$. Hence

$$ \Pr(G_0\text{ satisfies (108)}) \ge 1-\frac12

\frac12 . $$

Therefore,

$$ \boxed{\Pr(G_0\text{ satisfies the strong expansion condition (108)})\ge\frac12}. $$

$\square$