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

DOI10.1017/S0963548317000530MaRDI QIDQ4635508zbMATH OpenOpenAlexFDO

Authors Clayton Collier-Cartaino, Nathan Graber, Tao Jiang

Publication date 23 April 2018

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

Full work available at URL https://arxiv.org/abs/1404.5015

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Hypergraphs (05C65)

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

a_{m, r}

and

b_{m, r}

, depending only on

m

and

r

, such that

R (C_{2 m}^{r}, K_{t}^{r}) l e q a_{m, r} (f r a c t l n t)^{f} r a c m m - 1

and

R (C_{2 m + 1}^{r}, K_{t}^{r}) l e q b_{m, r} t^{f} r a c m m - 1

.

Recommendations

Cites work

Cited in

(33)

This page was built for publication: Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635508)