On the number of linear uniform hypergraphs with linear girth constraint

Abstract

For an integer $r⩾3$, a hypergraph on vertex set $[n]$ is $r$-uniform if each edge is a set of $r$ vertices, and is said to be linear if every two distinct edges share at most one vertex. Given a family $\mathcal{H}$ of linear $r$-uniform hypergraphs,let $For{b}_r^L(n,\mathcal{H})$ be the set of linear $r$-uniform hypergraphs on vertex set $[n]$, which does not contain any member from $\mathcal{H}$ as a subgraph. An $r$-uniform linear cycle of length $\ell$, denoted by $C_{\ell }^r$, is a linear $r$-uniform hypergraph on $(r-1)\ell$ vertices whose edges can be ordered as ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_{\ell }$ such that $|{\mathbf{e}}_i\cap {\mathbf{e}}_j|=1$ if $j=i\pm 1$ (indices taken modulo $\ell$) and $|{\mathbf{e}}_i\cap {\mathbf{e}}_j|=0$ otherwise. The linear girth of a linear $r$-uniform hypergraph is the smallest integer $\ell$ such that it contains a $C_{\ell }^r$. Let $For{b}_L(n,r,\ell )=For{b}_r^L(n,\mathcal{H})$ when $\mathcal{H}=\{C_i^r:3⩽i⩽\ell \}$, that is, $For{b}_L(n,r,\ell )$ is the set of all linear $r$-uniform hypergraphs on $[n]$ with linear girth greater than $\ell$. For integers $r⩾3$ and $\ell ⩾4$, Balogh and Li [On the number of linear hypergraphs of large girth, J. Graph Theory, 93(1) (2020), 113-141] showed that $|For{b}_L(n,r,\ell )|=2^{O(n^{1+1/\lfloor \ell /2\rfloor })}$ based on the graph container method. It is natural to obtain $|For{b}_L(n,r,\ell )|⩾2^{c\cdot n^{1+1/\ell }}$ for some constant $c$ by probabilistic deletion method. Combined with the known results that $|For{b}_L(n,r,3)|=2^{o(n^2)}$ and $|For{b}_L(n,3,4)|=2^{\hat{I}˜(n^{3/2})}$, by analyzing the random greedy high linear girth linear $r$-uniform hypergraph process, we show $|For{b}_L(n,r,\ell )|⩾2^{n^{1+1/(\ell -1)-O(\log \log n/\log n)}}$ for every pair of fixed integers $r,\ell ⩾4$, or $r=3$ and $\ell ⩾5$.