Hence the number of possible $G\in \cI_2^*(n, \zeta, \vec\beta) \backslash \cI_3^*(n, \zeta, \vec\beta)$ is at most

\begin{align*}
&2^k {n\choose k}\cdot |\cI(n-k)|\cdot  \exp_2 \left[ O_k((\zeta+\beta_1)\log(1/(\zeta+\beta_1))){n \choose k-1}\right.\\
&\left.\hspace{5cm}+\left(H \left(\frac{1}{2^{k+1}}\right) + \frac{2^{k+1}-1}{2^{k+1}}\cdot \log_2 (2^k-1)\right) {n-k \choose k-1} \right]\\
&\overset{(*)}{<} \exp_2\left[k(1-c){n\choose k-1}\right]|\cI(n-k)|,
\end{align*}

where (*) holds since $\zeta$ is sufficiently smaller than $\theta_1$, and $c$ is small.

§.§ Most formulae in $\cI_3^*(n, \zeta, \vec \beta)$ are monotone

In this step, we bound the number of formulae in $\cI_{3}^*(n,\zeta,\vec\beta)$ that are not monotone. Before stepping into the proof, we first summarize some properties of every $G\in \cI_3^*(n,\zeta,\vec\beta)$ that will be useful subsequently.

* For every $k-1$ variables $v_1,\dots, v_{k-1}$, there are at most $\zeta n$ variables $w$ such that $v_1\cdots v_{k-1}\ol w\in G$. The same bound holds for $w$'s with $\ol v_1v_2\cdots v_{k-1}\ol w\in G$, $w$'s with $ v_1\ol v_2v_3 \cdots v_{k-1}\ol w\in G$,  $w$'s with $\ol v_1\ol v_2 v_3\cdots  v_{k-1}\ol w\in G$, and so on.

* For every $i\in \{1,\dots,k\}$, there are at most $\zeta n^{k}$ clauses in $G$ having exactly $i$ negative literals.

* For every $i\in\{1,\dots,k-2\}$ and $\{u_1,\dots,u_i\}\in{X\choose i}$, $G$ contains at most $\beta_in^{k-i}$ clauses of the form $\ol u_1\cdots\ol u_iv_1\cdots v_{k-i}$;

* For every $u_1,\dots,u_k\in X$, we have $|Z_{u_1}\cap\dots\cap Z_{u_k}|\geq \frac{1}{2^{k+1}} {n-k \choose k-1}$.

Define $\cI_{4}^*(n,\zeta,\vec\beta)$ to be the subset of monotone formulae in $\cI_{3}^*(n,\zeta,\vec\beta)$.

$$\cI_{4}^*(n,\zeta,\vec\beta)=\{G\in \cI_3^*(n, \zeta,\vec\beta):\text{$G$ is monotone}\}.$$

We give an upper bound on $|\cI_{3}^*(n,\zeta,\vec\beta)\setminus \cI_{4}^*(n,\zeta,\vec\beta)|$. The following observation about $\ell$-hypergraphs generalizes a theorem on graphs [16] (also see <cit.>), and will be useful in our proof.

Every $\ell$-uniform hypergraph $H$ can be directed (i.e., every edge directed at some vertex) such that for every $\ell-1$ vertices $v_1,\dots,v_{\ell-1}$, there are at most
$$\ceil{\frac{(\ell-1)!}{(\ell!)^\frac{\ell-1}{\ell}}\cdot e(H)^\frac{1}{\ell}}$$
edges that contain all of $v_1,\dots,v_{\ell-1}$ and are directed at a vertex $w$ other than $v_1,\dots,v_{\ell-1}$.

$$L:=\ceil{\frac{(\ell-1)!}{(\ell!)^\frac{\ell-1}{\ell}}\cdot e(H)^\frac{1}{\ell}}.$$

For an $\ell$-graph $H$, construct an associated bipartite graph $B_H$ in which one part is $E(H)$, the edge set of $H$, and the other part is the multiset $\left\{S^L:S\in {V(H)\choose \ell-1}\right\}$. For every $e\in E(H)$ and $S\in {V(H)\choose \ell-1}$, we define that $e\sim S$ in $B_H$ if and only if $S\subset e$. Observe that an edge direction of $H$ in which every $\ell-1$ vertices support at most $L$ edges directed at another vertex is equivalent to an $E(H)$-perfect matching in $B_H$, which exists if and only if $|W|\leq|N_{B_H}(W)|$ for every $W\subset E(H)$.

For every $W\subset E(H)$, $N_{B_H}(W)$ is the set of those $S\in {V(H)\choose \ell-1}$ that are contained in some $e\in W$. By the Kruskal–Katona theorem in the form of <ref>, every collection of $(\ell-1)$-vertex sets $\cS\subset{V(H)\choose \ell-1}$ covers at most $\frac{((\ell-1)!|\cS|)^\frac{\ell}{\ell-1}}{\ell!}$ $\ell$-edges, so every $W\subset E(H)$ satisfies

\begin{align*}
|W|&\leq \frac{\left((\ell-1)!\cdot\frac{|N_{B_H}(W)|}{L}\right)^\frac{\ell}{\ell-1}}{\ell!},\text{ and }\\
|N_{B_H}(W)|&\geq\frac{(\ell!)^\frac{\ell-1}{\ell}|W|^\frac{\ell-1}{\ell}}{(\ell-1)!}\cdot L\geq  \frac{(\ell!)^\frac{\ell-1}{\ell}|W|^\frac{\ell-1}{\ell}}{(\ell-1)!}\cdot \frac{(\ell-1)!}{(\ell!)^\frac{\ell-1}{\ell}}\cdot e(H)^\frac{1}{\ell}\\
&= |W|^\frac{\ell-1}{\ell}\cdot e(H)^\frac{1}{\ell}\geq |W|.\qedhere
\end{align*}

