Latin Matchings and Ordered Designs <i>OD</i>(<i>n</i>−1, <i>n</i>, 2<i>n</i>−1)

Abstract

This paper revisits a combinatorial structure called the large set of ordered design (LOD). Among others, we introduce a novel structure called Latin matching and prove that a Latin matching of order n leads to an LOD(n−1, n, 2n−1); thus, we obtain constructions for LOD(1, 2, 3), LOD(2, 3, 5), and LOD(4, 5, 9). Moreover, we show that constructing a Latin matching of order n is at least as hard as constructing a Steiner system S(n−2, n−1, 2n−2); therefore, the order of a Latin matching must be prime. We also show some applications in multiagent systems.

Keywords

• combinatorial design
• ordered design
• Hamming code
• error-correcting code
• hat guessing game
• Latin matching