“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16033  


Abstract:  
A [t]trade is a pair T=(T_{+}, T_{−}) of disjoint collections
of subsets (blocks) of a vset V such that for every 0 ≤ i ≤ t,
any isubset of V is included in the same number
of blocks of T_{+} and of T_{−}. It follows that T_{+} = T_{−} and this common value is called the volume of T.
If we restrict all the blocks to have the same size, we obtain the classical ttrades as a special case of
[t]trades.
It is known that the minimum volume of a nonempty [t]trade is 2^{t}.
Simple [t]trades (i.e., those with no repeated blocks) correspond to a Boolean function of degree at most v−t−1.
From the characterization of KasamiTokura of such functions with small number of ones,
it is known that any simple [t]trade of volume at most 2·2^{t} belongs to one of two
affine types, called Type (A) and Type (B) where Type (A) [t]trades are known to exist. By considering the affine rank, we prove that
[t]trades of Type (B) do not exist.
Further, we derive the spectrum of volumes of simple trades up to 2.5·2^{t},
extending the known result for volumes less than 2·2^{t}.
We also give a characterization of "small" [t]trades for t=1,2. Finally, an algorithm to produce [t]trades for specified t, v
is given. The result of the implementation of the algorithm for t ≤ 4, v ≤ 7 is reported.
Download TeX format 

back to top 