Sparse Hypergraphs with Applications to Coding Theory

DOI10.1137/19M1248108zbMath1450.05044arXiv1902.05903OpenAlexW3039692898MaRDI QIDQ5130902

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 theorysparse hypergraphshypergraph independence number

Mathematics Subject Classification ID

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

Related Items

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 ⋮ Sparse hypergraphs: new bounds and constructions ⋮ New Turán Exponents for Two Extremal Hypergraph Problems ⋮ Constructing dense grid-free linear $3$-graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Uniform hypergraphs containing no grids
• A counterexample to sparse removal
• An extension of the Ruzsa-Szemerédi theorem
• On an extremal hypergraph problem related to combinatorial batch codes
• On an extremal hypergraph problem of Brown, Erdős and Sós
• The early evolution of the \(H\)-free process
• Upper bounds for parent-identifying set systems
• On a packing and covering problem
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Extremal uncrowded hypergraphs
• On hypergraphs of girth five
• Combinatorial batch codes
• Turán numbers and batch codes
• On the existence of triangulated spheres in 3-graphs, and related problems
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• A note on the random greedy independent set algorithm
• Graph removal lemmas
• Extremal problems for cycles in graphs
• On the Locality of Codeword Symbols
• Monotonicity testing over general poset domains
• Centralized Coded Caching Schemes: A Hypergraph Theoretical Approach
• On uncrowded hypergraphs
• On Representatives of Subsets
• Simple analysis of graph tests for linearity and PCP
• Probabilistic Existence Results for Parent-Identifying Schemes
• Separating Hash Families: A Johnson-type bound and New Constructions
• Bounds on Traceability Schemes
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression