Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians

DOI10.1017/S0963548316000444zbMATH Open1371.05198arXiv1510.03461OpenAlexW2963283234MaRDI QIDQ5366952FDOQ5366952

Authors: Axel Brandt, David Irwin, Tao Jiang 

Publication date: 10 October 2017

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

Abstract: Given a family of $r$-uniform hypergraphs $calF$ (or $r$-graphs for brevity), the Tur'an number $ex(n,calF)$ of $calF$ is the maximum number of edges in an $r$-graph on $n$ vertices that does not contain any member of $calF$. A pair $u,v$ is covered in a hypergraph $G$ if some edge of $G$ contains $u,v$. Given an $r$-graph $F$ and a positive integer $pgeqn(F)$, let $H_p^F$ denote the $r$-graph obtained as follows. Label the vertices of $F$ as $v_1,ldots,v_{n(F)}$. Add new vertices $v_{n(F)+1},ldots,v_p$. For each pair of vertices $v_i,v_j$ not covered in $F$, add a set $B_{i,j}$ of $r-2$ new vertices and the edge $v_i,v_{j}cup{B}_{i,j}$, where the $B_{i,j}$'s are pairwise disjoint over all such pairs $i,j$. We call $H_p^F$ the expanded $p$-clique with an embedded $F$. For a relatively large family of $F$, we show that for all sufficiently large $n$, $ex(n,H_p^F)=|T_r(n,p-1)|$, where $T_r(n,p-1)$ is the balanced complete $(p-1)$-partite $r$-graph on $n$ vertices. We also establish structural stability of near extremal graphs. Our results generalize or strengthen several earlier results and provide a class of hypergraphs for which the Tur'an number is exactly determined (for large $n$).

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

Recommendations

• A hypergraph Turán theorem via Lagrangians of intersecting families
• Some results on Lagrangians of hypergraphs
• Stability results for two classes of hypergraphs
• Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions
• A hypergraph Turán problem with no stability
• Stability and exact Turán numbers for matroids
• Turán numbers for Berge-hypergraphs and related extremal problems
• An extremal problem on Lagrangians of hypergraphs
• On Lagrangians of \(r\)-uniform hypergraphs

zbMATH Keywords

\(r\)-uniform hypergraphsexpanded \(p\)-clique

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Cites Work

• On extremal problems of graphs and generalized graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
• A hypergraph extension of Turán's theorem
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Extremal problems whose solutions are the blowups of the small Witt- designs
• Asymptotic solution for a new class of forbidden r-graphs
• Title not available (Why is that?)
• A hypergraph Turán theorem via Lagrangians of intersecting families
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• A new generalization of the Erdős-Ko-Rado theorem
• Three-graphs without two triples whose symmetric difference is contained in a third
• Stability theorems for cancellative hypergraphs
• A new construction for cancellative families of sets
• Turán number of generalized triangles
• Title not available (Why is that?)
• An exact Turán result for the generalized triangle
• Improved bounds for Erdős' matching conjecture
• On Triple Systems with Independent Neighbourhoods
• A new generalization of Mantel's theorem to \(k\)-graphs
• Turán numbers of extensions

Cited In (28)

• Stability theorems for some Kruskal-Katona type results
• Stability theorems for cancellative hypergraphs
• The maximum Lagrangian of 5-uniform hypergraphs without containing two edges intersecting at a vertex
• Dense 3-uniform hypergraphs containing a large clique
• A hypergraph Turán theorem via Lagrangians of intersecting families
• Stability results for two classes of hypergraphs
• A unified approach to hypergraph stability
• Lagrangian densities of linear forests and Turán numbers of their extensions
• A hypergraph extension of Turán's theorem
• The Lagrangian density of \(\{123, 234, 456\}\) and the Turán number of its extension
• Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions
• Lagrangian densities of enlargements of matchings in hypergraphs
• An irrational Turán density via hypergraph Lagrangian densities
• The Turán number of Berge hypergraphs with stable properties
• Rainbow Erdös-Rothschild problem for the Fano plane
• Lagrangian-perfect hypergraphs
• Turán numbers of extensions
• A hypergraph Turán theorem via Lagrangians of intersecting families
• Lagrangian densities of 4-uniform matchings and degree stability of extremal hypergraphs
• Maximisers of the hypergraph Lagrangian outside the principal range
• \(\lambda\)-perfect hypergraphs and Lagrangian densities of hypergraph cycles
• Hypergraph Lagrangians. I: The Frankl-Füredi conjecture is false
• Uniform hypergraphs with many edge‐colorings avoiding a fixed rainbow expanded complete graph
• A hypergraph Turán problem with no stability
• Lagrangians of hypergraphs. II: When colex is best
• An irrational Lagrangian density of a single hypergraph
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions

This page was built for publication: Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians

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