The ACO Seminar (2010-2011)
3:30pm, Wean 8220
, Renyi Institute, Budapest and UIUC, Urbana-Champaigh, IL
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