Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions

DOI10.1007/S00373-020-02270-WMaRDI QIDQ2045366zbMATH OpenOpenAlexFDO

Authors Biao Wu, Yuejian Peng

Publication date 12 August 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Lagrangian of hypegraphsTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Hypergraphs (05C65) Perfect graphs (05C17)

Abstract: For a fixed positive integer $n$ and an $r$-uniform hypergraph $H$, the Tur'an number $ex(n,H)$ is the maximum number of edges in an $H$-free $r$-uniform hypergraph on $n$ vertices, and the Lagrangian density of $H$ is defined as $p{i}_{lambda}(H)=supr!lambda(G):G;extisan;Hext-free;rext-uniformhypergraph$, where $lambda(G)$ is the Lagrangian of $G$. For an $r$-uniform hypergraph $H$ on $t$ vertices, it is clear that $p{i}_{lambda}(H)ger!lambda(K_{t-1}^r)$. We say that an $r$-uniform hypergraph $H$ on $t$ vertices is perfect if $p{i}_{lambda}(H)=r!lambda(K_{t-1}^r)$. Let $P_t=e_1,e_2,dots,e_t$ be the linear $3$-uniform path of length $t$, that is, $|e_i|=3$, $|e_{i}cap{e}_{i+1}|=1$ and $e_{i}cap{e}_j=emptyset$ if $|i-j|ge2$. We show that $P_3$ and $P_4$ are perfect, this supports a conjecture in cite{yanpeng} proposing that all $3$-uniform linear hypergraphs are perfect. Applying the results on Lagrangian densities, we determine the Tur'an numbers of their extensions.

Recommendations

• The Lagrangian density of the disjoint union of a \(3\)-uniform tight path and a matching and the Turán number of its extension
• \(\lambda\)-perfect hypergraphs and Lagrangian densities of hypergraph cycles
• Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions
• Lagrangian densities of enlargements of matchings in hypergraphs
• The Lagrangian density of \(\{123, 234, 456\}\) and the Turán number of its extension

Cites work

• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Turán theorem for extensions via an Erdős-Ko-Rado theorem for Lagrangians
• A hypergraph Turán theorem via Lagrangians of intersecting families
• An exact Turán result for the generalized triangle
• Asymptotic solution for a new class of forbidden r-graphs
• Extremal problems whose solutions are the blowups of the small Witt- designs
• GENERATING NON-JUMPING NUMBERS OF HYPERGRAPHS
• Hypergraphs do not jump
• Lagrangian densities of enlargements of matchings in hypergraphs
• Lagrangian densities of linear forests and Turán numbers of their extensions
• Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
• On the structure of linear graphs
• Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians
• The Lagrangian density of \(\{123, 234, 456\}\) and the Turán number of its extension
• Turán number of generalized triangles
• Turán numbers of extensions
• \(\lambda\)-perfect hypergraphs and Lagrangian densities of hypergraph cycles

Cited in

(10)

• Lagrangian densities of linear forests and Turán numbers of their extensions
• \(\lambda\)-perfect hypergraphs and Lagrangian densities of hypergraph cycles
• \((k-2)\)-linear connected components in hypergraphs of rank \(k\)
• The Lagrangian density of \(\{123, 234, 456\}\) and the Turán number of its extension
• An irrational Turán density via hypergraph Lagrangian densities
• Lagrangian densities of enlargements of matchings in hypergraphs
• Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions
• The Lagrangian density of the disjoint union of a \(3\)-uniform tight path and a matching and the Turán number of its extension
• The maximum Lagrangian of 5-uniform hypergraphs without containing two edges intersecting at a vertex
• Lagrangian-perfect hypergraphs

This page was built for publication: Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions

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