On the volumes and affine types of trades

Ebrahim Ghorbani ; Sara Kamali ; Gholamreza B. Khosrovshahi ; Denis Krotov

The electronic journal of combinatorics, Tome 27 (2020) no. 1

Résumé

A $[t]$-trade is a pair $T=(T_+, T_-)$ of disjoint collections of subsets (blocks) of a $v$-set $V$ such that for every $0\le i\le t$, any $i$-subset 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 $t$-trades 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 Kasami–Tokura of such functions with small number of ones, it is known that any simple $[t]$-trade of volume at most $2\cdot2^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\cdot 2^t$, extending the known result for volumes less than $2\cdot 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\le4$, $v\le7$ is reported.

Détail

DOI : 10.37236/8367

Classification : 05B05, 05B15, 94B05, 94B15
Mots-clés : Kasami-Tokura characterization