New Turán Exponents for Two Extremal Hypergraph Problems

DOI10.1137/20M1325769MaRDI QIDQ5138977zbMATH OpenOpenAlexFDO

Authors Chong Shangguan, Itzhak Tamo

Publication date 4 December 2020

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

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

zbMATH Keywords

sparse hypergraphsunion-free hypergraphscancellative hypergraphshypergraph Turán-type problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: An $r$-uniform hypergraph is called $t$-cancellative if for any $t+2$ distinct edges $A_1,ldots,A_t,B,C$, it holds that $(cu{p}_{i=1}^t{A}_i)cupBeq(cu{p}_{i=1}^t{A}_i)cupC$. It is called $t$-union-free if for any two distinct subsets $mathcalA,mathcalB$, each consisting of at most $t$ edges, it holds that $cu{p}_{AinmathcalA}Aeqcu{p}_{BinmathcalB}B$. Let $C_t(n,r)$ (resp. $U_t(n,r)$) denote the maximum number of edges of a $t$-cancellative (resp. $t$-union-free) $r$-uniform hypergraph on $n$ vertices. Among other results, we show that for fixed $rge3,tge3$ and $nightarrowinfty$ ${\displaystyle }$Omega(n^{lfloorfrac{2r}{t+2} floor+frac{2rpmod{t+2}}{t+1}})=C_t(n,r)=O(n^{lceilfrac{r}{lfloor t/2 floor+1} ceil}) ext{ and } Omega(n^{frac{r}{t-1}})=U_t(n,r)=O(n^{lceilfrac{r}{t-1} ceil}),${\displaystyle }$ thereby significantly narrowing the gap between the previously known lower and upper bounds. In particular, we determine the Tur'an exponent of $C_t(n,r)$ when $2midtextand(t/2+1)midr$, and of $U_t(n,r)$ when $(t-1)midr$. The main tool used in proving the two lower bounds is a novel connection between these problems and sparse hypergraphs.

Recommendations

• Some extremal results on hypergraph Turán problems
• Rational exponents for hypergraph Turan problems
• Turán numbers for Berge-hypergraphs and related extremal problems
• New bounds for a hypergraph bipartite Turán problem
• Another extremal problem for Turan graphs
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• On Turán exponents of bipartite graphs
• Publication:4949874
• A hypergraph extension of Turán's theorem
• A hypergraph extension of the bipartite Turán problem

Cites work

• scientific article; zbMATH DE number 4104975 (Why is no real title available?)
• scientific article; zbMATH DE number 3467166 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• scientific article; zbMATH DE number 3031694 (Why is no real title available?)
• 2-cancellative hypergraphs and codes
• Families of finite sets in which no set is covered by the union of \(r\) others
• New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback
• Nonrandom binary superimposed codes
• On Cancellative Set Families
• On an extremal hypergraph problem of Brown, Erdős and Sós
• On coloring graphs to maximize the proportion of multicolored k-edges
• Probabilistic Existence Results for Separable Codes
• Sparse hypergraphs with applications to coding theory
• The probabilistic method
• Uniform hypergraphs containing no grids
• Union-free families of sets and equations over fields
• Union-free hypergraphs and probability theory

Cited in

(7)

• Spectral Turán-type problems on cancellative hypergraphs
• Rational exponents for hypergraph Turan problems
• Some extremal results on hypergraph Turán problems
• Hypergraphs without exponents
• The complexity of Boolean failure identification
• Turán numbers for Berge-hypergraphs and related extremal problems
• 2-cancellative hypergraphs and codes

This page was built for publication: New Turán Exponents for Two Extremal Hypergraph Problems

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