Difference between revisions of "Tactical configuration"
m (links) |
m (link) |
||
Line 19: | Line 19: | ||
<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> | <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> | ||
− | 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. | + | 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. |
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 | 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 |
Revision as of 19:37, 4 January 2016
-design,
-
-design on a
-set
A -design is a system of
-subsets (blocks) of the set
such that every
-subset of elements of
appears in exactly
blocks. The class of
-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
elements, while every element is incident with exactly
sets. A
-design with
is called trivial. If a
-design is not trivial, then
![]() |
Every -design is an
-design for any
. The number
of occurrences of an arbitrary
-subset in the blocks of a
-design is given by the formula
![]() |
The condition that the be integers is a necessary condition for the existence of a
-design. In particular, for
every
-design is a balanced incomplete block design.
The main question concerning -designs is the problem of their existence and construction. For a long time, for
only isolated examples were known; in particular
-
- and
-
-designs connected with the five-fold transitive Mathieu groups
and
(cf. Mathieu group), respectively. However, in the 1960s the connection between
-designs and coding theory (cf. Code) was discovered (see, for example, [3] and [4]), and, starting from vectors with
non-zero coordinates, a way was shown of constructing a
-design belonging to a linear
-code, which is a
-dimensional vector subspace of an
-dimensional space over a finite field (see [5] and [7]).
It is well known that -fold transitive groups other than the symmetric and the alternating groups lead to non-trivial
-designs; this yields a few infinite series of
-designs. With the help of ideas from group theory and geometry, infinite classes of
- and
-designs were also constructed (see for example [6]).
For the number of blocks in a
-design there is the inequality
![]() | (*) |
generalizing the Fisher inequality for balanced incomplete block designs. In the case of equality in (*), the
-design is called tight. Tight
-designs generalize symmetric
-designs; in particular, for
the set of intersection numbers of blocks in a tight
-design contains exactly
different elements.
The tight -designs are the Hadamard designs, i.e. they are the
-
-designs, while for
there are no non-trivial tight
-designs. From a given
-
-design three other
-designs can be obtained: a) taking the complement in
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
-designs thus obtained are called, respectively, the complementary, the residual and the derived
-design with respect to the initial one. They are, respectively, a
-
-design with
![]() |
a -
-design with
![]() |
and a -
-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 -
-design with
is also known as a Steiner system and denoted by
; an arbitrary
-
-design is sometimes denoted
.
Of particular interest is the existence of non-trivial -designs without repeated blocks (i.e. no
-subset appears twice in the list of blocks); such
-designs are called simple. L. Teirlinck [a3] settled a long-standing conjecture by proving the existence of non-trivial simple
-designs for every value of
. A list of the known infinite families of simple
-designs with
and a table of simple
-designs with
is given in [a4].
The only non-trivial tight -design is the unique
-
-design related to the Mathieu group
(see [a5]–[a7]), and there are only finitely many tight
-designs for any fixed value
(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 ![]() ![]() |
[a4] | Y.M. Chee, C.J. Colbourn, D.L. Kreher, "Simple ![]() ![]() |
[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) |
Tactical configuration. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tactical_configuration&oldid=37364