Codegree Turán density of complete r-uniform hypergraphs

DOI10.1137/18M1163956MaRDI QIDQ4563373zbMATH OpenFDO

Authors Allan Lo, Yi Zhao

Publication date 1 June 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphminimum codegreeTurán

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Hypergraphs (05C65)

Abstract: Let $rge3$. Given an $r$-graph $H$, the minimum codegree $delt{a}_{r-1}(H)$ is the largest integer $t$ such that every $(r-1)$-subset of $V(H)$ is contained in at least $t$ edges of $H$. Given an $r$-graph $F$, the codegree Tur'an density $gamma(F)$ is the smallest $gamma>0$ such that every $r$-graph on $n$ vertices with $delt{a}_{r-1}(H)ge(gamma+o(1))n$ contains $F$ as a subhypergraph. Using results on the independence number of hypergraphs, we show that there are constants $c_1,c_2>0$ depending only on $r$ such that [ 1 - c_2 frac{ln t}{t^{r-1}} le gamma(K_t^r) le 1 - c_1 frac{ln t}{t^{r-1}}, ] where $K_t^r$ is the complete $r$-graph on $t$ vertices. This gives the best general bounds for $gamma(K_t^r)$.

Recommendations

• An exact result for hypergraphs and upper bounds for the Turán density of \(K^r_{r+1}\)
• On the codegree density of complete 3-graphs and related problems
• Partite Turán-densities for complete \(r\)-uniform hypergraphs on \(r+1\) vertices
• Co-degree density of hypergraphs
• The Turán problem for hypergraphs on fixed size

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• scientific article; zbMATH DE number 4200236 (Why is no real title available?)
• scientific article; zbMATH DE number 3752842 (Why is no real title available?)
• A hypergraph regularity method for generalized Turán problems
• Co-degree density of hypergraphs
• Codegree problems for projective geometries
• Extremal problems on the hypercube and the codegree Turán density of complete \(r\)-graphs
• Note on independent sets in steiner systems
• On independent sets in hypergraphs
• On the co-degree threshold for the Fano plane
• On the codegree density of complete 3-graphs and related problems
• On uncrowded hypergraphs
• The co-degree density of the Fano plane
• The codegree threshold for 3-graphs with independent neighborhoods
• \({\ell}\)-degree Turán density

Cited in

(10)

• On the codegree density of complete 3-graphs and related problems
• Hypergraph Turán Problems in l2-Norm
• On the codegree density of \(\mathrm{PG}_m(q)\)
• Partite Turán-densities for complete \(r\)-uniform hypergraphs on \(r+1\) vertices
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm
• Independence number of hypergraphs under degree conditions
• Extremal problems on the hypercube and the codegree Turán density of complete \(r\)-graphs
• Subgraphs with large minimum \(\ell\)-degree in hypergraphs where almost all \(\ell\)-degrees are large
• \({\ell}\)-degree Turán density

This page was built for publication: Codegree Turán density of complete \(r\)-uniform hypergraphs

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