Hypergraphs of girth 5 and 6 and coding theory

Abstract

In this paper, we study the maximum number of edges in an $N$-vertex $r$-uniform hypergraph with girth $g$ where $g\in \{5,6\}$. Writing ${\text{ex}}_r(N,{\mathcal{C}}_{<g})$ for this maximum, it is shown that ${\text{ex}}_r(N,{\mathcal{C}}_{<5})={\Omega }_r(N^{3/2-o(1)})$ for $r\in \{4,5,6\}$. We address an unproved claim from [31] asserting a technique of Ruzsa can be used to show that this lower bound holds for all $r\ge 3$. We carefully explain one of the main obstacles that was overlooked at the time the claim from [31] was made, and show that this obstacle can be overcome when $r\in \{4,5,6\}$. We use constructions from coding theory to prove nontrivial lower bounds that hold for all $r\ge 3$. Finally, we use a recent result of Conlon, Fox, Sudakov, and Zhao to show that the sphere packing bound from coding theory may be improved when upper bounding the size of linear $q$-ary codes of distance $6$.