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

Mathematics Subject Classification ID

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 $ellgeq3$, let $C_e^{r}ll$ denote the $r$-uniform linear cycle of length $ell$, which is an $r$-graph with edges $e_1,ldots,e_{e}ll$ such that $foralliin[ell-1]$, $|e_{i}cap{e}_{i+1}|=1$, $|e_{e}llcap{e}_1|=1$ and $e_{i}cap{e}_j=emptyset$ for all other pairs $i,j,ieqj$. For all $rgeq3$ and $ellgeq3$, we show that there exist positive constants $c_{m,r}$ and $c{\text{'}}_{m,r}$, depending only $m$ and $r$, such that $e{x}_L(n,C_{2m}^r)leq{c}_{m,r}{n}^{1+frac1m}$ and $e{x}_L(n,C_{2m+1}^r)leqc{\text{'}}_{m,r}{n}^{1+frac1m}$. 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_{2m}^r,K_t^r)leq{a}_{m,r}(fractlnt{)}^{f}racmm-1$ and $R(C_{2m+1}^r,K_t^r)leq{b}_{m,r}{t}^{f}racmm-1$.

Recommendations

• Hypergraph Turán numbers of linear cycles
• Turán and Ramsey numbers in linear triple systems
• Cycle-complete Ramsey numbers
• Linear Ramsey numbers
• On some Ramsey and Turán-type numbers for paths and cycles
• On graphs with linear Ramsey numbers
• The Cycle-Complete Graph Ramsey Numbers
• Turán and Ramsey numbers in linear triple systems. II
• Ramsey numbers of a cycle
• Ramsey numbers for line graphs and perfect graphs

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• 3-uniform hypergraphs avoiding a given odd cycle
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• A note on Ramsey numbers
• A note on odd cycle-complete graph Ramsey numbers
• A note on the Turán function of even cycles
• Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
• Coloring graphs with sparse neighborhoods
• Cycles of even length in graphs
• Dynamic concentration of the triangle-free process
• Exact solution of the hypergraph Turán problem for k-uniform linear paths
• Graph colouring and the probabilistic method
• Hypergraph Ramsey numbers: triangles versus cliques
• Hypergraph Turán numbers of linear cycles
• Hypergraphs with no cycle of a given length
• Independence numbers of locally sparse graphs and a Ramsey type problem
• Intersection Theorems for Systems of Sets
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On a Problem of Heilbronn
• On a class of degenerate extremal graph problems
• On arithmetic progressions of cycle lengths in graphs
• On cycle—Complete graph ramsey numbers
• On hypergraphs of girth five
• On the Turán number for the hexagon
• On the existence of triangulated spheres in 3-graphs, and related problems
• On the number of edges of quadrilateral-free graphs
• On the structure of linear graphs
• Rainbow Turán Problems
• Rainbow Turán problem for even cycles
• Solving a linear equation in a set of integers I
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The early evolution of the \(H\)-free process
• The history of degenerate (bipartite) extremal graph problems
• The independence number of graphs with a forbidden cycle and Ramsey numbers
• Turán numbers of subdivided graphs
• Turán problems and shadows. I: Paths and cycles

Cited in

(29)

• On the number of linear hypergraphs of large girth
• The exact linear Turán number of the sail
• Turán numbers for hypergraph star forests
• Spectral radius on linear \(r\)-graphs without expanded \(K_{r+1}\)
• Turán problems for star-path forests in hypergraphs
• Ramsey numbers for nontrivial Berge cycles
• Multicolor Turán numbers
• Linear saturation numbers of Berge-\(C_3\) and Berge-\(C_4\)
• A linear hypergraph extension of Turán's theorem
• A linear hypergraph extension of the bipartite Turán problem
• Supersaturation of even linear cycles in linear hypergraphs
• Sidorenko hypergraphs and random Turán numbers
• Spectral extremal results for hypergraphs
• Many pentagons in triple systems
• On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
• Linear cycles of consecutive lengths
• Linear Turán problems with bounded matching number in hypergraphs
• Turán theorems for even cycles in random hypergraph
• The Ramsey number of 3-uniform loose path versus star
• Asymptotic Turán number for linear 5-cycle in 3-uniform linear hypergraphs
• Turán and Ramsey numbers in linear triple systems. II
• The linear Turán number of small triple systems or why is the wicket interesting?
• Linear Turán numbers of acyclic triple systems
• On tight cycles in hypergraphs
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Hypergraph Turán numbers of linear cycles
• On 3-uniform hypergraphs without a cycle of a given length
• A Ramsey variant of the Brown-Erdős-Sós conjecture
• Cycles of given lengths in hypergraphs

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)