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

Combinatorial Theory

Combinatorial Theory banner

Large hypergraphs without tight cycles

Published Web Location Commons 'BY' version 4.0 license

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