ACO The ACO Seminar (2010-2011)

Sept. 30 3:30pm, Wean 8220
Zoltan Furedi, Renyi Institute, Budapest and UIUC, Urbana-Champaigh, IL
t-Cancellative Codes


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.

Back to the ACO seminar

Back to the ACO home page