We will also use the following version of Shearer's inequality [8] (see also <cit.>).

Let $W$ be a set and $\cF$ a family of subsets of $W$. Let $\cH$ be a hypergraph with vertex set $W$, with $\deg_{\cH}(v)\geq k$ for every $v\in W$. Then

$$\log_2|\cF|\leq\frac{1}{k}\sum_{A\in \cH}\log_2|\Tr(\cF,A)|,$$

where  $\Tr(\cF,A)=\{F\cap A:F\in\cF\}$.

We now show that most $k$-SAT formulae in $\cI_3^*(\vec\beta,\zeta)$ are also in $\cI_4^*(\vec\beta,\zeta)$ for sufficiently small $\vec\beta, \zeta$.

We can choose $\vec \beta=(\beta_1,\dots,\beta_{k-2})$, $\zeta>0$ and $c > 0$ such that

$$|\cI_3^*(n, \zeta,\vec\beta)\setminus \cI_{4}^*(\zeta,\vec\beta)|< \exp_2\left[{n\choose k}-cn^{k-2}\right].$$

Choose sufficiently small $\vec \beta=(\beta_1,\dots,\beta_{k-2})$, $\zeta>0$ and $c=c(\vec \beta,\zeta) > 0$.

Observe that every $G\in \cI_3^*(n, \zeta,\vec\beta)$ cannot contain any clause with exactly $k-1$ negative literals. This is because if $\ol u_1\cdots\ol u_{k-1}v\in G$, then since there exists some $\{w_1,\dots,w_{k-1}\}\in Z_{u_1}\cap\dots\cap Z_{u_{k-1}}\cap Z_v$, $G$ would have a non-minimal suformula

$$\{w_1\cdots w_{k-1}v, w_1\cdots w_{k-1}u_1,\dots, w_1\cdots w_{k-1}u_{k-1}, w_1\cdots w_{k-1}v, \ol u_1\cdots\ol u_{k-1}v\}$$

(as it is impossible to satisfy only the first clause).

Next observe that the number of $G\in \cI_3^*(n, \zeta)$ containing a clause with exactly $k$ negative literals is at most $\exp_2[(1-c){n\choose k}]$. Indeed, if $\ol u_1\cdots\ol u_k\in G$, then for all $\{w_1,\dots, w_{k-1}\}\in\bigcap_{i=1}^kZ_{u_i}$, to avoid the non-minimal subformula

$$\{w_1\cdots w_{k-1}v, w_1\cdots w_{k-1}u_1,\dots,w_1\cdots w_{k-1}u_k, \ol u_1\cdots\ol u_k\}$$

(as it is impossible to satisfy only the first clause), there cannot be any $v\in X\setminus \{u_1,\dots,u_k\}$ such that $w_1\cdots w_{k-1}v\in G$. Hence after specifying $u_1,\dots,u_k$ and $\bigcap_{i=1}^kZ_{u_i}$, we know at least
$$\frac{1}{k}\cdot (n-2k+1)\left|\bigcap_{i=1}^kZ_{u_i}\right|\geq \frac{n-2k+1}{k\cdot 2^{k+1}}{n-k\choose k-1}$$

monotone clauses that cannot belong to $G$. We can specify such $G$ in the following manner.

* We choose $u_1, \ldots, u_k$. There are at most ${n\choose k}$ choices.

* We choose $\bigcap_{i=1}^kZ_{u_i}$. This can be done in at most $2^{{n\choose k-1}}$ ways.

* We choose the non-monotone clauses in $G$. The number of choices is bounded above by $\exp_2\left[O_k(\zeta\log(1/\zeta)){n\choose k}\right]$.

* Finally, we pick the monotone clauses in $G$, of which the number of choices is bounded above by
$$\exp_2\sqb{{n\choose k}-\frac{n-2k+1}{k\cdot 2^{k+1}}{n-k\choose k-1}}.$$

Hence the number of possible $G$ is at most

$${n\choose k}\cdot 2^{{n\choose k-1}}\cdot \exp_2\left[O_k(\zeta\log(1/\zeta)){n\choose k}+{n\choose k}-\frac{n-2k+1}{k\cdot 2^{k+1}}{n-k\choose k-1}\right]\overset{(*)}{\leq} \exp_2\sqb{(1-c){n\choose k}},$$

where (*) is due to the fact that $\zeta$ and $c$ are sufficiently small.

Finally, we bound the number of $G\in \cI_3^*(n, \zeta,\vec\beta)\setminus \cI_4^*(n, \zeta,\vec\beta)$ containing no clause with exactly $k-1$ or $k$ negative literals. For every such $G$, we decompose $G=G_0\sqcup G_1\sqcup \dots\sqcup G_{k-2}$, such that every $G_i$ is the set of clauses in $G$ with exactly $i$ negative literals. Observe that $|G_1|,\dots,|G_{k-2}|\leq \zeta n^k$ as $G\in \cI^*(n, \zeta)$. We will prove in a second that:

