TY - GEN
T1 - Suitable permutations, Binary covering Arrays, and Paley matrices
AU - Colbourn, Charles
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - A set of permutations of length ν is t-suitable if every element precedes every subset of t – 1 others in at least one permutation. The maximum length of a t-suitable set of N permutations depends heavily on the relation between t and N. Two classical results, due to Dushnik and Spencer, are revisited. Dushnik’s result determines the maximum length when t > √2N. On the other hand, when t is fixed Spencer’s uses a strong connection with binary covering arrays of strength t – 1 to obtain a lower bound on the length that is doubly exponential in t. We explore intermediate values for t, by first considering directed packings and related Golomb rulers, and then by examining binary covering arrayswhose number of rows is approximately equal to their number of columns. These in turn are constructed from Hadamard and Paley matrices, for which we present some computational data and questions.
AB - A set of permutations of length ν is t-suitable if every element precedes every subset of t – 1 others in at least one permutation. The maximum length of a t-suitable set of N permutations depends heavily on the relation between t and N. Two classical results, due to Dushnik and Spencer, are revisited. Dushnik’s result determines the maximum length when t > √2N. On the other hand, when t is fixed Spencer’s uses a strong connection with binary covering arrays of strength t – 1 to obtain a lower bound on the length that is doubly exponential in t. We explore intermediate values for t, by first considering directed packings and related Golomb rulers, and then by examining binary covering arrayswhose number of rows is approximately equal to their number of columns. These in turn are constructed from Hadamard and Paley matrices, for which we present some computational data and questions.
KW - Directed block design
KW - Golomb ruler
KW - Hadamard matrix
KW - Paley matrix
KW - Suitable sets of permutations
UR - http://www.scopus.com/inward/record.url?scp=84945897861&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84945897861&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-17729-8_3
DO - 10.1007/978-3-319-17729-8_3
M3 - Conference contribution
AN - SCOPUS:84945897861
SN - 9783319177281
T3 - Springer Proceedings in Mathematics and Statistics
SP - 29
EP - 42
BT - Algebraic Design Theory and Hadamard Matrices, ADTHM 2014
A2 - Colbourn, Charles J.
PB - Springer New York LLC
T2 - Workshop on Algebraic Design Theory and Hadamard Matrices, ADTHM 2014
Y2 - 8 July 2014 through 11 July 2014
ER -