Let me know if there's a similar question but I couldn't find any. This question is from the course on probabilistic methods.
I have tried several approaches, but none has seemed to converge to a solution.
Let $G$ be a $k$-uniform hypergraph with $n$ vertices and $m$ edges. A transversal $T$ in $G$ is a subset of $V(G)$ if $T$ intersects every edge $e = \{v_1,..., v_k\}$ in $E(G)$. I am interested in proving it using the alteration method.
Thanks!
This is not a proof for the desired bound, but it is a proof of another bound using the alteration method (also known as sample and modify), so I hope it is an inspiring remark.
I adapt the proof from here for independent sets. Funny enough, I obtain a different bound which is better for very sparse hypergraphs, namely for $n>\max(\frac{k}{\log(k)}-\frac{1}{k},k)m$, and for very dense large hypergraphs.
In the first step we remove each of the $n$ vertices in $G$ independently with probability $p$, along with its incident hyperedges. In the second step we remove the minimum number of vertices along with their remaining incident hyperedges such that the resulting hypergraph is empty. Notice that the removed vertices are a transversal in $G$. Let $X$ be the number of vertices removed in the first step and $Y$ the number of remaining hyperedges, which is an upper bound to the number of vertices removed in the second step. Then we have $$\mathbb E[X]=np$$ for the first step and $$\mathbb E[Y]=m(1-p)^k$$ for the hyperedges (i.e. the second step) because a hyperedge is still present if none of its $k$ vertices is removed. Now, the expected size of the resulting transversal is $s(p)=\mathbb E[X+Y]=np+(1-p)^km$. Taking the derivative, we obtain $s'(p)=n-k(1-p)^{k-1}m$. Notice that $s'$ is increasing in $p$. If the average degree is at least $1$, i.e. $n\le km$, then we have a unique minimizer of $s$ at $p^*=1-(\frac{n}{km})^{\frac{1}{k-1}}$, otherwise $s'>0$ and the unique minimizer is $p^*=0$. This shows that there exists a transversal of size at most $s(p^*)=m$ if $n>km$, meaning that we just choose (at most) one vertex in each hyperedge for the transversal, while for $n\le km$ we have a transversal of size at most $$s(p^*)=n\left(1-\left(\frac{n}{km}\right)^{\frac{1}{k-1}}\right)+\frac{n^{\frac{k}{k-1}}}{k^{\frac{k}{k-1}}m^{\frac{1}{k-1}}}.$$ For the bound on $n$ given above, our bound is $m$ which is better than the bound by the OP. For $m=\binom{n}{k}$ and $n$ large our bound is essentially $n+c$ for some constant $c$ depending on $k$, while the bound by the OP is essentially $c'n^k$ for some $c'$ depending on $k$. However, we can also identify cases where the bound by the OP is better. Hence, the bounds are not comparable.