For all $t_1,\dots,t_{k-2}\leq \zeta n^k$, we have

\begin{align*}
& \left|\left\{G\in \cI_3^*(n, \zeta,\vec\beta)\setminus \cI_4^*(n, \zeta,\vec\beta):\text{$G$ contains no clause with exactly $k$ negative literals, }\right.\right.\\
&\left.\left.\qquad\qquad\qquad\qquad\qquad\qquad\qquad |G_1|=t_1,\dots, |G_{k-2}|=t_{k-2} \right\}\right|\\
& <\exp_2\left[{n\choose k}-2cn^{n-2}\right].
\end{align*}

Since the number of choices of $t_1,\dots,t_{k-2}$ is at most $(\zeta n^k)^{k-2}$, given <ref>, we know that there are at most $(\zeta n^k)^{k-2}\cdot \exp_2\left[{n\choose k}-2cn^{k-2}\right]$ formulae in $|\cI_3^*(n, \zeta,\vec\beta)\setminus \cI_4^*(n, \zeta,\vec\beta)|$ containing no clause with exactly $k-1$ or $k$ negative literals. Combining this with the previous two observations, we have the desired bound

\begin{align*}
|\cI_3^*(n, \zeta,\vec\beta)\setminus \cI_4^*(n, \zeta,\vec\beta)|&\leq (\zeta n^k)^{k-2}\cdot \exp_2\left[{n\choose k}-2cn^{k-2}\right]+\exp_2\left[(1-c){n\choose k}\right]\\
&\leq \exp_2\left[{n\choose k}-cn^{k-2}\right].
\end{align*}

Consider some $G\in \cI_3^*(n, \zeta,\vec\beta)\setminus \cI_4^*(n, \zeta,\vec\beta)$ such that $G$ contains no clause with exactly $k-1$ or $k$ negative literals, and $|G_1|=t_1$,…, $|G_{k-2}|=t_{k-2}$.

For every $i\in[k-2]$, we construct an auxiliary collection $G_i'\subset {X\choose i}\times {X\choose k-i-1}\times X$ based on $G_i$, by doing the following: for every clause $\ol u_1\cdots\ol u_iv_1\cdots v_{k-i}\in G_i$, we pick one $j\in\{1,\dots,k-i\}$ and put the element $(\{u_1,\dots,u_i\},\{v_1,\dots,v_{j-1},v_{j+1},\dots, v_{k-i}\},v_j)$ in $G_i'$. In other words, we obtain $G_i'$ from $G_i$ by making the set of positive literals in every clause “directed" at some $v_j$.

There are clearly many ways to build $G_i'$. We claim that there exists some $G_i'$ such that for every $u_1,\dots,u_i\in X$ and $v_1,\dots,v_{k-i-1}\in X\setminus\{u_1,\dots,u_i\}$, there are at most
$$\ceil{\frac{(k-i-1)!}{((k-i)!)^\frac{k-i-1}{k-i}}\cdot \beta_i^\frac{1}{k-i}\cdot n}$$
elements of the form $(\{u_1,\dots,u_i\},\{v_1,\dots,v_{k-i-1}\},w)$. For every $u_1,\dots,u_i\in X$, define the $(k-i)$-hypergraph $H$ by

\begin{align*}
E(H)&=\{\{v_1,\dots,v_{k-i}\}:\ol u_1\cdots\ol u_iv_1\cdots v_{k-i}\in G_i\}.
\end{align*}

Since $G$ contains at most $\beta_in^{k-i}$ clauses of the form $\ol u_1\dots\ol u_iv_1\dots v_{k-i}$, we have $e(H)\leq \beta_in^{k-i}$, so by <ref> we know that $H$ can be directed such that every $v_1,\dots,v_{k-i-1}\in X\setminus\{u_1,\dots,u_i\}$ are contained in at most $\ceil{\frac{(k-i-1)!}{((k-i)!)^\frac{k-i-1}{k-i}}\cdot \beta_i^\frac{1}{k-i}\cdot n}$ edges directed at some other vertex. This gives us the $G_i'$ as wanted.

Now we fix this $G_i'$. Define the $(i+1)$-multigraph $H_i$ by

