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

DOI10.1017/S0963548316000444MaRDI QIDQ5366952zbMATH OpenOpenAlexFDO

Authors Axel Brandt, David Irwin, Tao Jiang

Publication date 10 October 2017

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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$).

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

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3467166 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• A hypergraph Turán theorem via Lagrangians of intersecting families
• A hypergraph extension of Turán's theorem
• A new construction for cancellative families of sets
• A new generalization of Mantel's theorem to \(k\)-graphs
• A new generalization of the Erdős-Ko-Rado theorem
• An exact Turán result for the generalized triangle
• Asymptotic solution for a new class of forbidden r-graphs
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Extremal problems whose solutions are the blowups of the small Witt- designs
• Improved bounds for Erdős' matching conjecture
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On Triple Systems with Independent Neighbourhoods
• On extremal problems of graphs and generalized graphs
• On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
• Stability theorems for cancellative hypergraphs
• Three-graphs without two triples whose symmetric difference is contained in a third
• Turán number of generalized triangles
• 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
• 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
• An irrational Turán density via hypergraph Lagrangian densities
• A hypergraph extension of Turán's theorem
• Lagrangian densities of enlargements of matchings in hypergraphs
• The Turán number of Berge hypergraphs with stable properties
• Rainbow Erdös-Rothschild problem for the Fano plane
• Lagrangian-perfect hypergraphs
• A hypergraph Turán theorem via Lagrangians of intersecting families
• Turán numbers of extensions
• 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
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• An irrational Lagrangian density of a single hypergraph
• 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)