Degenerate Turán densities of sparse hypergraphs

DOI10.1016/J.JCTA.2020.105228zbMATH Open1435.05122arXiv1907.04930OpenAlexW3006036904MaRDI QIDQ2306000FDOQ2306000

Authors: Chong Shangguan, Itzhak Tamo 

Publication date: 20 March 2020

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: For fixed integers $r>kge2,ege3$, let $f_r(n,er-(e-1)k,e)$ be the maximum number of edges in an $r$-uniform hypergraph in which the union of any $e$ distinct edges contains at least $er-(e-1)k+1$ vertices. A classical result of Brown, ErdH{o}s and S'os in 1973 showed that $f_r(n,er-(e-1)k,e)=Theta(n^k).$ The degenerate Tur'an density is defined to be the limit (if it exists) ${\displaystyle }$pi(r,k,e):=lim_{n ightarrowinfty}frac{f_r(n,er-(e-1)k,e)}{n^k}.${\displaystyle }$ Extending a recent result of Glock for the special case of $r=3,k=2,e=3$, we show that ${\displaystyle }$pi(r,2,3):=lim_{n ightarrowinfty}frac{f_r(n,3r-4,3)}{n^2}=frac{1}{r^2-r-1}${\displaystyle }$ for arbitrary fixed $rge4$. For the more general cases $r>kge3$, we show that ${\displaystyle }$frac{1}{r^k-r}leliminf_{n ightarrowinfty}frac{f_r(n,3r-2k,3)}{n^k}lelimsup_{n ightarrowinfty}frac{f_r(n,3r-2k,3)}{n^k}le frac{1}{k!�inom{r}{k}-frac{k!}{2}}.${\displaystyle }$ The main difficulties in proving these results are the constructions establishing the lower bounds. The first construction is recursive and purely combinatorial, and is based on a (carefully designed) approximate induced decomposition of the complete graph, whereas the second construction is algebraic, and is proved by a newly defined matrix property which we call {it strongly 3-perfect hashing}.

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

Recommendations

• Some extremal results on complete degenerate hypergraphs
• Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity
• Sparse hypergraphs: new bounds and constructions
• Turán densities of some hypergraphs related to \(K_{k+1}^{k}\)
• On the Turán density of \(\{1, 3\}\)-hypergraphs

zbMATH Keywords

algebraic constructionsparse hypergraphapproximate decomposition of the complete graphdegenerate Turán density

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Hypergraphs (05C65) Triple systems (05B07)

Cites Work

• On extremal problems of graphs and generalized graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The history of degenerate (bipartite) extremal graph problems
• Title not available (Why is that?)
• On a packing and covering problem
• On the combinatorial problems which I would most like to see solved
• The difference between consecutive primes. II
• On the Size of Separating Systems and Families of Perfect Hash Functions
• The probabilistic method
• Title not available (Why is that?)
• On a problem of K. Zarankiewicz
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Problems and results in combinatorial analysis and graph theory
• On an extremal hypergraph problem of Brown, Erdős and Sós
• On the existence of triangulated spheres in 3-graphs, and related problems
• An extension of the Ruzsa-Szemerédi theorem
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• Uniform hypergraphs containing no grids
• On a hypergraph matching problem
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Separating hash families: a Johnson-type bound and new constructions
• Title not available (Why is that?)
• Rational exponents for hypergraph Turan problems
• Rational exponents in extremal graph theory
• Large girth approximate Steiner triple systems
• Triple systems with no three triples spanning at most five points
• 2-cancellative hypergraphs and codes
• Disjoint systems

Cited In (14)

• Sparse hypergraphs with applications to coding theory
• On subgraphs of bounded degeneracy in hypergraphs
• On the \((6,4)\)-problem of Brown, Erdős, and Sós
• Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity
• Hypergraph Turán densities can have arbitrarily large algebraic degree
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• On the Turán density of \(\{1, 3\}\)-hypergraphs
• A note on the structure of Turán densities of hypergraphs
• Approximate Steiner (r − 1, r, n)‐systems without three blocks on r + 2 points
• On 2-parent-identifying set systems of block size 4
• Some extremal results on complete degenerate hypergraphs
• Sparse hypergraphs: new bounds and constructions
• Non-jumping Turán densities of hypergraphs
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

This page was built for publication: Degenerate Turán densities of sparse hypergraphs

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