Superimposed codes

Joint School of Mathematics and ACO Colloquium
Thursday, September 26, 2013 - 4:30pm for 1 hour (actually 50 minutes)
Skyles 005
Zoltan Furedi – Renyi Institute of Mathematics of the Hungarian Academy of Sciences
Karim Lounici

Please Note: Refreshements served at 4:00pm

There are many instances in Coding Theory when codewords must be restored from partial information, like defected data (error correcting codes), or some superposition of the strings.These lead to superimposed codes, close relatives of group testing problems.There are lots of versions and related problems, likeSidon sets, sum-free sets, union-free families, locally thin families, cover-free codes and families, etc.We discuss two cases {\it cancellative} and {\it union-free} codes.A family of sets $\mathcal F$ (and the corresponding code of0-1 vectors) is called {\bf union-free} if $A\cup B = C\cup D$ and $A,B,C,D\in \mathcal F$ imply $\{ A,B\}=\{ C, D \}$.$\mathcal F$ is called $t$-{\bf cancellative}if for all distict $t+2$ members $A_1, \dots, A_t$ and $B,C\in \mathcal F$ $$A_1\cup\dots \cup A_t\cup B \neq A_1\cup \dots A_t \cup C. $$Let $c_t(n)$ be the size of the largest $t$-cancellative code on $n$elements. We significantly improve the previous upper bounds of Alon, Monti, K\"orner and Sinaimeri, and introduce a method to deal with such problems, namely to investigate first the constant weight case (i.e., uniform hypergraphs).