Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers

DOI10.1017/S0963548317000530zbMATH Open1390.05149arXiv1404.5015OpenAlexW2181694489MaRDI QIDQ4635508FDOQ4635508

Authors: Clayton Collier-Cartaino, Nathan Graber, Tao Jiang

Publication date: 23 April 2018

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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'an 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

e l l g e q 3

, let

C_{e}^{r} l l

denote the

r

-uniform linear cycle of length

e l l

, which is an

r

-graph with edges

e_{1}, l d o t s, e_{e} l l

such that

f o r a l l i i n [e l l - 1]

,

| e_{i} c a p e_{i + 1} | = 1

,

| e_{e} l l c a p e_{1} | = 1

and

e_{i} c a p e_{j} = e m p t y s e t

for all other pairs

i, j, i e q j

. For all

r g e q 3

and

e l l g e q 3

, we show that there exist positive constants

c_{m, r}

and

c'_{m, r}

, depending only

m

and

r

, such that

e x_{L} (n, C_{2 m}^{r}) l e q c_{m, r} n^{1 + f r a c 1 m}

and

e x_{L} (n, C_{2 m + 1}^{r}) l e q c'_{m, r} n^{1 + f r a c 1 m}

. This answers a question of Kostochka, Mubayi, and Verstra"ete. For even cycles, our result extends the result of Bondy and Simonovits on the Tur'an numbers of even cycles to linear hypergraphs. Using our results on linear Tur'an numbers we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants