Large hypergraphs without tight cycles
Large hypergraphs without tight cycles
复制标题
DOI：
10.5070/c61055374
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Barnabás Janzer
中科院分区：
文献类型：
--
作者：
Barnabás Janzer
一个长度为$\ell>r$的$r$-一致紧圈是一个超图，它的顶点为$v_1，\dots，v_\ell $，边为$\{v_i，v_{i+1}，\dots，v_{i+r-1}\}$（对所有的$i$），其指数取模$\ell$。Sudakov和Tomon证明了，对于每个固定的$r\geq 3$，一个不包含任何长度的紧圈的n$个顶点上的$r$-一致超图最多有$n^{r-1+o（1）}$条超边，但最著名的构造（具有最多的边数）只给出$\Omega（n^{r-1}）$条边。本文证明了，对于每个固定的$r\geq 3$，存在$r$-一致超图，其$\Omega（n^{r-1}\log n/\log\log n）$边不含紧圈，从而证明了上界指数中的$o（1）$项是必要的.
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.