Probabilistic Transversals in Hypergraphs

28 Views Asked by At

This is a result from Noga Alon's 1990 paper, "Transversal Numbers of Uniform Hypergraphs".

In section 3: $\,H = (\,V,E\,)$ is a random $k$-uniform hypergraph on a set $V$ of $n$ vertices, with $m$ (not necessarily distinct) edges, constructed by choosing the $m$ edges randomly and independently according to a uniform distribution on the $k$-subsets of $V$.

He writes that by setting $n = [k \; log \, k]$ with edges $m = k$ and a fixed subset $X$ of $V$, and $|X| \leq log^2k - 10 \,log \,k\, log\,( log\,k)$, estimating the probability that $X$ is transversal of $H$ is done in the following manner. For each of the $m$ edges $e$ of $H$, the probability that $e$ does not intersect $X$ satisfies

$$\mathbb{P}(e \cap X = \emptyset) = \frac{\binom{\,n - |X|\,}{k}}{\binom{\,n}{k}} \geq \bigg( \frac{n-|X| - k}{n-k} \bigg)^k \geq \bigg(\frac{k \; log \, k - log^2k + 10 \,log \,k\, log\,( log\,k) - k}{k \; log \, k - k} \bigg)^k$$

My question (as a beginner in the probabilistic method) is how to derive $n = [k \; log \, k]$ and $|X| \leq log^2k - 10 \,log \,k\, log\,( log\,k) $.

I have attempted the usual method of finding minimum/maximum values for $\bigg(\frac{n-|X| - k}{n-k}\bigg)^k$, but this does not appear to work.

1

There are 1 best solutions below

1
On

These are not derived. They’re choices the author makes in order to prove Proposition $3.1$. Since $c_k$ is a bound that needs to hold for all $k$-uniform hypergraphs, the author is free to make arbitrary choices in proving a lower bound for $c_k$.