Hypergraphs of girth 5 and 6 and coding theory

Document detail

ID

oai:arXiv.org:2404.01839

Topic

Mathematics - Combinatorics Computer Science - Information The... 05C35, 05C65, 94B65, 11H71

Author

Haymaker, Kathryn Tait, Michael Timmons, Craig

Year

2024

listing date

4/10/2024

Keywords

coding $r theory

Metrics

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 $\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

Document

Open

Source

Articles recommended by ES/IODE AI

Computer Science