Conflict-Avoiding Codes and Cyclic Triple Systems

The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length $n$ and Hamming weight 3 and having the following property: any $3\times n$ matrix whose rows are cyclic shifts of three different code vectors contains a $3\times3$ permutation matrix as a submatrix. This property (in the special case $w=3$) characterizes conflict-avoiding codes of length $n$ for $w$ active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of $w$ active users to transmit a data packet successfully in one of $w$ attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length $n$ with $w=3$ is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for $w=3$ which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.