Technical Program

Paper Detail

Paper Title Universally Sparse Hypergraphs with Applications to Coding Theory
Paper IdentifierTH4.R4.1
Authors Chong Shangguan, Itzhak Tamo, Tel Aviv University, Israel
Session Codes and Set Systems
Location Odéon, Level 3
Session Time Thursday, 11 July, 16:40 - 18:00
Presentation Time Thursday, 11 July, 16:40 - 17:00
Manuscript  Click here to download the manuscript
Abstract For fixed integers $r\ge 2,e\ge 2,v\ge r+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. Let $f_r(n,v,e)$ denote the maximum number of edges in a $\mathscr{G}_r(v,e)$-free $r$-uniform hypergraph on $n$ vertices. Brown, Erd\H{o}s and S\'{o}s showed in 1973 that there exist constants $c_1,c_2$ depending only on $r,e,v$ such that $c_1n^{\frac{er-v}{e-1}}\le f_rac(n,v,e)\le c_2n^{\lceil\frac{er-v}{e-1}\rceil}.$ For $e-1|er-v$, the lower bound matches the upper bound up to a constant factor; whereas for $e-1\nmid er-v$, it is a notoriously hard problem to determine the correct exponent of $n$. Our main result is an improvement $f_r(n,v,e)=\Omega(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}})$ for any $r,e,v$ satisfying $\gcd(e-1,er-v)=1$. Moreover, the hypergraph we constructed is not only $\mathscr{G}_r(v,e)$-free but also universally $\mathscr{G}_r(ir-\lceil\frac{(i-1)(er-v)}{e-1}\rceil,i)$-free for every $1\le i\le e$. Interestingly, our new lower bound provides improved constructions for several seemingly unrelated topics in Coding Theory, namely, Parent-Identifying Set Systems, uniform Combinatorial Batch Codes and optimal Locally Recoverable Codes.