Sept. 30 3:30pm, Wean 8220

Zoltan Furedi, Renyi Institute, Budapest and UIUC, Urbana-Champaigh, IL

t-Cancellative Codes

Zoltan Furedi, Renyi Institute, Budapest and UIUC, Urbana-Champaigh, IL

t-Cancellative Codes

Abstract:

A family F of sets is called t-cancellative if for any
distinct t+2 members A_1, ..., A_t, B, C \in F
A_1\cup A_2 \cup ...\cup A_t \cup B \neq
A_1\cup A_2 \cup ...\cup A_t \cup C.
Let M_t(n) be the maximum size of a such an F on n
elements. It is known that
1.5^n /n < M_1(n) < 1.5^n
(Tolhuizen, construction, Frankl and Furedi, upper bound).

Korner and Simeniori showed 0.11 < lim sup M_2(n)/ log_2 n < 0.42 Here we give a slight improvement on the upper bound (0.4151) and also consider M_t(n,k), the size of the largest t-cancellative k-uniform family on n vertices, thus answering a question of G. O. H. Katona.