Counting Hypergraphs with Large Girth

Abstract

Morris and Saxton used the method of containers to bound the number of $n$-vertex graphs with $m$ edges containing no $\ell$-cycles, and hence graphs of girth more than $\ell$. We consider a generalization to $r$-uniform hypergraphs. The {\em girth} of a hypergraph $H$ is the minimum $\ell$ such that for some $F\subseteq H$, there exists a bijection $\varphi :E(C_{\ell })\to E(F)$ with $e\subseteq \varphi (e)$ for all $e\in E(C_{\ell })$. Letting $N_m^r(n,\ell )$ denote the number of $n$-vertex $r$-uniform hypergraphs with $m$ edges and girth larger than $\ell$ and defining $\lambda =\lceil (r-2)/(\ell -2)\rfloor$, we show \[ N_m^r(n,\ell) \leq N_m^2(n,\ell)^{r - 1 + λ}\] which is tight when $\ell -2$ divides $r-2$ up to a $1+o(1)$ term in the exponent. This result is used to address the extremal problem for subgraphs of girth more than $\ell$ in random $r$-uniform hypergraphs.

Corrected the upper bound of Theorem 1.5 for odd \ell

References in corpus (2)

• The regularity method for graphs with few 4-cycles
• Triangle-free Subgraphs of Hypergraphs