Namespaces
Variants
Actions

Difference between revisions of "Tactical configuration"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Undo revision 48946 by Ulf Rehmann (talk))
Tag: Undo
m (fixing spaces)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
''<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t0920402.png" />-design, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t0920405.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t0920406.png" />-design on a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t0920407.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t0920408.png" />''
+
<!--
 +
t0920402.png
 +
$#A+1 = 99 n = 4
 +
$#C+1 = 99 : ~/encyclopedia/old_files/data/T092/T.0902040 Tactical configuration,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t0920409.png" />-design is a system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204010.png" />-subsets (blocks) of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204011.png" /> such that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204012.png" />-subset of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204013.png" /> appears in exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204014.png" /> blocks. The class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204015.png" />-designs coincides with the class of [[balanced incomplete block design]]s (cf. [[Block design|Block design]]). The name tactical configuration is given to an [[incidence system]] in which every set is incident with exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204016.png" /> elements, while every element is incident with exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204017.png" /> sets. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204018.png" />-design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204019.png" /> is called trivial. If a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204021.png" />-design is not trivial, then
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204022.png" /></td> </tr></table>
+
'' $  t $-design,  $  t $-$  ( v, k, \lambda ) $-design on a  $  v $-set  $  S $''
  
Every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204023.png" />-design is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204024.png" />-design for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204025.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204026.png" /> of occurrences of an arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204027.png" />-subset in the blocks of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204028.png" />-design is given by the formula
+
A  $  t $-design is a system of  $  k $-subsets (blocks) of the set  $  S $
 +
such that every  $  t $-subset of elements of  $  S $
 +
appears in exactly  $  \lambda $
 +
blocks. The class of  $  2 $-designs coincides with the class of [[balanced incomplete block design]]s (cf. [[Block design|Block design]]). The name tactical configuration is given to an [[incidence system]] in which every set is incident with exactly  $  k $
 +
elements, while every element is incident with exactly  $  r $
 +
sets. A  $  t $-design with  $  t = k $
 +
is called trivial. If a  $  t $-design is not trivial, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204029.png" /></td> </tr></table>
+
$$
 +
t + 1  \leq  k  \leq  v - 1 - t.
 +
$$
  
The condition that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204030.png" /> be integers is a necessary condition for the existence of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204031.png" />-design. In particular, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204032.png" /> every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204033.png" />-design is a balanced incomplete block design.
+
Every  $  t $-design is an  $  s $-design for any  $  s \leq  t $.  
 +
The number  $  \lambda _ {s} $
 +
of occurrences of an arbitrary  $  s $-subset in the blocks of a  $  t $-design is given by the formula
  
