Technical Program

Paper Detail

Paper Title Universally Sparse Hypergraphs with Applications to Coding Theory TH4.R4.1 Chong Shangguan, Itzhak Tamo, Tel Aviv University, Israel Codes and Set Systems Odéon, Level 3 Thursday, 11 July, 16:40 - 18:00 Thursday, 11 July, 16:40 - 17:00 Click here to download the manuscript 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.