Skip to main content
eScholarship
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Large hypergraphs without tight cycles

  • Author(s): Janzer, Barnabás
  • et al.

Published Web Location

https://doi.org/10.5070/C61055374Creative Commons 'BY' version 4.0 license
Abstract

An $r$-uniform tight cycle of length $\ell>r$ is a hypergraph with vertices $v_1,\dots,v_\ell$ and edges $\{v_i,v_{i+1},\dots,v_{i+r-1}\}$ (for all $i$), with the indices taken modulo $\ell$. It was shown by Sudakov and Tomon that for each fixed $r\geq 3$, an $r$-uniform hypergraph on $n$ vertices which does not contain a tight cycle of any length has at most $n^{r-1+o(1)}$ hyperedges, but the best known construction (with the largest number of edges) only gives $\Omega(n^{r-1})$ edges. In this note we prove that, for each fixed $r\geq 3$, there are $r$-uniform hypergraphs with $\Omega(n^{r-1}\log n/\log\log n)$ edges which contain no tight cycles, showing that the $o(1)$ term in the exponent of the upper bound is necessary.

Mathematics Subject Classifications: 05C65, 05C38

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View