Suppose $H=(V,E)$ is a $3$-uniform hypergraph with $n$ vertices $V$ and $O(n^{3/2})$ hyperedges, $E.$
My question is: How many vertices do I need to delete to make sure all hyperedges are destroyed?
I can solve this problem by Pigeonhole principle and greedy approach, but unfortunately, it does not give me a good upper bound. I know if I delete at most $n-n^{2/3}$ vertices, then $H$ has no more hyperedges. I was wondering if there is any better solution/idea for that?
It is more natural to search for a maximal independent set (which contains no hyperedges). Choose $K$ vertices at random. We have at most $C\cdot (K/n)^3\cdot n^{3/2}=CK^3/n^{3/2}$ edges on them. Assume that it is less than $K/2$, than removing a vertex from any edge we get an independent set of size $K/2$ (this trick is due to Erdős, I think.) So, we may get an independent set of size $K/2$ provided that $CK^2<n^{3/2}$, so $K$ is of order $n^{3/4}$.
On the other hand, if we consider a random hypergraph with $E=[n^{3/2}]$ hyperedges $e_1,\dots,e_{E}$ (chosen independently at random, so they may coincide and actual number of hyperedges may be even less), the probability that a given subset of size $K$ is independent equals $$ \left(1-\binom{K}{3}/\binom{n}3\right)^E\sim e^{-EK^3/n^3}. $$ If it is less than $1/\binom{n}K$, we may find a hypergraph without independent subsets of size $K$. We have $\binom{n}K=\frac{n(n-1)\dots (n-K+1)}{K!}\leqslant \frac{n^Ke^K}{K^K}=e^{K(\log n+1-\log K)}$. Thus we need $EK^3/n^3>C\cdot K\log n$, this happens when $K>n^{3/4}(C\log n)^{1/2}$.
