%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Information from $t$-design parameters}
For $t$ a non-negative integer and $v,k,\lambda$ positive integers
with $t\le k\le v$, a $t$-*design* \index{t-design}
with *parameters*
$t,v,k,\lambda$, or a $t$-$(v,k,\lambda)$ *design*, is a binary block
design with exactly $v$ points, such that each block has size $k$ and
each $t$-subset of the points is contained in exactly $\lambda$ blocks.
\>TDesignLambdas( <t>, <v>, <k>, <lambda> )
A $t$-$(v,k,\lambda)$ design is also an $s$-$(v,k,\lambda_s)$ design
for $0\le s\le t$, where $\lambda_s=\lambda{v-s \choose t-s}/{k-s \choose t-s}$.
Given a non-negative integer <t>, and positive integers <v>, <k>,
<lambda>, with $<t>\le <k>\le <v>$, this function returns a length
$<t>+1$ list whose $(s+1)$-st element is $\lambda_s$ as defined above,
if all the $\lambda_s$ are integers. Otherwise, `fail' is returned.
Given a non-negative integer <t>, and positive integers <v> and <k>, with
$<t>\le <k>\le <v>$, this function returns the minimum positive <lambda>
such that `TDesignLambdas( <t>, <v>, <k>, <lambda> )' does not return
`fail'.
Suppose $D$ is a <t>-(<v>,<k>,<lambda>) design, let $i$ and $j$
be non-negative integers with $i+j\le t$, and suppose $X$ and $Y$
are disjoint subsets of the points of $D$, such that $X$ and $Y$ have
respective sizes $i$ and $j$. The $(i,j)$-*intersection number* is
the number of blocks of $D$ that contain $X$ and are disjoint from $Y$
(this number depends only on <t>, <v>, <k>, <lambda>, $i$ and $j$).
Given a non-negative integer <t>, and positive integers <v>, <k>
and <lambda>, with $<t>\le <k>\le <v>$, this function returns the
*<t>-design intersection triangle*, which is a two dimensional array
whose $(i+1,j+1)$-entry is the $(i,j)$-intersection number for
a <t>-(<v>,<k>,<lambda>) design (assuming such a design exists),
such that $i,j\ge 0$, $i+j\le t$. This function returns `fail' if
`TDesignLambdas(<t>,<v>,<k>,<lambda>)' does. When $=1$, then more
information can be obtained using "SteinerSystemIntersectionTriangle".
A *Steiner system* is a <t>-(<v>,<k>,1) design, and in this case it
is possible to extend the notion of intersection triangle defined in "TDesignIntersectionTriangle".
Suppose $D$ is a <t>-(<v>,<k>,1) design, with $B$ a block of $D$,
let $i$ and $j$ be non-negative integers with $i+j\le k$, and suppose
$X$ and $Y$ are disjoint subsets of $B$, such that $X$ and $Y$ have
respective sizes $i$ and $j$. The $(i,j)$-*intersection number* is the number of blocks of $D$ that contain $X$ and are disjoint from $Y$
(this number depends only on <t>, <v>, <k>, $i$ and $j$). Note that
when $i+j\le t$, this intersection number is the same as that defined in "TDesignIntersectionTriangle" for the general <t>-design case.
Given a non-negative integer <t>, and positive integers <v> and
<k>, with $<t>\le <k>\le <v>$, this function returns the *Steiner
system intersection triangle*, which is a two dimensional array whose
$(i+1,j+1)$-entry is the $(i,j)$-intersection number for a <t>-(<v>,<k>,1)
design (assuming such a design exists), such that $i,j\ge 0$, $i+j\le
k$. This function returns `fail' if `TDesignLambdas(,,,1)' does.
Given a non-negative integer <t>, and positive integers <v>, <k> and
<lambda>, with $<t>\le <k>\le <v>$, this function returns a non-negative
integer which is an upper bound on the multiplicity of any block in
any <t>-(<v>,<k>,<lambda>) design (the *multiplicity* of a block in
a block design is the number of times that block occurs in the block
list). In particular, if the value $0$ is returned, then this implies
that a <t>-(<v>,<k>,<lambda>) design does not exist.
Although our bounds are reasonably good, we do not claim that the
returned bound $m$ is always achieved; that is, there may not exist a
<t>-(<v>,<k>,<lambda>) design having a block with multiplicity $m$.
See also "ResolvableTDesignBlockMultiplicityBound".
A *resolution* of a block design is a partition of the blocks into
subsets, each of which forms a partition of the point set, and a block
design is *resolvable* if it has a resolution.
Given a non-negative integer <t>, and positive integers <v>, <k> and
<lambda>, with $<t>\le <k>\le <v>$, this function returns a non-negative
integer which is an upper bound on the multiplicity of any block in any
resolvable <t>-(<v>,<k>,<lambda>) design (the *multiplicity* of a block
in a block design is the number of times that block occurs in the block
list). In particular, if the value $0$ is returned, then this implies
that a resolvable <t>-(<v>,<k>,<lambda>) design does not exist.
Although our bounds are reasonably good, we do not claim that the returned
bound $m$ is always achieved; that is, there may not exist a resolvable
<t>-(<v>,<k>,<lambda>) design having a block with multiplicity $m$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Information from (mixed) orthogonal array parameters}
For integers $N,k,s,t$, with $N,k>0$, $s>1$, and $0\le t\le k$,
an *orthogonal array* \index{orthogonal array}
OA$(N,k,s,t)$ is an $N\times k$ array, in which the entries come from a
set of size $s$ of *symbols*, with the property that in any $N\times t$
subarray, every possible $t$-tuple of symbols occurs as a row equally
often (which must be $N/s^t$ times).
For integers $N,k_1,\ldots,k_w,s_1,\ldots,s_w,t$, with
$w,N,k_1,\ldots,k_w>0$, $s_1,\ldots,s_w>1$, and $0\le t\le k:=k_1+\cdots+k_w$,
a *mixed orthogonal array* \index{mixed orthogonal array}
OA$(N,s_1^{k_1},\ldots,s_w^{k_w},t)$ is an $N\times k$
array, in which the entries in the first
$k_1$ columns come from a set of symbols of size $s_1$, the entries
in the next $k_2$ columns come from a set of symbols of size $s_2$,
and so on, with the property that in any $N\times t$ subarray, every
possible $t$-tuple of symbols occurs as a row equally often.
Clearly, a mixed orthogonal array OA$(N,s^k,t)$ is the same thing as an
orthogonal array OA$(N,k,s,t)$.
The rows of an orthogonal array or mixed orthogonal array are called *runs*.
The *multiplicity* of a run is the number of times it appears as a row
in the array.
\>OARunMultiplicityBound( <N>, <k>, <s>, <t> )
Suppose <N>, <k>, <s>, and <t> are integers, with <N>, <k> positive,
$<s> > 1$, and $0\le <t>\le <k>$. Then this function returns an upper
bound on the multiplicity of any run in an orthogonal array OA$(N,k,s,t)$.
An upper bound on the multiplicity of a run in a mixed orthogonal array
can be obtained by replacing <k> and <s> by non-empty lists of the same
length, $w$ say, of positive integers, such that $0\le <t> \le$ `Sum(<k>)',
and each entry of <s> is at least 2. Then the function returns an
upper bound on the multiplicity of any run in a mixed orthogonal array
OA$(N,s[1]^{k[1]},...,s[w]^{k[w]},t)$.
If the value $0$ is returned, then this implies that an orthogonal array
or mixed orthogonal array with the given parameters does not exist.
We do not claim that the returned upper bound $m$ is achieved; that
is, there may well be no (mixed) orthogonal array with the given
parameters having a run with multiplicity $m$.
In \cite{CaSo}, Cameron and Soicher introduce block intersection
polynomials and their applications to the study of block designs.
Here we give functions to construct and analyze block intersection
polynomials.
For $k$ a non-negative integer, define the polynomial
$P(x,k)=x(x-1)\cdots(x-k+1)$. Let $s$ and $t$ be non-negative
integers, with $s\ge t$, and let $m_0,\ldots,m_s$ and
$\lambda_0,\ldots,\lambda_t$ be rational numbers. Then the *block
intersection polynomial* for the sequences $[m_0,\ldots,m_s]$,
$[\lambda_0,\ldots,\lambda_t]$ is defined to be
$$\sum_{j=0}^t{t\choose j}P(-x,t-j)[P(s,j)\lambda_j-\sum_{i=j}^s P(i,j)m_i],$$
and is denoted by $B(x,[m_0,\ldots,m_s],[\lambda_0,\ldots,\lambda_t]).$
Now suppose <x> is an indeterminate over the rationals, and <m> and
<lambdavec> are non-empty lists of rational numbers, such that the length
of <lambdavec> is not greater than that of <m>. Then this function
returns the block intersection polynomial $B(<x>,<m>,<lambdavec>)$.
The importance of a block intersection polynomial is as follows.
Let $D=(V,{\cal B})$ be a block design, let $S\subseteq V$, with $s=|S|$,
and for $i=0,\ldots,s$, suppose that $m_i$ is a non-negative integer
with $m_i\le n_i$, where $n_i$ is the number of blocks intersecting $S$
in exactly $i$ points. Let $t$ be a non-negative *even* integer with $t\le
s$, and suppose that, for $j=0\ldots,t$, we have $\lambda_j=1/{s\choose
j}\sum_{T\subseteq S,|T|=j}\lambda_T$, where $\lambda_T$ is the number of blocks of $D$ containing $T$. Then the block intersection
polynomial $B(x)=B(x,[m_0,\ldots,m_s],[\lambda_0,\ldots,\lambda_t])$
is a polynomial with integer coefficients, and $B(n)\ge 0$ for every
integer $n$. (These conditions can be checked using the function "BlockIntersectionPolynomialCheck".) In addition, if $B(n)=0$ for some
integer $n$, then $m_i=n_i$ for $i\not\in\{n,n+1,\ldots,n+t-1\}$.
For more information on block intersection polynomials and their
applications, see \cite{CaSo} and \cite{Soi10}.
Suppose <m> is a list of non-negative integers, and <lambdavec> is a
list of non-negative rational numbers, with the length of <lambdavec>
odd and not greater than the length of <m>.
Then, for <x> an indeterminate over the rationals, this function
checks whether `BlockIntersectionPolynomial(<x>,<m>,<lambdavec>)' is a
polynomial over the integers and has a non-negative value at each integer.
The function returns `true' if this is so; else `false' is returned.
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.28Bemerkung:
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
