The Turán density problem for hypergraphs

DOI10.4310/JOC.2022.V13.N4.A2MaRDI QIDQ2166387zbMATH OpenOpenAlexFDO

Authors Adam Sanitt, John Talbot

Publication date 24 August 2022

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

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

zbMATH Keywords

entropy compressiontransversals

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65) Transversal (matching) theory (05D15)

Abstract: Given a $k$-graph $H$ a complete blow-up of $H$ is a $k$-graph $hatH$ formed by replacing each $vinV(H)$ by a non-empty vertex class $A_v$ and then inserting all edges between any $k$ vertex classes corresponding to an edge of $H$. Given a subgraph $GsubseteqhatH$ and an edge $einE(H)$ we define the density $d_e(G)$ to be the proportion of edges present in $G$ between the classes corresponding to $e$. The density Tur'an problem for $H$ asks: determine the minimal value $d_{crit}(H)$ such that any subgraph $GsubseteqhatH$ satisfying $d_e(G)>d_{crit}(H)$ for every $einE(H)$ contains a copy of $H$ as a transversal, i.e. a copy of $H$ meeting each vertex class of $hatH$ exactly once. We give upper bounds for this hypergraph density Tur'an problem that generalise the known bounds for the case of graphs due to Csikv'ari and Nagy, [Combinatorics, Probability and Computing, 21(4):531-553, 2012] although our methods are different, employing an entropy compression argument.

Recommendations

• The density Turán problem
• Turán densities of some hypergraphs related to \(K_{k+1}^{k}\)
• The Turán problem for hypergraphs on fixed size
• Turán problems on non-uniform hypergraphs
• On possible Turán densities

Cited in

(16)

• Extremal hypergraphs and bounds for the Turán density of the 4-uniform \(K_{5}\)
• Asymptotic solution of the Turán problem for some hypergraphs
• Non-jumping Turán densities of hypergraphs
• The density Turán problem
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• Turán problems for integer-weighted graphs
• Exact solution of the hypergraph Turán problem for k-uniform linear paths
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• The density Turan problem for 3-uniform linear hypertrees. An efficient testing algorithm
• Turán problems on non-uniform hypergraphs
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Turánnical hypergraphs
• On the density of a graph and its blowup
• Hypergraph Turán densities can have arbitrarily large algebraic degree
• The maximal length of a gap between r-graph Turán densities
• A note on the structure of Turán densities of hypergraphs

This page was built for publication: The Turán density problem for hypergraphs

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