= Solution
We use the <random alteration method>, controlling large <hypergraph independent sets> and then removing the few forbidden overlaps. Fix $k=2005$, let $n$ tend to infinity, and independently include each three-element subset of an $n$-vertex set as an <hypergraph edge> with <probability> $p=n^{-7/4}$. Call the resulting three-<uniform hypergraph> $H_0$, and let $s=\lceil n/(2k)\rceil$.
For any prescribed $s$-vertex set, the <probability> that it is a <hypergraph independent set> is $(1-p)^{\binom s3}$. Hence the <union bound> gives
$$
\mathbb P\bigl(H_0\text{ has an independent set of size }s\bigr)
\leq\binom ns(1-p)^{\binom s3}
\leq\exp\bigl(n\log2-p\tbinom s3\bigr)\longrightarrow0,
$$
because $p\binom s3$ has order $n^{5/4}$, with a positive constant depending only on $k$.
Let $Y$ count <unordered pairs> of distinct <hypergraph edges> meeting in two vertices. Each potential pair consists of its common pair and two distinct additional vertices, so
$$
\mathbb E Y=\binom n2\binom{n-2}2p^2=O(n^{1/2}).
$$
The <Markov inequality> implies $\mathbb P(Y\geq n/2)=O(n^{-1/2})$. We may therefore fix one realization for which $Y<n/2$ and no $s$-vertex <hypergraph independent set> exists. For each offending <hypergraph edge> pair choose one vertex from its union, and let $D$ be the set of all chosen vertices. Delete $D$, together with all incident <hypergraph edges>, and call the induced <hypergraph> $H$. Then $|D|\leq Y<n/2$, so $N=|V(H)|>n/2$. The next two parts verify both desired properties of this same $H$.
Back to article page
