Linear Turan numbers of linear cycles and cycle-complete Ramsey numbers
2018
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 Turan number exL(n,H) is the maximum number of edges in a linear r-graph G that does not contain H as a subgraph. For each ' 3, let C r ' denote the r-uniform linear cycle of length ', which is an r-graph with edges e1,...,e' such that8i2 (' 1),|ei\ei+1| = 1,|e'\e1| = 1 and ei\ej =; for all other pairs{i,j},i6 j. For all r 3 and ' 3, we show that there exists a positive constant cr,', depending only r and ', such that exL(n,C r ' ) cr.'n 1+b 2 ' c . This answers a question of Kostochka, Mubayi, and Verstraete (30). For even ', our result extends the result of Bondy and Simonovits (7) on the Turan numbers of even cycles to linear hypergraphs. Using our results on linear Turan numbers we also obtain bounds on the cycle-complete hy- pergraph Ramsey numbers. We show that there are positive constants am,r and bm,r, depending only on m and r, such that R(C r 2m ,K r t ) am,r( t lnt ) m m 1 and R(C r 2m+1 ,K r ) bm,rt m m 1 .
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
41
References
15
Citations
NaN
KQI