S(2), Ryser, and Brualdi Conjectures (2001)

Originators: André Kézdy and Hunter Snevily (presented by André Kézdy - REGS 2007)

Definitions: Let f(n,k) be the minimum size of a set S of permutations of [n] such that every permutation of [n] agrees in at least k positions with some element of S. Let g(n,k) be the minimum size of a maximal set of permutations of [n] such that every two of them agree in fewer than k positions.

Conjecture (The S(2)-Conjecture): f(n,2) = n for even n and f(n,2) > n for odd n.

Comments: A latin square has a transversal with distinct elements (a "latin transversal") if and only if there is a permutation of [n] that agrees in exactly one position with each row. Thus f(n,2) > n if and only if every latin square of order n has such a transversal.

The S(2)-Conjecture implies the following conjectures:

Ryser's Conjecture: every latin square of odd order has a latin transversal.
Brualdi's Conjecture: every latin square of order n has a partial latin transversal of size n-1.
Quistorff's Conjecture [Q]: g(n,2) = n for even n and g(n,2) > n for odd n.

Always f(n,k)≤g(n,k), since a maximal set avoiding pairs with k shared positions is a set S such that permutations outside have at least k shared positions with some element of S. Hence Quistorff's Conjecture follows from the S(2)-Conjecture. Also, the rows of a latin square of odd order form a set of permutations that pairwise agree in no positions. A latin transversal is a permutation agreeing with each in exactly one position. Such a permutation can always be added if g(n,2)>n (or f(n,2)>n). Quistorff's Conjecture was originally posed in his Habilitation thesis in 1999.

There are some known results about f(n,k):

f(n,1) = ⌈(n+1)/2⌉ [KS, CW]
f(n,2) ≤ n for even n (addition modulo n produces a Latin square with no latin transversal when n is even)
f(n,n-1) = n!
⌊n/2⌋+2 ≤ f(n,2) ≤ 4n/3+ O(1) [CW]

The computation of f(n,1) is an exercise using Hall's Theorem. The survey by Quistorff [Q] contains further discussion of these and related concepts. Keevash and Ku [KK], in studying a different problem, provide constructions that imply bounds on f(n,k) for general k.

References:
[CK] Cameron, Peter J.; Ku, C. Y.; Intersecting families of permutations. European J. Combin. 24 (2003), no. 7, 881--890.
[CW] Cameron, Peter J.; Wanless, Ian M.; Covering radius for sets of permutations. Discrete Math. 293 (2005), no. 1-3, 91--109.
[KK] Keevash, Peter; Ku, Cheng Yeaw; A random construction for permutation codes and the covering radius. Des. Codes Cryptogr. 41 (2006), no. 1, 79--86.
[KS] Kézdy, André E.; Snevily, Hunter S.; 2001 manuscript.
[Q] Quistorff, Jörn. A survey on packing and covering problems in the Hamming permutation space. Electron. J. Combin. 13 (2006), no. 1, Article 1, 13 pp.