Linear Turan numbers of r-uniform linear cycles and related Ramsey numbers

Abstract

An $r$-uniform hypergraph is called an $r$-graph. A hypergraph is linear if every two edges intersect in at most one vertex. Given a linear $r$-graph $H$ and a positive integer $n$, the linear Turán number $e{x}_L(n,H)$ is the maximum number of edges in a linear $r$-graph $G$ that does not contain $H$ as a subgraph. For each $\ell \ge 3$, let $C_{\ell }^r$ denote the $r$-uniform linear cycle of length $\ell$, which is an $r$-graph with edges $e_1,\dots ,e_{\ell }$ such that $\forall i\in [\ell -1]$, $|e_i\cap e_{i+1}|=1$, $|e_{\ell }\cap e_1|=1$ and $e_i\cap e_j=\varnothing$ for all other pairs $\{i,j\},i\ne j$. For all $r\ge 3$ and $\ell \ge 3$, we show that there exist positive constants $c_{m,r}$ and $c_{m,r}^{\prime }$, depending only $m$ and $r$, such that $e{x}_L(n,C_{2m}^r)\le c_{m,r}{n}^{1+\frac{1}{m}}$ and $e{x}_L(n,C_{2m+1}^r)\le c_{m,r}^{\prime }{n}^{1+\frac{1}{m}}$. This answers a question of Kostochka, Mubayi, and Verstraëte. For even cycles, our result extends the result of Bondy and Simonovits on the Turán numbers of even cycles to linear hypergraphs. Using our results on linear Turán numbers we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants $a_{m,r}$ and $b_{m,r}$, depending only on $m$ and $r$, such that $R(C_{2m}^r,K_t^r)\le a_{m,r}(\frac{t}{\ln t}{)}^{\frac{m}{m-1}}$ and $R(C_{2m+1}^r,K_t^r)\le b_{m,r}{t}^{\frac{m}{m-1}}$.

25 pages, corrected typos in version 1

Cited by in corpus (1)

• Cycles of given lengths in hypergraphs