Proof. Each edge in $S_G$ has the form $e \cup \{e\}$ for some $e \in E$ , and $\left \vert e \cup \{e\} \right \vert = \left \vert e \right \vert + 1 = k$ . So $S_G$ is $k$ uniform.

For any pair of distinct edges $e_1 \cup \{e_1\}$ and $e_2 \cup \{e_2\}$ in $S_G$ , we have

\begin{equation*}\left \vert (e_1 \cup \{e_1\}) \cap (e_2 \cup \{e_2\}) \right \vert = \left \vert e_1 \cap e_2 \right \vert \leq 1.\end{equation*}

Thus $S_G$ is linear.

Finally, each vertex in $V$ has the same degree in $G$ and $S_G$ , while each element in $E$ has degree $1$ in $S_G$ . Therefore, the maximum degree of $S_G$ is the same as the maximum degree of $G$ .

Proof. Classifying the independence sets of $S_G$ based on their intersections with $V \subset V(S_G)$ , we have

\begin{equation*}Z_{S_G}(\lambda ) = \sum _{S \subset V} \sum _{I \in \mathcal {I}(S_G)\,:\, I \cap V = V \backslash S} \lambda ^{\left \vert I \right \vert }.\end{equation*}

A set of vertices $I \subset V \sqcup E$ with $I \cap V = V \backslash S$ is independent in $S_G$ if and only if $J \,:\!=\, I \cap E$ is contained in $E(S)$ . So we have

\begin{equation*}\sum _{I \in \mathcal {I}(S_G)\,:\, I \cap V = V \backslash S} \lambda ^{\left \vert I \right \vert } = \lambda ^{\left \vert V \backslash S \right \vert } \sum _{J \subset E(S)} \lambda ^{\left \vert J \right \vert } = \lambda ^{\left \vert V \backslash S \right \vert } (1 + \lambda )^{e(S)}\end{equation*}

and the lemma follows.

Proof. Set $\lambda _0 = -\frac {3\log n}{\alpha }$ . As $Z_{S_G}(0) = 1$ , it suffices to show that $Z_{S_G}(\lambda _0) \lt 0$ .

By Lemma2.3, we have the identity

\begin{equation*}Z_{S_G}(\lambda _0) = \sum _{S \subset V} \lambda _0^{\left \vert V \right \vert - \left \vert S \right \vert } (1 + \lambda _0)^{e(S)}.\end{equation*}

We isolate the term with $S = \emptyset$ and obtain

\begin{equation*}Z_{S_G}(\lambda _0) = \lambda _0^{\left \vert V \right \vert } \left (1 + \sum _{S \subset V, S \neq \emptyset } \lambda _0^{-\left \vert S \right \vert } (1 + \lambda _0)^{e(S)}\right )\end{equation*}

Since $0 \leq 1 + \lambda _0 \leq e^{\lambda _0}$ , for each $S \subset V$ we can estimate

\begin{equation*}\left \vert \lambda _0^{-\left \vert S \right \vert } (1 + \lambda _0)^{e(S)} \right \vert \leq \left \vert \lambda _0 \right \vert ^{-\left \vert S \right \vert } e^{\lambda _0 e(S)} \leq \alpha ^{\left \vert S \right \vert } e^{-3 \log n \cdot \left \vert S \right \vert }.\end{equation*}

Thus we have

\begin{equation*}\left \vert \sum _{S \subset V, S \neq \emptyset } \lambda _0^{-\left \vert S \right \vert } (1 + \lambda _0)^{e(S)} \right \vert \leq \sum _{k = 1}^n \binom {n}{k} \alpha ^{k} e^{-3 \log n \cdot k} \leq \sum _{k = 1}^n \frac {1}{k!} \left (\frac {\alpha }{n^2}\right )^k.\end{equation*}

where the second inequality uses the estimate $\binom {n}{k} \leq \frac {n^k}{k!}$ .

We assume that $\alpha \leq n$ , so $\left (\frac {\alpha }{n^2}\right )^k \lt \frac {1}{n}$ for each $k \geq 1$ . This leads to

