Sparse hypergraphs with applications to coding theory

DOI10.1137/19M1248108MaRDI QIDQ5130902zbMATH OpenOpenAlexFDO

Authors Chong Shangguan, Itzhak Tamo

Publication date 29 October 2020

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

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

zbMATH Keywords

coding theoryhypergraph independence numbersparse hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial codes (94B25)

Abstract: For fixed integers $rge3,ege3,vger+1$, an $r$-uniform hypergraph is called $mathscr{G}_r(v,e)$-free if the union of any $e$ distinct edges contains at least $v+1$ vertices. Brown, ErdH{o}s and S'{o}s showed that the maximum number of edges of such a hypergraph on $n$ vertices, denoted as $f_r(n,v,e)$, satisfies ${\displaystyle }$Omega(n^{frac{er-v}{e-1}})=f_r(n,v,e)=mathcal{O}(n^{lceilfrac{er-v}{e-1} ceil}).${\displaystyle }$ For $e-1mider-v$, the lower bound matches the upper bound up to a constant factor; whereas for $e-1mider-v$, in general it is a notoriously hard problem to determine the correct exponent of $n$. Among other results, we improve the above lower bound by showing that ${\displaystyle }$f_r(n,v,e)=Omega(n^{frac{er-v}{e-1}}(log n)^{frac{1}{e-1}})${\displaystyle }$ for any $r,e,v$ satisfying $gcd(e-1,er-v)=1$. The hypergraph we constructed is in fact $mathscr{G}_r(ir-lceilfrac(i-1)(er-v)e-1ceil,i)$-free for every $2leilee$, and it has several interesting applications in Coding Theory. The proof of the new lower bound is based on a novel application of the lower bound on the hypergraph independence number due to Duke, Lefmann, and R{"o}dl.

Recommendations

• Sparse hypergraphs: new bounds and constructions
• Degenerate Turán densities of sparse hypergraphs
• On an extremal hypergraph problem related to combinatorial batch codes
• On codes from hypergraphs.
• Uniform hypergraphs containing no grids

Cites work

• A counterexample to sparse removal
• A note on the random greedy independent set algorithm
• An extension of the Ruzsa-Szemerédi theorem
• Bounds on Traceability Schemes
• Centralized Coded Caching Schemes: A Hypergraph Theoretical Approach
• Combinatorial batch codes
• Extremal problems for cycles in graphs
• Extremal uncrowded hypergraphs
• Graph removal lemmas
• scientific article; zbMATH DE number 981682 (Why is no real title available?)
• scientific article; zbMATH DE number 5130822 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• Monotonicity testing over general poset domains
• On a packing and covering problem
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• On an extremal hypergraph problem of Brown, Erdős and Sós
• On an extremal hypergraph problem related to combinatorial batch codes
• On hypergraphs of girth five
• On Representatives of Subsets
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On the existence of triangulated spheres in 3-graphs, and related problems
• On the Locality of Codeword Symbols
• On the power of two, three and four probes
• On uncrowded hypergraphs
• Probabilistic Existence Results for Parent-Identifying Schemes
• Separating hash families: a Johnson-type bound and new constructions
• Simple analysis of graph tests for linearity and PCP
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The early evolution of the \(H\)-free process
• The probabilistic method
• Turán numbers and batch codes
• Uniform hypergraphs containing no grids
• Upper bounds for parent-identifying set systems

Cited in

(19)

• Sparse hypergraphs: new bounds and constructions
• Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection
• Sparse codes derived from graphs
• Uniform hypergraphs containing no grids
• scientific article; zbMATH DE number 1303555 (Why is no real title available?)
• Sparse 0−1 Matrices and Forbidden Hypergraphs
• Nonlinear Sparse-Graph Codes for Lossy Compression
• New Turán Exponents for Two Extremal Hypergraph Problems
• Superimposed codes and hypergraphs containing no grids.
• Constructing dense grid-free linear 3-graphs
• Hash property and coding theorems for sparse matrices and maximum-likelihood coding
• Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Local-vs-global combinatorics
• Applications of sparse hypergraph colorings
• New upper bounds for wide-sense frameproof codes
• Separating hash families with large universe
• On generalized Ramsey numbers in the non-integral regime
• Supersaturation of odd linear cycles

This page was built for publication: Sparse hypergraphs with applications to coding theory

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