oai:arXiv.org:2404.01839
Computer Science
2024
4/10/2024
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
$\textrm{ex}_r ( N, \mathcal{C}_{ 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 \geq 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 \geq 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$.
Haymaker, Kathryn,Tait, Michael,Timmons, Craig, 2024, Hypergraphs of girth 5 and 6 and coding theory