\begin{align*}
V(H_i)&={X\choose k-i},\\
E(H_i)&=\{\{\{u_1,v_1,\dots,v_{k-i-1}\},\dots, \{u_i,v_1,\dots,v_{k-i-1}\},\{w,v_1,\dots,v_{k-i-1}\}\}:
\\&\hspace{6cm} (\{u_1,\dots,u_i\},\{v_1,\dots,v_{k-i-1}\},w)\in G_i'\}.
\end{align*}

For every $e=\{\{u_1,v_1,\dots,v_{k-i-1}\},\dots, \{u_i,v_1,\dots,v_{k-i-1}\},\{w,v_1,\dots,v_{k-i-1}\}\}\in E(H_i)$ and any other $i$ variables $a_1,\dots,a_i\notin\{u_1,\dots, u_i,v_1,\dots,v_{k-i-1},w\}$, since $\ol u_1\cdots \ol u_{i}v_1\cdots v_{k-i-1}w\in G_i$, to avoid the non-minimal subformula

$$\{v_1\cdots v_{k-i-1}a_1\cdots a_iw, v_{1}\cdots v_{k-i-1}a_1\cdots a_iu_1,\dots, v_1\cdots v_{k-i-1}a_1\cdots a_iu_i,\ol u_1\cdots \ol u_{i}v_1\cdots v_{k-i-1}w\}$$

(as it is impossible to satisfy only the first clause), we have

$$G_0\cap \{v_1\cdots v_{k-i-1}a_1\cdots a_iw, v_{1}\cdots v_{k-i-1}a_1\cdots a_iu_1,\dots, v_1\cdots v_{k-i-1}a_1\cdots a_iu_i\}<i+1.$$

Define the formula $F(e,a_1,\dots,a_i)$ by

$$F(e,a_1,\dots,a_i)=\{v_1\cdots v_{k-i-1}a_1\cdots a_iw, v_{1}\cdots v_{k-i-1}a_1\cdots a_iu_1,\dots, v_1\cdots v_{k-i-1}a_1\cdots a_iu_i\}.$$

We also observe that given any vertex $\mathbf v\in V(H_i)$, we have

$$\deg_{H_i}(\mathbf v)\leq (k-i)\left({n\choose i-1}\cdot\ceil{\frac{(k-i-1)!}{((k-i)!)^\frac{k-i-1}{k-i}}\cdot \beta_i^\frac{1}{k-i}\cdot n}+{n\choose i-1}\cdot\zeta n\right).$$

This is because when $\mathbf v$ takes the role of (say) $\{u_1,v_1,\dots,v_{k-i-1}\}$ in an edge, to identify an edge containing $\mathbf v$, it suffices to:

* identify $u_1$ from the $k-i$ variables in $\mathbf v$;

* choose $u_2,\dots,u_i\in X$ from at most ${n\choose i-1}$ choices;

* choose $w$ from at most $\ceil{\frac{(k-i-1)!}{((k-i)!)^\frac{k-i-1}{k-i}}\cdot \beta_i^\frac{1}{k-i}\cdot n}$ choices, according to the property of $G_i'$.

When $\mathbf v$ takes the role of $\{w,v_1,\dots,v_{k-i-1}\}$ in an edge, to identify an edge containing $\mathbf v$, it suffices to:

* identify $w$ from the $k-i$ variables in $\mathbf v$;

* choose the lexicographically smallest $i-1$ variables among $u_1,\dots, u_i$ from at most ${n\choose i-1}$ choices;

* choose the remaining variable from at most $\zeta n$ choices, according to <ref>.

Let $\nu_i$ and $\tau_i$ denote the matching and vertex cover numbers of $H_i$. Choose $\rho_i>0$ sufficiently small, yet still larger than $\beta_i$ and $\zeta$ such that we have the degree bound

$$\deg_{H_i}(\mathbf v)\leq (k-i)\left({n\choose i-1}\cdot\ceil{\frac{(k-i-1)!}{((k-i)!)^\frac{k-i-1}{k-i}}\cdot \beta_i^\frac{1}{k-i}\cdot n}+{n\choose i-1}\cdot\zeta n\right)\leq\rho_in^i$$

for every $\mathbf v\in V(H_i)$. We then have the  inequalities
$$(i+1)\nu_i\geq\tau_i\geq\frac{t_i}{\rho_i n^i}.$$

Given $t_i$, $\nu_i$ and $\tau_i$, the number of possible $G_i$ is bounded by the product of:

* ${{n\choose k-i}\choose \tau_i}\leq {n^{k-i}\choose\tau_i}$ (choosing a vertex cover $\mathcal T_i$ of $H_i$);

* ${{k\choose i}\tau_i{n\choose i}\choose t_i}$ (choosing a collection of $t_i$ clauses, each using at least one member of $\mathcal T_i$).

Suppose $G_1,\dots,G_{k-2}$ have been determined and consider the number of possible $G_0$. Let $\mathcal M_i$ be some maximum matching of $H_i$; say $\mathcal M_i=\{e_j:j\in[\nu_i]\}$.
Define the family of monotone formulae $\mathcal J_i$ by

\begin{align*}
\mathcal J_i&=\bigcup_{j=1}^{\nu_i}\{F(e_j,a_1,\dots,a_i):a_1,\dots,a_i\notin\{u_1,\dots, u_i,v_1,\dots,v_{k-i-1},w\}\\
& \qquad\qquad\text{ with }e_j=\{\{u_1,v_1,\dots,v_{k-i-1}\},\dots, \{u_i,v_1,\dots,v_{k-i-1}\},\{w,v_1,\dots,v_{k-i-1}\}\}\}.
\end{align*}

For every possible $G_0$ and every $F(e_j,a_1,\dots,a_i)\in \mathcal J_i$, we have $|G_0\cap F(e_j,a_1,\dots,a_i)|< i+1.$
Moreover, since every $F(e_j,a_1,\dots,a_i)$ is of the form $\{y_1\cdots y_{k-1}z_1,\dots, y_1\cdots y_{k-1}z_{i+1}\}$, and every formula of the form $\{y_1\cdots y_{k-1}z_1,\dots, y_1\cdots y_{k-1}z_{i+1}\}$ can come from at most ${k-1\choose i}$ different  $e_j\in\mathcal M_i$, we have

$$|\mathcal J_i|\geq\frac{\nu_i{n-k\choose i}}{{k-1\choose i}}.$$

Let $\mathcal H$ be a (non-uniform) multigraph, whose vertex set is the set of all monotone clauses on variable set $X$, and whose edge set is the union of all $\mathcal J_i$ and a number of single-clause formulae, such that every monotone clause lies in exactly $\sum_{i=1}^{k-2}{k-1\choose i}$ edges. In other words, we have

\begin{align*}
V(\mcH)={X\choose k},\qquad
E(\mcH)=\left(\bigcup_{i=1}^{k-2}\mathcal J_i\right)\cup\left(\bigcup_{C\in {X\choose k}}\{C\}^{\sum_{i=1}^{k-2}\left({k-1\choose i}-\eta_i(C)\right)}\right),
\end{align*}

where $\eta_i(C)\leq {k-1\choose i}$ is the number of edges in $\mathcal J_i$ that contain $C$.  Notice that every vertex in $\cH$ has degree exactly $\sum_{i=1}^{k-2}{k-1\choose i}$.

Let $\mathcal G_{0}$ be the collection of all possible $G_0$. By <ref>, we have

$$\log_2|\mathcal G_{0}|\leq  \left(\sum_{i=1}^{k-2}{k-1\choose i}\right)^{-1}\sum_{F\in \mathcal J_i} \log_2|\Tr(\cG_0,F)|=\left(2^{k-1}-2\right)^{-1}\sum_{F\in \mathcal J_i} \log_2|\Tr(\cG_0,F)|.$$
For all $F(e_j,a_1,\dots,a_i)\in \mathcal J_i$, since $|G_0\cap F(e_j,a_1,\dots,a_i)|< i+1$ for all $G_0\in \mathcal G_{0}$, we have $|\text{Tr}(\mathcal G_{0},F(e_j,a_1,\dots,a_i))|\leq 2^{i+1}-1$. Since we also have all $\text{Tr}\left(\mathcal G_0,\{T\}^{\sum_{i=1}^{k-2}\left({k-1\choose i}-\eta_i(T)\right)}\right)\leq 2$, it follows that

\begin{align*}
\log_2|\mathcal G_{0}|
&\leq \left(2^{k-1}-2\right)^{-1}\left(\sum_{C\in {V\choose k}}\sum_{i=1}^{k-2}\left({k-1\choose i}-\eta_i(C)\right)+\sum_{i=1}^{k-2}|\mathcal J_i|\log_2(2^{i+1}-1)\right)\\
&\overset{(*)}{=}{n\choose k}-\left(2^{k-1}-2\right)^{-1}\left(\sum_{i=1}^{k-2}(i+1-\log_2(2^{i+1}-1))|\mathcal J_i|\right)\\
&\overset{(**)}{\leq} {n\choose k}-\left(2^{k-1}-2\right)^{-1}\left(\sum_{i=1}^{k-2}\frac{(i+1-\log_2(2^{i+1}-1)){n-k\choose i}\nu_i}{{k-1\choose i}}\right)\\
&\overset{(***)}{\leq} {n\choose k}-\left(2^{k-1}-2\right)^{-1}\left(\sum_{i=1}^{k-2}\frac{(i+1-\log_2(2^{i+1}-1)){n-k\choose i}\tau_i}{(i+1){k-1\choose i}}\right)
\end{align*}

where (*) is because $\sum_{T\in {V\choose k}}\eta_i(T)=(i+1)|\mathcal J_i|$, (**) is because $|\mathcal J_i|\geq\frac{\nu_i{n-k\choose i}}{{k-1\choose i}}$, and (***) is because $\frac{\tau_i}{i+1}\leq\nu_i$. For every $i\in\{1,\dots, k-1\}$, set
$$\delta_i=\left(2^{k-1}-2\right)^{-1}\cdot \frac{i+1-\log_2(2^{i+1}-1)}{(i+1){k-1\choose i}}>0.$$

Given all the $t_i$, $\nu_i$ and $\tau_i$ for $i\in\{1,\dots,k-2\}$, combining the above with the previous observation that there are at most ${n^{k-i}\choose\tau_i}{{k\choose i}\tau_i{n\choose i}\choose t_i}$ possible $G_i$, we obtain that the number of possible $G\in\cI_3^*(n, \zeta,\vec\beta)\setminus \cI_4^*(n, \zeta,\vec\beta)$  is at most

\begin{align*}
&\exp_2\left[{n\choose k}-\left(\sum_{i=1}^{k-2}\delta_i{n-k\choose i}\tau_i\right)\right]\cdot \prod_{i=1}^{k-2}{n^{k-i}\choose\tau_i}{{k\choose i}\tau_i{n\choose i}\choose t_i}\\
&\leq\exp_2\left[{n\choose k}+\sum_{i=1}^{k-2}\left(O_k(\log n)\tau_i+H\left(\frac{t_i}{{k\choose i}\tau_i{n\choose i}}\right)\tau_in^i-\delta_i{n-k\choose i}\tau_i\right)\right]\\
&\overset{(*)}{\leq} \exp_2\left[{n\choose k}+\sum_{i=1}^{k-2}\left(O_k(\log n)+H\left(\frac{\rho_i\cdot 2(i!)}{{k\choose i}}\right)n^i-\delta_i{n-k\choose i}\right)\tau_i\right]\\
&\leq \exp_2\left[{n\choose k}-3cn^{k-2}\right],
\end{align*}

where (*) is due to the fact that $\tau_i\geq\frac{t_i}{\rho_i n^i}$. For every $i\in\{1,\dots,k-2\}$, there are at most $\frac{{n\choose k-i}}{i+1}$ possible values of $\nu_i$ and at most ${n\choose k-i}$ possible values of $\tau_i$. Hence the number of possible $G\in\cI_4^*(n, \zeta,\vec\beta)$ given $t_1,\dots,t_{k-2}$ is at most $\exp_2\left[{n\choose k}-3cn^{k-2}\right]\cdot\left(\prod_{i=1}^{k-2}\frac{{n\choose k-i}}{i+1}{n\choose k-i}\right)\leq \exp_2\left[{n\choose k}-2cn^{k-2}\right]$.

§.§ Bound on $|\cI^*(n, \zeta)|$

Decomposing $\cI^*(n, \zeta)$, we have

\begin{align*}
|\cI^*(n, \zeta)|
&\leq |\cI^*(n, \zeta)\setminus\cI_1^*(n, \zeta, \beta_1)|+|\cI_1^*(n, \zeta, \beta_1)\setminus\cI_2^*(n, \zeta,\vec\beta)| + |\cI_2^*(n, \zeta,\vec\beta)\setminus\cI_3^*(n, \zeta,\vec\beta)|\\ &+|\cI_3^*(n, \zeta,\vec\beta)\setminus\cI_4^*(n, \zeta,\vec\beta)|+|\cI_4^*(n, \zeta,\vec\beta)|.
\end{align*}

Recall that we have the following inequalities from a combination of <ref>, <ref>, <ref>, <ref> and <ref>, where $\vec \beta > 0$ chosen so that $\beta_1$ is sufficiently small (in general and also with respect to $\beta_2, \ldots \beta_k$), $\zeta > 0$ is sufficiently small relative to $\vec \beta$, and $c'> c > 0$ are constants chosen to be small relative to $\zeta$ and $\vec \beta$.

|^*(n, ζ)∖_1^*(n, ζ)|      ≤exp_21/2n-1k-1(n-1),

|_1^*(n, ζ, β_1)∖_2^*(n, ζ,β⃗)|    ≤(k-2)exp_2(1-c')nk+exp_2(1-c')nk-1|(n-1)|

|_2^*(n, ζ,β⃗)∖_3^*(n, ζ,β⃗)|      ≤exp_2k(1-c')nk-1|(n-k)|,

|_3^*(n, ζ,β⃗)∖_4^*(n, ζ,β⃗)|    ≤exp_2nk-c'n^k-2,

|_4^*(n, ζ,β⃗)|    ≤2^nk.

Combining the above inequalities gives the desired upper bound.

|^*(n, ζ)|      ≤2^nk+exp_2(1-c)nk+∑_i=1^k-2exp_2i(1-c)nk-1|(n-i)|

exp_2(1-c)knk-1 |(n-k)|+exp_2nk-cn^k-2.

This immediately gives the desired tight asymptotic.

Choose some $\theta>\log_23$ with $\pi(\cF_k,\theta)= 1$ and some $\zeta<\zeta_0$ as in <ref>. We then choose $\epsilon>0$ as in <ref>.

Recall from <ref> that for $n$ sufficiently large, we have

$$|\cI(n)|\leq  2^{\left(1-\epsilon\right)\binom{n}{k}} + 2^{n} \abs{\cI^*(n, \zeta)}.$$

Then, substituting the bound in <ref>, we obtain by induction that for some constant $\Delta,c_0>0$ and all $n$,

\begin{equation}\label{eq:strongub}
\abs{\cI(n)}\leq (1+\Delta\cdot 2^{-c_0n})B(n),
\end{equation}

where $B(n)=2^{{n\choose k}+n}$.

[1]
Peter Allen, Almost every 2-SAT function is unate, Israel J. Math.
161 (2007), 311–346.

[2]
József Balogh, Neal Bushaw, Maurício Collares, Hong Liu, Robert
Morris, and Maryam Sharifzadeh, The typical structure of graphs with no
large cliques, Combinatorica 37 (2017), 617–632.

[3]
József Balogh, Robert Morris, and Wojciech Samotij, Independent sets
in hypergraphs, J. Amer. Math. Soc. 28 (2015), 669–709.

[4]
József Balogh, Robert Morris, and Wojciech Samotij, The method of
hypergraph containers, Proceedings of the International Congress of
Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures,
World Sci. Publ., Hackensack, NJ, 2018, pp. 3059–3092.

[5]
József Balogh and Wojciech Samotij, An efficient container lemma,
Discrete Anal. (2020), Paper No. 17, 56pp.

[6]
Béla Bollobás and Graham R. Brightwell, The number of $k$-SAT
functions, Random Structures Algorithms 22 (2003), 227–247.

[7]
Béla Bollobás, Graham R. Brightwell, and Imre Leader, The number
of 2-SAT functions, Israel J. Math. 133 (2003), 45–60.

[8]
F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer, Some
intersection theorems for ordered sets and graphs, J. Combin. Theory Ser. A
43 (1986), 23–37.

[9]
George E. Collins, Quantifier elimination for real closed fields by
cylindrical algebraic decomposition, Automata theory and formal languages
(Second GI Conf., Kaiserslautern, 1975), 1975, pp. 134–183.

[10]
P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs
not containing a fixed subgraph and a problem for hypergraphs having no
exponent, Graphs Combin. 2 (1986), 113–121.

[11]
P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic
enumeration of $K_{n}$-free graphs, Colloquio Internazionale sulle
Teorie Combinatorie (Rome, 1973), Tomo II, 1976, pp. 19–27.

[12]
Zoltán Füredi, The maximum number of edges in a minimal graph of
diameter $2$, J. Graph Theory 16 (1992), 81–98.

[13]
Zoltán Füredi and Zeinab Maleki, The minimum number of triangular
edges and a symmetrization method for multiple graphs, Combin. Probab.
Comput. 26 (2017), 525–535.

[14]
Zoltán Füredi, Oleg Pikhurko, and Miklós Simonovits, On
triple systems with independent neighbourhoods, Combin. Probab. Comput.
14 (2005), 795–813.

[15]
Vytautas Gruslys and Shoham Letzter, Minimizing the number of triangular
edges, Combin. Probab. Comput. 27 (2018), 580–622.

[16]
S. L. Hakimi, On the degrees of the vertices of a directed graph, J.
Franklin Inst. 279 (1965), 290–308.

[17]
L. Ilinca and J. Kahn, On the number of 2-SAT functions, Combin.
Probab. Comput. 18 (2009), 749–764.

[18]
L. Ilinca and J. Kahn, The number of 3-SAT functions, Israel J. Math.
192 (2012), 869–919.

[19]
Jeff Kahn, An entropy approach to the hard-core model on bipartite
graphs, Combin. Probab. Comput. 10 (2001), 219–237.

[20]
G. Katona, A theorem of finite sets, Theory of graphs (Proc.
Colloq., Tihany, 1966), 1968, pp. 187–207.

[21]
Manuel Kauers, How to use cylindrical algebraic decomposition, Sém.
Lothar. Combin. 65 (2010/12), Art. B65a, 16.

[22]
Peter Keevash, Hypergraph Turán problems, Surveys in combinatorics
2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press,
Cambridge, 2011, pp. 83–139.

[23]
Joseph B. Kruskal, The number of simplices in a complex, Mathematical
optimization techniques, Univ. of California Press, Berkeley, Calif., 1963,
pp. 251–278.

[24]
Brendan D. McKay, Practical graph isomorphism, (1981), pp. 45–87.

[25]
Brendan D. McKay, Practical graph isomorphism II, J. Symbolic Comput. 60 (2014), pp. 94–112.

[26]
David Saxton and Andrew Thomason, Hypergraph containers, Invent. Math.
201 (2015), 925–992.

[27]
Alexander Schrijver, Combinatorial optimization. Polyhedra and
efficiency, Springer-Verlag, Berlin, 2003.

§ BRUTE FORCE VERIFICATION OF CONJECTURE <REF> FOR $K=5$ (BY NITYA MANI AND EDWARD YU)

§.§ Overview

As observed in Remark <ref>, to verify that $\pi(\mcF_k, \theta) = 1$ for some fixed $k$ and some $\theta > \log_2 3$,
it suffices to show that for some constant $n > k$, $\alpha(\vec{H}) + (\log_2 3) \beta(\vec{H}) \le 1$ over all $\vec T_k$-free $k$-PDGs $\vec{H}$ on exactly $n$ vertices (with $\alpha(\vec H)\binom{n}{k}$ undirected edges and $\beta(\vec H)\binom{n}{k}$ directed edges).

This is a finite check for any fixed $k$. The new result for 5-SAT relies on $(n,k)=(7,4)$, which took 6600 CPU hours (in parallel) after several optimizations. We describe the algorithm used to efficiently enumerate $7$-vertex $4$-PDGs and verify they were $\vec T_4$-free. The complete, documented code (along with installation and running instructions) can be found at <https://github.com/ThinGarfield/Density-k-PDG/tree/v10.1>.

Using this code, we computed for the following pairs $(n, k)$, the largest value of $\theta$ (which appears in the corresponding table entry) such that $\alpha(\vec{H}) + \theta \beta(\vec{H}) \le 1$ for all $n$-vertex $\vec T_k$-free $k$-PDGs $\vec{H}$.

$n$       2     3     4     5     6     7
2     1

3     $3/2$     1

4     $3/2$     $4/3$     1

5     $5/3$     $5/3$     $5/4$     1

6     $5/3$     $5/3$     $3/2$     $6/5$     1

7     $7/4$     $7/4$     $\mathbf{7/4}$     $7/5$     $7/6$     1

8     $7/4$     ?     ?     8/5     $4/3$     $8/7$

In the above table, the $(n,k)=(8,5)$ entry does not follow by computation (indeed, the projected size of such a calculation using our methods would be far beyond any reasonable computational resources). Rather, this follows by way of using the $(n,k)=(7,4)$ case as in Proposition <ref> to observe that $\pi(\vec{T}_5, 8/5) \le 1$ and finding a $\vec{T}_5$-free $8$ vertex graph $\vec H$ with only directed edges where $\alpha(\vec{H}) + \frac85 \beta(\vec{H}) = \frac85 \beta(\vec{H}) = 1$.

§.§ $n = 7, k =4$

Our computation enables us to verify Conjecture <ref> for $k = 5$.

We have that $\pi(\vec T_5, \theta) = 1$ for some $\theta > \log_2 3 $. Consequently the number of $5$-SAT functions is $(1 + o(1))2^{n + {n \choose k}}$.

By computation (described in more details in the following sections), we verify that for all $7$-vertex $\vec T_4$-free graphs $\vec{H}$, $\alpha(\vec{H}) + \frac74 \beta(\vec{H}) \le 1$. This is a tight estimate for $n = 7$, achieved by the following $4$-PDG:

\begin{align*}
\vec{H} = ([7],\{&123\wc6, 124\wc6,134\wc6, 234\wc6, 125\wc6,135\wc6, 235\wc6, 145\wc6, 245\wc6,\\
&123\wc7, 124\wc7,134\wc7, 234\wc7, 125\wc7,135\wc7, 235\wc7, 145\wc7, 245\wc7\})
\end{align*}

By subsampling, this verifies that $\pi(\vec{T}_4, 7/4) = 1$. Applying Lemma <ref>, we find that

$$1 \ge \pi(\vec T_4, 7/4)
\ge \pi\left(\vec T_5, \frac{4 \cdot 7/4 + 1}{5} \right)
= \pi(\vec T_5, 8/5).$$

Taking $\theta = 8/5 > \log_2 3$, the desired result  follows from Theorem <ref>.

§.§ Compute environment

We implement this search in C++ 17 (specific details about the development environment and installation can be found in the code README).

We use the Google Cloud Platform Compute Engine to enumerate $k$-PDGs. Below we summarize the runtime for fixed $n, k$ of computing the maximal $\theta$ such that $\alpha(\vec{H}) + \theta \beta(\vec{H}) \le 1$ for all $n$-vertex, $\vec T_k$-free $k$-PDGs.

* $n = 7, k = 3$ took  880 CPU hours

* $n = 7, k = 4$ (the primary desired case) took  6600 CPU hours in 30 batches, checking 29313 base graphs (described in more detail in the following subsection)

* $n = 7, k = 5$ took a few minutes on a regular computer

* $n = 8, k =5$ is not computationally tractable with the current algorithm (would require $\sim 10^{15}$ CPU hours with the current implementation and checking 4722759 base graphs). We think $n = 9, k =5$, an even more expensive computation, is the minimum $n$ that might verify Conjecture <ref> for $k = 6$.

* $n = 8, k = 6$ took  200 CPU hours

§.§ Algorithm

We outline the algorithm below. Further documentation and associated testing can be found in the codebase.

Principally, we enumerate in a way to reduce the number of “base $k$-PDGs” that must be checked by growing a search tree of $k$-PDGs and eliminate unnecessary steps in computation. These optimizations are crucial for making the problem more computationally tractable.

* Initialization: Let $\mcG_{k-1}$ be the set comprising the single PDG formed by taking a collection of vertices $\{1, \ldots, k-1\}$ with no edges.

* For $\ell \in \{k, k+1, \ldots, n-1\}$:

* Initialize $\mcG_{\ell} := \left\{(V(\vec{G}) \cup \{\ell\}, E(\vec{G})) : \vec{G} \in \mcG_{\ell-1}\right\}$

* For each $\vec{G} \in \mcG_{\ell}$:

* Consider all possible combinations of edges (undirected or directed towards any vertex) that could be added to each $\vec{G} \in \mcG_{\ell}$ that include vertex $\ell$. Let $\mcE_{\ell}$ be the collection of possible edge sets to add.

* For each potential collection of edges $F \in \mcE_{\ell}$, consider candidate $\vec{H}_F = (V(\vec{G}), E(\vec{G}) \cup F)$, and check if $\vec{H}$ is $\vec T_k$-free. If not, discard the associated $\vec{H}_F$. If so, express $\vec{H}_F$ in a canonical form, which is a representation chosen to ease in tracking non-isomorphic $k$-PDGs.

* For each $\vec T_k$-free $\vec{H}_F$ not isomorphic to some existing element in $\mcG_{\ell}$, add $\vec{H}_F$ to $\mcG_{\ell}$.

* Sort $\mcG_{\ell}$ with respect to the canonical form.

* Repeat the above process for $\ell = n$, but this time do not represent PDGs in canonical form or check for isomorphisms (but verify that the $k$-PDGs in $\mcG_n$ are $\vec T_k$-free)

* Return the maximum value of $\theta$ such that for all $\vec{H} \in \mcG_n$, $\alpha(\vec{H}) + \theta \beta(\vec{H}) \le 1$.

There are several implemented optimizations (verified by a variety of tests, outlined in the code ) that make the above algorithm computationally tractable. We outline some of the most important ones below.

* We represent $k$-PDGs with a data structure that contains edges, vertex signatures, and a graph hash without pointer indirections, representing edges with a 16-bit struct. This representation makes it faster to verify that a $k$-PDG is $\vec T_k$-free, check for isomorphisms, and copy and grow $k$-PDGs.

* As we grow our classes $\mcG_{\ell}$, for every $\vec{G} \in \mcG_{\ell}$ we keep track of the largest $\theta$ such that $\alpha(\vec{G}) + \theta \beta(\vec{G}) \le 1$.

* We use bit mask manipulation and a bit representation of edges to efficiently verify if a $k$-PDG is $\vec T_k$-free. We also attempt to limit the number of supersets of edge sets that contain a copy of $\vec T_k$ that are checked.

* We adapt some graph isomorphism checking strategies [24, 25] to $k$-PDGs by hashing degree information of vertices in a current $k$-PDG in a permutation invariant way (which is maintained via a canonical form to represent $k$-PDGs). We call this hash the vertex signature. We also compute a whole $k$-PDG graph hash. These steps make it easier to verify if two $k$-PDGs are isomorphic (although both of these sets of hashes could match for non-isomorphic $k$-PDGs, in which case we check for the $k$-PDGs being identical as we walk through permutations that align in vertex signature).