The main question concerning <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204034.png" />-designs is the problem of their existence and construction. For a long time, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204035.png" /> only isolated examples were known; in particular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204036.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204037.png" />- and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204038.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204039.png" />-designs connected with the five-fold transitive Mathieu groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204041.png" /> (cf. [[Mathieu group|Mathieu group]]), respectively. However, in the 1960s the connection between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204042.png" />-designs and coding theory (cf. [[Code|Code]]) was discovered (see, for example, [[#References|[3]]] and [[#References|[4]]]), and, starting from vectors with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204043.png" /> non-zero coordinates, a way was shown of constructing a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204044.png" />-design belonging to a linear <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204046.png" />-code, which is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204047.png" />-dimensional vector subspace of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204048.png" />-dimensional space over a [[Finite field|finite field]] (see [[#References|[5]]] and [[#References|[7]]]).
+
$$
 +
\lambda _ {s}  = \
 +
\left ( \begin{array}{c}
 +
k - s \\
 +
t - s
 +
\end{array}
 +
\right ) ^ {-1}
 +
\left ( \begin{array}{c}
 +
v - s \\
 +
t - s
 +
\end{array}
 +
\right ) \lambda ,\ \
 +
0 < s \leq  t.
 +
$$
  
It is well known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204049.png" />-fold transitive groups other than the symmetric and the alternating groups lead to non-trivial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204050.png" />-designs; this yields a few infinite series of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204051.png" />-designs. With the help of ideas from group theory and geometry, infinite classes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204052.png" />- and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204053.png" />-designs were also constructed (see for example [[#References|[6]]]).
+
The condition that the $  \lambda _ {s} $
 +
be integers is a necessary condition for the existence of a t $-design. In particular, for  $  t \geq  2 $
 +
every  $  t $-design is a balanced incomplete block design.
  
For the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204054.png" /> of blocks in a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204055.png" />-design there is the inequality
+
The main question concerning  $  t $-designs is the problem of their existence and construction. For a long time, for  $  t > 3 $
 +
only isolated examples were known; in particular  $  5 $-$  ( 12, 6, 1) $- and  $  5 $-$  ( 24, 8, 1) $-designs connected with the five-fold transitive Mathieu groups  $  M _ {12} $
 +
and  $  M _ {24} $ (cf. [[Mathieu group|Mathieu group]]), respectively. However, in the 1960s the connection between  $  t $-designs and coding theory (cf. [[Code|Code]]) was discovered (see, for example, [[#References|[3]]] and [[#References|[4]]]), and, starting from vectors with  $  v $
 +
non-zero coordinates, a way was shown of constructing a t $-design belonging to a linear  $  ( n, k) $-code, which is a  $  k $-dimensional vector subspace of an  $  n $-dimensional space over a [[Finite field|finite field]] (see [[#References|[5]]] and [[#References|[7]]]).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204056.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
It is well known that  $  t $-fold transitive groups other than the symmetric and the alternating groups lead to non-trivial  $  t $-designs; this yields a few infinite series of  $  3 $-designs. With the help of ideas from group theory and geometry, infinite classes of  $  4 $- and  $  5 $-designs were also constructed (see for example [[#References|[6]]]).
  
generalizing the [[Fisher inequality]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204057.png" /> for balanced incomplete block designs. In the case of equality in (*), the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204058.png" />-design is called tight. Tight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204060.png" />-designs generalize symmetric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204061.png" />-designs; in particular, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204062.png" /> the set of intersection numbers of blocks in a tight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204063.png" />-design contains exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204064.png" /> different elements.
+
For the number  $  b $
 +
of blocks in a  $  t $-design there is the inequality
  
The tight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204065.png" />-designs are the Hadamard designs, i.e. they are the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204066.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204067.png" />-designs, while for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204068.png" /> there are no non-trivial tight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204069.png" />-designs. From a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204070.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204071.png" />-design three other <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204072.png" />-designs can be obtained: a) taking the complement in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204073.png" /> of each block; b) discarding an arbitrary element and all the blocks that contain it; and c) taking blocks containing an arbitrarily chosen element and removing it from them. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204074.png" />-designs thus obtained are called, respectively, the complementary, the residual and the derived <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204078.png" />-design with respect to the initial one. They are, respectively, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204079.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204080.png" />-design with
+
$$ \tag{* }
 +
b \geq  \
 +
\left \{
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204081.png" /></td> </tr></table>
+
\begin{array}{ll}
 +
\left ( \begin{array}{c}
 +
v \\
 +
s
 +
\end{array}
 +
\right )  & \textrm{ if }  t = 2s, v \geq  k + s,  \\
 +
2 \left ( \begin{array}{c}
 +
v - 1 \\
 +
s
 +
\end{array}
 +
\right )  & \textrm{ if }  t = 2s + 1, v - 1 \geq  k + s,  \\
 +
\end{array}
 +
\right.
 +
$$
  
a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204082.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204083.png" />-design with
+
generalizing the [[Fisher inequality]]  $  ( b \geq  v) $
 +
for balanced incomplete block designs. In the case of equality in (*), the  $  t $-design is called tight. Tight  $  t $-designs generalize symmetric  $  2 $-designs; in particular, for  $  t = 2s $
 +
the set of intersection numbers of blocks in a tight  $  t $-design contains exactly  $  s $
 +
different elements.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204084.png" /></td> </tr></table>
+
The tight  $  3 $-designs are the Hadamard designs, i.e. they are the  $  3 $-$  ( 4n, 2n, n- 1) $-designs, while for  $  s \geq  2 $
 +
there are no non-trivial tight  $  ( 2s + 1) $-designs. From a given  $  t $-$  ( v, k, \lambda ) $-design three other  $  t $-designs can be obtained: a) taking the complement in  $  S $
 +
of each block; b) discarding an arbitrary element and all the blocks that contain it; and c) taking blocks containing an arbitrarily chosen element and removing it from them. The  $  t $-designs thus obtained are called, respectively, the complementary, the residual and the derived  $  t $-design with respect to the initial one. They are, respectively, a  $  t $-$  ( v, v- k, \lambda  ^ {c} ) $-design with
  
and a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204085.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204086.png" />-design.
+
$$
 +
\lambda  ^ {c}  = \
 +
\left ( \begin{array}{c}
 +
k \\
 +
t
 +
\end{array}
 +
\right )  ^ {-1}
 +
\left ( \begin{array}{c}
 +
v - k \\
 +
t
 +
\end{array}
 +
\right ) \lambda ,
 +
$$
 +
 
 +
a $  ( t - 1) $-$  ( v- 1, k, \lambda  ^ {r} ) $-design with
 +
 
 +
$$
 +
\lambda  ^ {r}  = ( v - k) ( k - t + 1)  ^ {-1} \lambda
 +
$$
 +
 
 +
and a  $  ( t - 1) $-$  ( v- 1, k- 1, \lambda ) $-design.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Dembowski,  "Finite geometries" , Springer  (1968)  pp. 254</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D.K. Ray-Chaudhuri,  R.M. Wilson,  "On t-designs"  ''Osaka J. Math.'' , '''12'''  (1975)  pp. 737–744</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  E.F. Assmus,  H.F. Mattson,  "Perfect codes and the Mathieu groups"  ''Arch. Math. Basel'' , '''17'''  (1966)  pp. 121–135</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.F. Assmus,  H.F. Mattson,  "New 5-designs"  ''J. Comb. Theory'' , '''6'''  (1969)  pp. 122–151</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N.V. Semakov,  V.A. Zinov'ev,  "Balanced codes and tactical configurations"  ''Problems Inform. Transmission'' , '''5''' :  3  (1969)  pp. 22–28  ''Probl. Peredachi Inform.'' , '''5''' :  3  (1969)  pp. 28–36</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  W.O. Alltop,  "An infiite class of 5-designs"  ''J. Comb. Theory'' , '''12'''  (1972)  pp. 390–395</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  V. Pless,  "Symmetry codes over GF(3) and new five-designs"  ''J. Comb. Theory'' , '''12'''  (1972)  pp. 119–142</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Dembowski,  "Finite geometries" , Springer  (1968)  pp. 254</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D.K. Ray-Chaudhuri,  R.M. Wilson,  "On t-designs"  ''Osaka J. Math.'' , '''12'''  (1975)  pp. 737–744</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  E.F. Assmus,  H.F. Mattson,  "Perfect codes and the Mathieu groups"  ''Arch. Math. Basel'' , '''17'''  (1966)  pp. 121–135</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.F. Assmus,  H.F. Mattson,  "New 5-designs"  ''J. Comb. Theory'' , '''6'''  (1969)  pp. 122–151</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N.V. Semakov,  V.A. Zinov'ev,  "Balanced codes and tactical configurations"  ''Problems Inform. Transmission'' , '''5''' :  3  (1969)  pp. 22–28  ''Probl. Peredachi Inform.'' , '''5''' :  3  (1969)  pp. 28–36</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  W.O. Alltop,  "An infiite class of 5-designs"  ''J. Comb. Theory'' , '''12'''  (1972)  pp. 390–395</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  V. Pless,  "Symmetry codes over GF(3) and new five-designs"  ''J. Comb. Theory'' , '''12'''  (1972)  pp. 119–142</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204087.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204088.png" />-design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204089.png" /> is also known as a [[Steiner system|Steiner system]] and denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204090.png" />; an arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204091.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204092.png" />-design is sometimes denoted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204093.png" />.
+
A t $-$  ( v , k, \lambda ) $-design with $  \lambda = 1 $
 +
is also known as a [[Steiner system|Steiner system]] and denoted by $  S( t, k, v ) $;  
 +
an arbitrary t $-$  ( v, k, \lambda ) $-design is sometimes denoted $  S _  \lambda  ( t, k, v) $.
  
Of particular interest is the existence of non-trivial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204094.png" />-designs without repeated blocks (i.e. no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204095.png" />-subset appears twice in the list of blocks); such <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204096.png" />-designs are called simple. L. Teirlinck [[#References|[a3]]] settled a long-standing conjecture by proving the existence of non-trivial simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204098.png" />-designs for every value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t09204099.png" />. A list of the known infinite families of simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040100.png" />-designs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040101.png" /> and a table of simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040102.png" />-designs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040103.png" /> is given in [[#References|[a4]]].
+
Of particular interest is the existence of non-trivial t $-designs without repeated blocks (i.e. no $  k $-subset appears twice in the list of blocks); such t $-designs are called simple. L. Teirlinck [[#References|[a3]]] settled a long-standing conjecture by proving the existence of non-trivial simple t $-designs for every value of t $.  
 +
A list of the known infinite families of simple t $-designs with t \geq  4 $
 +
and a table of simple t $-designs with $  v \leq  30 $
 +
is given in [[#References|[a4]]].
  
The only non-trivial tight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040104.png" />-design is the unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040105.png" />-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040106.png" />-design related to the Mathieu group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040107.png" /> (see [[#References|[a5]]]–[[#References|[a7]]]), and there are only finitely many tight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040108.png" />-designs for any fixed value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040109.png" /> (see [[#References|[a8]]]).
+
The only non-trivial tight $  4 $-design is the unique $  4 $-$  ( 23, 7, 1) $-design related to the Mathieu group $  M _ {23} $ (see [[#References|[a5]]]–[[#References|[a7]]]), and there are only finitely many tight $  2s $-designs for any fixed value $  s \geq  5 $ (see [[#References|[a8]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , '''I-II''' , North-Holland  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. Teirlinck,  "Non-trivial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040110.png" />-designs without repeated blocks exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040111.png" />"  ''Disc. Math.'' , '''65'''  (1987)  pp. 301–311</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  Y.M. Chee,  C.J. Colbourn,  D.L. Kreher,  "Simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040112.png" />-designs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040113.png" />"  ''Ars Comb.'' , '''29'''  (1990)  pp. 193–258</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  N. Ito,  "Tight 4-designs"  ''Osaka J. Math.'' , '''12'''  (1975)  pp. 493–522</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  H. Enomoto,  N. Ito,  R. Noda,  "Tight 4-designs"  ''Osaka J. Math.'' , '''16'''  (1979)  pp. 353–356</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Bremner,  "A diophantine equation arising from tight 4-designs"  ''Osaka J. Math.'' , '''16'''  (1979)  pp. 353–356</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E. Bannai,  "On tight designs"  ''Quart. J. Math. (Oxford)'' , '''28'''  (1977)  pp. 433–448</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.J. MacWilliams,  N.J.A. Sloane,  "The theory of error-correcting codes" , '''I-II''' , North-Holland  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. Teirlinck,  "Non-trivial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040110.png" />-designs without repeated blocks exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040111.png" />"  ''Disc. Math.'' , '''65'''  (1987)  pp. 301–311</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  Y.M. Chee,  C.J. Colbourn,  D.L. Kreher,  "Simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040112.png" />-designs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t092/t092040/t092040113.png" />"  ''Ars Comb.'' , '''29'''  (1990)  pp. 193–258</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  N. Ito,  "Tight 4-designs"  ''Osaka J. Math.'' , '''12'''  (1975)  pp. 493–522</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  H. Enomoto,  N. Ito,  R. Noda,  "Tight 4-designs"  ''Osaka J. Math.'' , '''16'''  (1979)  pp. 353–356</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Bremner,  "A diophantine equation arising from tight 4-designs"  ''Osaka J. Math.'' , '''16'''  (1979)  pp. 353–356</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E. Bannai,  "On tight designs"  ''Quart. J. Math. (Oxford)'' , '''28'''  (1977)  pp. 433–448</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR></table>

Latest revision as of 02:59, 21 March 2022


$ t $-design, $ t $-$ ( v, k, \lambda ) $-design on a $ v $-set $ S $

A $ t $-design is a system of $ k $-subsets (blocks) of the set $ S $ such that every $ t $-subset of elements of $ S $ appears in exactly $ \lambda $ blocks. The class of $ 2 $-designs coincides with the class of balanced incomplete block designs (cf. Block design). The name tactical configuration is given to an incidence system in which every set is incident with exactly $ k $ elements, while every element is incident with exactly $ r $ sets. A $ t $-design with $ t = k $ is called trivial. If a $ t $-design is not trivial, then

$$ t + 1 \leq k \leq v - 1 - t. $$

Every $ t $-design is an $ s $-design for any $ s \leq t $. The number $ \lambda _ {s} $ of occurrences of an arbitrary $ s $-subset in the blocks of a $ t $-design is given by the formula

$$ \lambda _ {s} = \ \left ( \begin{array}{c} k - s \\ t - s \end{array} \right ) ^ {-1} \left ( \begin{array}{c} v - s \\ t - s \end{array} \right ) \lambda ,\ \ 0 < s \leq t. $$

The condition that the $ \lambda _ {s} $ be integers is a necessary condition for the existence of a $ t $-design. In particular, for $ t \geq 2 $ every $ t $-design is a balanced incomplete block design.

The main question concerning $ t $-designs is the problem of their existence and construction. For a long time, for $ t > 3 $ only isolated examples were known; in particular $ 5 $-$ ( 12, 6, 1) $- and $ 5 $-$ ( 24, 8, 1) $-designs connected with the five-fold transitive Mathieu groups $ M _ {12} $ and $ M _ {24} $ (cf. Mathieu group), respectively. However, in the 1960s the connection between $ t $-designs and coding theory (cf. Code) was discovered (see, for example, [3] and [4]), and, starting from vectors with $ v $ non-zero coordinates, a way was shown of constructing a $ t $-design belonging to a linear $ ( n, k) $-code, which is a $ k $-dimensional vector subspace of an $ n $-dimensional space over a finite field (see [5] and [7]).

It is well known that $ t $-fold transitive groups other than the symmetric and the alternating groups lead to non-trivial $ t $-designs; this yields a few infinite series of $ 3 $-designs. With the help of ideas from group theory and geometry, infinite classes of $ 4 $- and $ 5 $-designs were also constructed (see for example [6]).

For the number $ b $ of blocks in a $ t $-design there is the inequality

$$ \tag{* } b \geq \ \left \{ \begin{array}{ll} \left ( \begin{array}{c} v \\ s \end{array} \right ) & \textrm{ if } t = 2s, v \geq k + s, \\ 2 \left ( \begin{array}{c} v - 1 \\ s \end{array} \right ) & \textrm{ if } t = 2s + 1, v - 1 \geq k + s, \\ \end{array} \right. $$

generalizing the Fisher inequality $ ( b \geq v) $ for balanced incomplete block designs. In the case of equality in (*), the $ t $-design is called tight. Tight $ t $-designs generalize symmetric $ 2 $-designs; in particular, for $ t = 2s $ the set of intersection numbers of blocks in a tight $ t $-design contains exactly $ s $ different elements.

The tight $ 3 $-designs are the Hadamard designs, i.e. they are the $ 3 $-$ ( 4n, 2n, n- 1) $-designs, while for $ s \geq 2 $ there are no non-trivial tight $ ( 2s + 1) $-designs. From a given $ t $-$ ( v, k, \lambda ) $-design three other $ t $-designs can be obtained: a) taking the complement in $ S $ of each block; b) discarding an arbitrary element and all the blocks that contain it; and c) taking blocks containing an arbitrarily chosen element and removing it from them. The $ t $-designs thus obtained are called, respectively, the complementary, the residual and the derived $ t $-design with respect to the initial one. They are, respectively, a $ t $-$ ( v, v- k, \lambda ^ {c} ) $-design with

$$ \lambda ^ {c} = \ \left ( \begin{array}{c} k \\ t \end{array} \right ) ^ {-1} \left ( \begin{array}{c} v - k \\ t \end{array} \right ) \lambda , $$

a $ ( t - 1) $-$ ( v- 1, k, \lambda ^ {r} ) $-design with

$$ \lambda ^ {r} = ( v - k) ( k - t + 1) ^ {-1} \lambda $$

and a $ ( t - 1) $-$ ( v- 1, k- 1, \lambda ) $-design.

References

[1] R. Dembowski, "Finite geometries" , Springer (1968) pp. 254
[2] D.K. Ray-Chaudhuri, R.M. Wilson, "On t-designs" Osaka J. Math. , 12 (1975) pp. 737–744
[3] E.F. Assmus, H.F. Mattson, "Perfect codes and the Mathieu groups" Arch. Math. Basel , 17 (1966) pp. 121–135
[4] E.F. Assmus, H.F. Mattson, "New 5-designs" J. Comb. Theory , 6 (1969) pp. 122–151
[5] N.V. Semakov, V.A. Zinov'ev, "Balanced codes and tactical configurations" Problems Inform. Transmission , 5 : 3 (1969) pp. 22–28 Probl. Peredachi Inform. , 5 : 3 (1969) pp. 28–36
[6] W.O. Alltop, "An infiite class of 5-designs" J. Comb. Theory , 12 (1972) pp. 390–395
[7] V. Pless, "Symmetry codes over GF(3) and new five-designs" J. Comb. Theory , 12 (1972) pp. 119–142

Comments

A $ t $-$ ( v , k, \lambda ) $-design with $ \lambda = 1 $ is also known as a Steiner system and denoted by $ S( t, k, v ) $; an arbitrary $ t $-$ ( v, k, \lambda ) $-design is sometimes denoted $ S _ \lambda ( t, k, v) $.

Of particular interest is the existence of non-trivial $ t $-designs without repeated blocks (i.e. no $ k $-subset appears twice in the list of blocks); such $ t $-designs are called simple. L. Teirlinck [a3] settled a long-standing conjecture by proving the existence of non-trivial simple $ t $-designs for every value of $ t $. A list of the known infinite families of simple $ t $-designs with $ t \geq 4 $ and a table of simple $ t $-designs with $ v \leq 30 $ is given in [a4].

The only non-trivial tight $ 4 $-design is the unique $ 4 $-$ ( 23, 7, 1) $-design related to the Mathieu group $ M _ {23} $ (see [a5][a7]), and there are only finitely many tight $ 2s $-designs for any fixed value $ s \geq 5 $ (see [a8]).

References

[a1] F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , I-II , North-Holland (1978)
[a2] T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986)
[a3] L. Teirlinck, "Non-trivial -designs without repeated blocks exist for all " Disc. Math. , 65 (1987) pp. 301–311
[a4] Y.M. Chee, C.J. Colbourn, D.L. Kreher, "Simple -designs with " Ars Comb. , 29 (1990) pp. 193–258
[a5] N. Ito, "Tight 4-designs" Osaka J. Math. , 12 (1975) pp. 493–522
[a6] H. Enomoto, N. Ito, R. Noda, "Tight 4-designs" Osaka J. Math. , 16 (1979) pp. 353–356
[a7] A. Bremner, "A diophantine equation arising from tight 4-designs" Osaka J. Math. , 16 (1979) pp. 353–356
[a8] E. Bannai, "On tight designs" Quart. J. Math. (Oxford) , 28 (1977) pp. 433–448
[a9] M. Hall, "Combinatorial theory" , Blaisdell (1967)
How to Cite This Entry:
Tactical configuration. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tactical_configuration&oldid=49466
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article