On the Turán density of \1, 3\-hypergraphs

MaRDI QIDQ1732027zbMATH OpenFDO

Authors Shuliang Bai, Linyuan Lu

Publication date 15 March 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.06143, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p34

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Hypergraphs (05C65) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper, we consider the Tur'an problems on $1,3$-hypergraphs. We prove that a $1,3$-hypergraph is degenerate if and only if it's $H_5^{1,3}$-colorable, where $H_5^{1,3}$ is a hypergraph with vertex set $V=[5]$ and edge set $E=2,3,1,2,4,1,3,5,1,4,5.$ Using this result, we further prove that for any finite set $R$ of distinct positive integers, except the case $R=1,2$, there always exist non-trivial degenerate $R$-graphs. We also compute the Tur'an densities of some small $1,3$-hypergraphs.

Review text

Summary: In this paper, we consider the Turán problems on \(\{1,3\}\)-hypergraphs. We prove that a \(\{1, 3\}\)-hypergraph is degenerate if and only if it's \(H^{\{1, 3\}}_5\)-colorable, where \(H^{\{1, 3\}}_5\) is a hypergraph with vertex set \(V=[5]\) and edge set \(E=\{\{2\}, \{3\}, \{1, 2, 4\},\{1, 3, 5\}, \{1, 4, 5\}\}.\) Using this result, we further prove that for any finite set \(R\) of distinct positive integers, except the case \(R=\{1, 2\}\), there always exist non-trivial degenerate \(R\)-graphs. We also compute the Turán densities of some small \(\{1,3\}\)-hypergraphs.

Recommendations

• On the Turán number of triple systems
• Degenerate Turán densities of sparse hypergraphs
• Turán problems on non-uniform hypergraphs
• On the Turán density of uniform hypergraphs
• The Turán problem for hypergraphs on fixed size

Cites work

• A note on generalized Lagrangians of non-uniform hypergraphs
• An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
• scientific article; zbMATH DE number 3224335 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Non-uniform Turán-type problems
• On some extremal problems in graph theory
• On the structure of linear graphs
• Turán problems on non-uniform hypergraphs

Cited in

(8)

• On the Turán number of triple systems
• Turán density of 2-edge-colored bipartite graphs with application on \(\{2, 3\}\)-hypergraphs
• Degenerate Turán densities of sparse hypergraphs
• New Turán densities for 3-graphs
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• A note on the structure of Turán densities of hypergraphs

This page was built for publication: On the Turán density of \(\{1, 3\}\)-hypergraphs

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