Turán problems and shadows. I: Paths and cycles
From MaRDI portal
Publication:472166
DOI10.1016/J.JCTA.2014.09.005zbMath1302.05129arXiv1308.4120OpenAlexW2059283278WikidataQ105583652 ScholiaQ105583652MaRDI QIDQ472166
Dhruv Mubayi, Alexandr V. Kostochka, Jacques Verstraete
Publication date: 19 November 2014
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: A $k$-path is a hypergraph P_k = e_1,e_2,...,e_k such that |e_i cap e_j| = 1 if |j - i| = 1 and e_i cap e_j is empty otherwise. A k-cycle is a hypergraph C_k = e_1,e_2,.. ,e_k obtained from a (k-1)-path e_1,e_2,...,e_{k-1} by adding an edge e_k that shares one vertex with e_1, another vertex with e_{k-1} and is disjoint from the other edges. Let ex_r(n,G) be the maximum number of edges in an r-graph with n vertices not containing a given r-graph G. We determine ex_r(n, P_k) and ex_r(n, C_k) exactly for all k ge 4 and r ge 3 and $n$ sufficiently large and also characterize the extremal examples. The case k = 3 was settled by Frankl and F"{u}redi. This work is the next step in a long line of research beginning with conjectures of ErdH os and S'os from the early 1970's. In particular, we extend the work (and settle a recent conjecture) of F"uredi, Jiang and Seiver who solved this problem for P_k when r ge 4 and of F"uredi and Jiang who solved it for C_k when r ge 5. They used the delta system method, while we use a novel approach which involves random sampling from the shadow of an r-graph.
Full work available at URL: https://arxiv.org/abs/1308.4120
Cites Work
- Unnamed Item
- Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths
- 3-uniform hypergraphs avoiding a given odd cycle
- An extension of the Ruzsa-Szemerédi theorem
- Hypergraphs in which all disjoint pairs have distinct unions
- Pentagons vs. triangles
- The maximum size of hypergraphs without generalized 4-cycles
- Exact solution of some Turán-type problems
- A homological approach to two problems on finite sets
- A hypergraph extension of the bipartite Turán problem
- Cycles of even length in graphs
- Proof of a conjecture of Erdős on triangles in set-systems
- Minimal paths and cycles in set systems
- An intersection theorem for four sets
- On extremal problems of graphs and generalized graphs
- Hypergraph Turán numbers of linear cycles
- Hypergraph Extensions of the Erdős-Gallai Theorem
- Hypergraphs with No Cycle of a Given Length
- On maximal paths and circuits of graphs
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- An Extremal Set-Intersection Theorem
- On families of finite sets no two of which intersect in a singleton
- Set Systems with No Singleton Intersection
Related Items (46)
Turán numbers for hypergraph star forests ⋮ Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three ⋮ Turán numbers for 3-uniform linear paths of length 3 ⋮ Large hypergraphs without tight cycles ⋮ Refined Turán numbers and Ramsey numbers for the loose 3-uniform path of length three ⋮ The Turán number of disjoint copies of paths ⋮ The number of hypergraphs without linear cycles ⋮ Hypergraphs with no tight cycles ⋮ On the spectrum and linear programming bound for hypergraphs ⋮ Turán problems and shadows. II: Trees ⋮ Turán numbers of complete 3-uniform Berge-hypergraphs ⋮ Extremal \(H\)-free planar graphs ⋮ Anti‐Ramsey number of expansions of paths and cycles in uniform hypergraphs ⋮ Linear cycles of consecutive lengths ⋮ Turán and Ramsey numbers for 3‐uniform minimal paths of length 4 ⋮ Extremal Problems for Hypergraph Blowups of Trees ⋮ Turán, involution and shifting ⋮ The junta method in extremal hypergraph theory and Chvátal's conjecture ⋮ Linearity of saturation for Berge hypergraphs ⋮ Forbidden intersections for codes ⋮ On hypergraphs without loose cycles ⋮ Hypergraph Turán numbers of linear cycles ⋮ Extremal Results for Berge Hypergraphs ⋮ On Tight Cycles in Hypergraphs ⋮ A linear hypergraph extension of the bipartite Turán problem ⋮ Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers ⋮ The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture ⋮ One more Turán number and Ramsey number for the loose 3-uniform path of length three ⋮ Turán numbers for Berge-hypergraphs and related extremal problems ⋮ Turán theorems for even cycles in random hypergraph ⋮ On extremal hypergraphs for forests of tight paths ⋮ Cycles of given lengths in hypergraphs ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ Relative Turán numbers for hypergraph cycles ⋮ Intersecting families without unique shadow ⋮ Turán numbers of general star forests in hypergraphs ⋮ Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs ⋮ Asymptotics for the Turán number of Berge-\(K_{2,t}\) ⋮ Supersaturation of even linear cycles in linear hypergraphs ⋮ Minimum degree of 3-graphs without long linear paths ⋮ Paths in Hypergraphs: A Rescaling Phenomenon ⋮ Extremal Theta-free planar graphs ⋮ Maximum Size Intersecting Families of Bounded Minimum Positive Co-degree ⋮ Planar Turán numbers of short paths ⋮ Turán Problems and Shadows III: Expansions of Graphs ⋮ Ramsey Numbers for Nontrivial Berge Cycles
This page was built for publication: Turán problems and shadows. I: Paths and cycles