\begin{equation*}\left \vert \sum _{S \subset V, S \neq \emptyset } \lambda _0^{-\left \vert S \right \vert } (1 + \lambda _0)^{e(S)} \right \vert \leq \frac {1}{n}\sum _{k = 1}^n \frac {1}{k!} \lt \frac {e}{n} \lt 1.\end{equation*}

Thus we conclude that

\begin{equation*}1 + \sum _{S \subset V, S \neq \emptyset } \lambda _0^{-\left \vert S \right \vert } (1 + \lambda _0)^{e(S)} \gt 0\end{equation*}

so $Z_{S_G}(\lambda _0) \lt 0$ , as desired.

Proof. We take a prime $p$ in $[\Delta, 2\Delta ]$ , which exists by Chebyshev’s theorem. Let $H_{k, \Delta }$ be the hypergraph on the vertex set $V = [k] \times \mathbb {Z}_p$ with an edge $\{(i, a + id)\,:\, i \in [k]\}$ for each pair $(a, d) \in \mathbb {Z}_p \times [\Delta ]$ . The number of vertices in $H_{k, \Delta }$ is $\left \vert V \right \vert = kp \leq 2 \Delta k$ .

Any vertex $(i, x) \in V$ is contained precisely in the edges corresponding to $(a, d) \in \mathbb {Z}_p \times [\Delta ]$ with $a \equiv x - id \pmod {p}$ . As there is exactly one $a \in \mathbb {Z}_p$ corresponding to each $d \in [\Delta ]$ , $H_{k, \Delta }$ is $\Delta$ regular.

The size of the intersection between two distinct edges corresponding to $(a, d)$ and $(a', d')$ is the number of solutions $i \in [k]$ to the linear congruence equation $a + id \equiv a' + id' \pmod {p}$ . As $k \leq \Delta \leq p$ , there is at most one solution $i \in [k]$ to this linear congruence equation, so every pair of hyperedges in $H_{k, \Delta }$ intersect in at most one vertex. Therefore, $H_{k, \Delta }$ is a linear hypergraph.

Proof of Theorem 1.2. Let $H = H_{(k - 1), \Delta }$ be the $(k - 1)$ uniform linear hypergraph constructed in Lemma2.5. If $H$ has an even number of vertices, we remove an arbitrary vertex $v$ of $H$ together with any edge containing the vertex. Thus, we obtain a $(k - 1)$ uniform linear hypergraph $H$ with an odd number of vertices, maximum degree $\Delta$ , and minimum degree at least $(\Delta - 1)$ . By Proposition2.2, $G = S_H$ is a $k$ uniform linear hypergraph with maximum degree $\Delta$ .

Let $n \leq 2k \Delta$ be the number of vertices in $H$ . For any vertex subset $S$ of $H$ , the $(k - 1)$ uniformity of $H$ implies that the number of edges in $G$ with at least one vertex in $S$ is lower bounded by

\begin{equation*}e(S) \geq \frac {1}{k - 1} \sum _{v \in S} d(v) \geq \frac {\Delta - 1}{k - 1} \left \vert S \right \vert .\end{equation*}

By our assumptions $\Delta \gt 100k^2$ and $n \leq 2k \Delta$ , we can check that

\begin{equation*}\frac {\Delta - 1}{k - 1} \gt \frac {\Delta }{k} \gt 10 \sqrt {\Delta } \gt 10 \log \Delta \gt 3 \log (2k\Delta ) \geq 3 \log (n).\end{equation*}

Furthermore, we have $\frac {\Delta - 1}{k - 1} \leq \Delta - 1 \lt n$ . So we can apply Lemma2.4 with $\alpha = \frac {\Delta - 1}{k - 1}$ . We conclude that $Z_{G}$ has a negative real zero $\lambda$ with

\begin{equation*}-\lambda \leq \frac {3\log n}{(\Delta - 1) / (k - 1)} \leq \frac {3 k \log (2\Delta k)}{\Delta } \leq \frac {6k \log \Delta }{\Delta }\end{equation*}

where the last two inequalities follow from $\Delta \gt 100k^2$ . So $G$ satisfies the requirements of Theorem 1.2.