pith. machine review for the scientific record. sign in

arxiv: 1807.04683 · v1 · pith:WRS3B6IBnew · submitted 2018-07-12 · 🧮 math.CO

On r-uniform hypergraphs with circumference less than r

classification 🧮 math.CO
keywords lengthuniformbergeedgeseveryfrachypergraphhypergraphs
0
0 comments X
read the original abstract

We show that for each $k\geq 4$ and $n>r\geq k+1$, every $n$-vertex $r$-uniform hypergraph with no Berge cycle of length at least $k$ has at most $\frac{(k-1)(n-1)}{r}$ edges. The bound is exact, and we describe the extremal hypergraphs. This implies and slightly refines the theorem of Gy\H{o}ri, Katona and Lemons that for $n>r\geq k\geq 3$, every $n$-vertex $r$-uniform hypergraph with no Berge path of length $k$ has at most $\frac{(k-1)n}{r+1}$ edges. To obtain the bounds, we study bipartite graphs with no cycles of length at least $2k$, and then translate the results into the language of multi-hypergraphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.