Name
Abstract | ||
|---|---|---|
A q × n array with entries from 0, 1,..., q − 1 is said to form a difference matrix if the vector difference (modulo q ) of each pair of columns consists of a permutation of [0, 1,... q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1] t , a λq × n array will be said to form a ( t, q, λ, Δ ) sign-balanced matrix if for each choice C 1 , C 2 ,..., C t of t columns and for each choice ɛ = ( ɛ 1 ,..., ɛ t ) ∈ Δ of signs, the linear combination ∑ j = 1 t ε j C j contains (mod q ) each entry of [0, 1,..., q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k ( n, t, q, λ, δ ) of rows have to be so that for each choice of t columns and for each choice ( ɛ 1 , ..., ɛ t ) of signs in δ, the linear combination ∑ j = 1 t ε j C j contains each entry of [0, 1,..., q − 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k ( n, t, q, λ, δ ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0012-365X(98)00122-8 | Discrete Mathematics |
Keywords | Field | DocType |
lovász local lemma,stein-chen method,difference matrices,poisson approximation,probabilistic method,lovasz local lemma,upper bound,idea generation,probability distribution | Linear combination,Discrete mathematics,Combinatorics,Matrix (mathematics),Modulo,Permutation,Matrix difference equation,Logarithm,Lovász local lemma,Poisson distribution,Mathematics | Journal |
Volume | Issue | ISSN |
190 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anant P. Godbole | 1 | 95 | 16.08 |
| Laura K. Potter | 2 | 0 | 0.34 |
| Erik J. Sandquist | 3 | 0 | 0.34 |