# three-uniform hypergraph on $n$ vertices with at least $n/3$ edges contains an independent set of size at least $\frac{2n^{3/2}}{3\sqrt{3m}}$

Here is question 3 from chapter 3 Part 1 of The Probabilistic Method, 4th edition.

Prove that every three-uniform hypergraph with $$n$$ vertices and $$m \ge n∕3$$ edges contains an independent set (i.e., a set of vertices containing no edges) of size at least $$\frac{2n^{3/2}}{3\sqrt{3m}}$$.

I'm trying to solve this using a probabilistic approach. I've only been able to get $$\frac{n^{3/2}-mn^{1/2}}{\sqrt{3m}}$$ as a bound by defining $$S\subset [n]$$ by randomly including a vertex in $$S$$ with probability $$p$$. We call the resulting induced graph $$G':=G[S]$$ and denote its vertex set and edge set by $$V'$$ and $$E'$$. Then $$\mathbb E[|V'|]-\mathbb E[|E'|]=np-mp^3$$ because for each edge to be inside $$S$$ we need all three of its vertices to be chosen. Also, removing one vertex per edge in $$G'$$ results in an edge-less graph, so $$\alpha(G)\ge\alpha(G')\ge np-mp^3$$, where $$\alpha$$ is the size of the largest independent set. The inequality comes from taking the expectation on $$\alpha(G')\ge \mathbb E[|V'|]-\mathbb E[|E'|]$$.

Then the idea is to optimize over $$p$$, so make the 1st derivative w.r.t. $$p$$ equal to zero and get $$p=\frac{n^{1/2}}{\sqrt{3m}}$$ and the optimized RHS of the equality is $$\frac{n^{3/2}-mn^{1/2}}{\sqrt{3m}}$$.

Now the problem is that there is a minus there and the hypothesis is that $$m\ge n/3$$ so $$-mn^{1/2}\le-\frac{-n^{3/2}}{3}$$ and so $$\alpha(G)\ge f(m,n)$$ with $$f(m,n)\le \frac{2n^{3/2}}{3\sqrt{3m}}=:B$$, which does't prove anything. I think I must have made a mistake somewhere...

I only showed that the largest independent set is bounded from below by something which is below $$B$$. If I had showed that it is bounded by $$B$$ then that would probably be enough to say that there exists an independent set of size at least $$B$$.

Your algebra is fine. I think you just misunderstand what optimizing over $$p$$ does.

The inequality $$\alpha(G) \ge np - mp^3$$ holds for any $$m, n$$ and any $$p \in [0,1]$$, because the random process you've described works for any $$m, n$$ and any $$p \in [0,1]$$. It will produce a random independent set $$S$$, with $$\mathbb E[|S|] \ge np - mp^3$$; therefore, with positive probability, it will produce an $$S$$ with $$|S| \ge np - mp^3$$; therefore, the largest independent set has size at least $$np - mp^3$$.

At this point, if all you want to do is to write a proof, you can just write:

For no particular reason, we are inspired to take $$p = \sqrt{\frac{n}{3m}}$$, which satisfies $$0 \le p \le 1$$ provided that $$m \ge n/3$$. With this value of $$p$$, we conclude that $$\alpha(G) \ge \frac{2n^{3/2}}{3\sqrt{3m}}$$, which was what we wanted.

If we want to actually find a good value of $$p$$ to pick, so that we can come up with the proof, then optimizing over $$p$$ is a good idea. When $$m \ge n/3$$, we conclude that $$p = \sqrt{\frac{n}{3m}}$$ is the best probability to use. In other words, we deduce the inequality $$np - mp^3 \le \frac{2n^{3/2}}{3\sqrt{3m}}.$$ You're right that sticking this inequality into our proof would produce nonsense! But this inequality doesn't belong in our proof to begin with. It is part of our outside-the-proof reasoning for picking $$p$$.

All we actually need to know is that the right-hand side $$\frac{2n^{3/2}}{3\sqrt{3m}}$$ is achievable by some choice of $$p$$. We don't, strictly speaking, need to know that it's the largest possible value of $$np - mp^3$$. (But if it weren't, we could have written a better proof.)

In more complicated problems, it is common to skip taking the derivative, because we wouldn't get a closed form for the answer. Even here, we could be lazy and think "hmm... we want $$np$$ and $$mp^3$$ to be about the same size. Let's try setting $$mp^3 = \frac12 np$$. This gives us $$p^2 = \frac{n}{2m}$$, which gives some answer of the form $$O(n^{3/2}/m^{1/2})$$. Good enough!" Then, we could write a proof using $$p = \sqrt{\frac{n}{2m}}$$. That proof would work equally well, even though it no longer proves the best lower bound that this method can prove.

• Awesome answer, thanks. I didn't see the usefulness of $m\ge n/3$ so I kept trying to use it and coming up with inequalities but it's just a technical constraint to have the optimized $p$ be in $[0,1]$. Commented Dec 29, 2020 at 9:20