Common transversals for partitions of a finite set

✍ Scribed by T.C. Brown

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 725 KB
• Volume: 51
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90065-7

✦ Synopsis

For ~22, ta?, let A, ,..., 4 be s-cell partitions of a finite set X. Assume that if x, y E X7 x # y, then x, y belong to different cells of at least one of the part&ons 4. For each k > 1, let c(s, t, k) be the least integer such that if A 1,. . . ., 4 X satisfy the preceding conditions, and the smallest of all the cells of all the partitions has exady k elements, and 1x1~ c(s, t, k), then A 1, . . . ,b have a common transversal. The functions b(s, t, k) arc defined analogously, except that now the smallest of all the cells of all the partitions is only required to have at least k elements. Thus b(s, t, 1) involves no restriction on the sizes of the cells of the partitions. Note that &, t, 1) = max(c(s, t, k) : k 2 1).

We show, using essentially the method of Longyear [4], that (11 c(s, t, 1) = s'-s'-l-(s-1)'~l+2, sa2, tal, (s, t)#(2,2); (2) c(s,3,s-1)z+-s2-(s-1)2+s, sa2:, t=3; (3) C(S,t,(t-2)(s-1)'-2)~(t-l)(t-2)(s-1)'-2tS(S-1)'-1+l.

sa2, ta3, sat-2; (4) b(s, 2, [(s + 1)/21[) = 0, s a 2, t = 2;

(5) c(s, t,Sk)~s'-s'-'-Sk(S-l)'-k-l+Sk+l, sa2, k>O, tak+2.