Namespaces
Variants
Actions

Difference between revisions of "Pasch configuration"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link)
Line 3: Line 3:
 
A collection of four triples isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300401.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300402.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300403.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300404.png" />. Pasch configurations have been studied extensively in the context of Steiner triple systems.
 
A collection of four triples isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300401.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300402.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300403.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300404.png" />. Pasch configurations have been studied extensively in the context of Steiner triple systems.
  
A Steiner triple system of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300405.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300406.png" />, is an ordered pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300407.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300408.png" /> is a set of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300409.png" />, called elements or points, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004010.png" /> is a collection of triples, also called lines or blocks, which collectively have the property that every pair of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004011.png" /> occur in precisely one triple. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004012.png" /> exist if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004013.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004014.png" />, [[#References|[a5]]] (cf. also [[Steiner system|Steiner system]]). To within isomorphism, the Steiner triple systems of orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004016.png" /> are unique, but for all greater orders the structure is not unique. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004018.png" />-configuration in a Steiner triple system is a collection of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004019.png" /> lines whose union contains precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004020.png" /> points. A configuration whose number of occurrences in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004021.png" /> depends only upon the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004022.png" /> and not on the structure of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004023.png" /> is called constant and otherwise variable. There are two configurations with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004024.png" /> and five with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004025.png" />, all of which are constant. There are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004026.png" /> configurations with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004027.png" />, of which the Pasch configuration or quadrilateral is the unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004028.png" />-configuration and the one containing the least number of points. Five of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004029.png" />-line configurations are constant but the Pasch configuration is variable. It was shown in [[#References|[a7]]] that the number of occurrences of all the other variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004030.png" />-line configurations can be expressed in terms of the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004031.png" /> and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004032.png" /> of Pasch configurations in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004033.png" />.
+
A [[Steiner triple system]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300405.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300406.png" />, is an ordered pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300407.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300408.png" /> is a set of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p1300409.png" />, called elements or points, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004010.png" /> is a collection of triples, also called lines or blocks, which collectively have the property that every pair of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004011.png" /> occur in precisely one triple. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004012.png" /> exist if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004013.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004014.png" />, [[#References|[a5]]] (cf. also [[Steiner system|Steiner system]]). To within isomorphism, the Steiner triple systems of orders <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004016.png" /> are unique, but for all greater orders the structure is not unique. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004018.png" />-configuration in a Steiner triple system is a collection of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004019.png" /> lines whose union contains precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004020.png" /> points. A configuration whose number of occurrences in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004021.png" /> depends only upon the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004022.png" /> and not on the structure of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004023.png" /> is called constant and otherwise variable. There are two configurations with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004024.png" /> and five with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004025.png" />, all of which are constant. There are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004026.png" /> configurations with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004027.png" />, of which the Pasch configuration or quadrilateral is the unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004028.png" />-configuration and the one containing the least number of points. Five of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004029.png" />-line configurations are constant but the Pasch configuration is variable. It was shown in [[#References|[a7]]] that the number of occurrences of all the other variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004030.png" />-line configurations can be expressed in terms of the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004031.png" /> and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004032.png" /> of Pasch configurations in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004033.png" />.
  
 
The above gives motivation to the problem of constructing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004034.png" /> containing no Pasch configurations, so-called anti-Pasch or quadrilateral free Steiner triple systems. A solution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004035.png" /> was first given by A.E. Brouwer ([[#References|[a1]]], see also [[#References|[a8]]]) and it was a long-standing conjecture that anti-Pasch <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004036.png" /> also exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004038.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004039.png" />. This was settled in the affirmative in two papers, [[#References|[a6]]] and [[#References|[a10]]], published in 2000. The proof resolves the first case of a conjecture by P. Erdős, [[#References|[a3]]], that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004040.png" /> there is an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004041.png" /> so that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004043.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004044.png" />, there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004045.png" /> avoiding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004046.png" />-configurations for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004047.png" />. Anti-Pasch <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004048.png" /> have application to erasure-correcting codes, [[#References|[a2]]]. The theoretical maximum number of Pasch configurations in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004049.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004050.png" /> but this is achieved only in the point-line designs obtained from the projective spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004051.png" />, [[#References|[a9]]].
 
The above gives motivation to the problem of constructing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004034.png" /> containing no Pasch configurations, so-called anti-Pasch or quadrilateral free Steiner triple systems. A solution for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004035.png" /> was first given by A.E. Brouwer ([[#References|[a1]]], see also [[#References|[a8]]]) and it was a long-standing conjecture that anti-Pasch <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004036.png" /> also exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004038.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004039.png" />. This was settled in the affirmative in two papers, [[#References|[a6]]] and [[#References|[a10]]], published in 2000. The proof resolves the first case of a conjecture by P. Erdős, [[#References|[a3]]], that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004040.png" /> there is an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004041.png" /> so that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004043.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004044.png" />, there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004045.png" /> avoiding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004046.png" />-configurations for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004047.png" />. Anti-Pasch <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004048.png" /> have application to erasure-correcting codes, [[#References|[a2]]]. The theoretical maximum number of Pasch configurations in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004049.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004050.png" /> but this is achieved only in the point-line designs obtained from the projective spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004051.png" />, [[#References|[a9]]].

Revision as of 15:12, 19 March 2018

quadrilateral

A collection of four triples isomorphic to , , , . Pasch configurations have been studied extensively in the context of Steiner triple systems.

A Steiner triple system of order , , is an ordered pair where is a set of cardinality , called elements or points, and is a collection of triples, also called lines or blocks, which collectively have the property that every pair of distinct elements of occur in precisely one triple. exist if and only if or , [a5] (cf. also Steiner system). To within isomorphism, the Steiner triple systems of orders and are unique, but for all greater orders the structure is not unique. A -configuration in a Steiner triple system is a collection of lines whose union contains precisely points. A configuration whose number of occurrences in an depends only upon the order and not on the structure of the is called constant and otherwise variable. There are two configurations with and five with , all of which are constant. There are configurations with , of which the Pasch configuration or quadrilateral is the unique -configuration and the one containing the least number of points. Five of the -line configurations are constant but the Pasch configuration is variable. It was shown in [a7] that the number of occurrences of all the other variable -line configurations can be expressed in terms of the order and the number of Pasch configurations in the .

The above gives motivation to the problem of constructing containing no Pasch configurations, so-called anti-Pasch or quadrilateral free Steiner triple systems. A solution for was first given by A.E. Brouwer ([a1], see also [a8]) and it was a long-standing conjecture that anti-Pasch also exist for all , or . This was settled in the affirmative in two papers, [a6] and [a10], published in 2000. The proof resolves the first case of a conjecture by P. Erdős, [a3], that for every there is an integer so that for every , or , there is an avoiding -configurations for . Anti-Pasch have application to erasure-correcting codes, [a2]. The theoretical maximum number of Pasch configurations in an is but this is achieved only in the point-line designs obtained from the projective spaces , [a9].

The Pasch configuration is an example of a so-called trade. A pair of distinct collections of blocks is said to be mutually -balanced if each -element subset of the base set is contained in precisely the same number of blocks of as of . Each collection , is then referred to as a trade. The Pasch configuration is the smallest trade that can occur in a Steiner triple system. If is the collection , , , , then, by replacing each triple with its complement, a collection , , , , , is obtained which contains precisely the same pairs as . This transformation is known as a Pasch switch, and when applied to a Steiner triple system yields another, usually non-isomorphic, Steiner triple system. There are non-isomorphic s, of which precisely one is anti-Pasch. It was shown in [a4] that all of the remaining systems can be obtained from one another by successive Pasch switches. Other relevant papers in this area are [a11] and [a12].

The number of Pasch configurations and their distribution within a Steiner triple system is an invariant and provides a simple and useful test to help in determining whether two systems are isomorphic.

References

[a1] A.E. Brouwer, "Steiner triple systems without forbidden subconfigurations" Rept. Math. Centrum Amsterdam , ZW104/77 (1977)
[a2] C.J. Colbourn, J.H. Dinitz, D.R. Stinson, "Applications of combinatorial designs to communications, cryptography and networking" London Math. Soc. Lecture Notes , 267 (1999) pp. 37–100
[a3] P. Erdös, "Problems and results in combinatorial analysis" Creation in Math. , 9 (1976) pp. 25
[a4] P.B. Gibbons, "Computing techniques for the construction and analysis of block designs" Techn. Rept. Dept. Computer Sci. Univ. Toronto , 92 (1976)
[a5] T.P. Kirkman, "On a problem in combinations" Cambridge and Dublin Math. J. , 2 (1847) pp. 191–204
[a6] A.C.H. Ling, C.J. Colbourn, M.J. Grannell, T.S. Griggs, "Construction techniques for anti-Pasch Steiner triple systems" J. London Math. Soc. (2) , 61 (2000) pp. 641–657
[a7] M.J. Grannell, T.S. Griggs, E. Mendelsohn, "A small basis for four-line configurations in Steiner triple systems" J. Combin. Designs , 3 (1995) pp. 51–59
[a8] T.S. Griggs, J.P. Murphy, J.S. Phelan, "Anti-Pasch Steiner triple systems" J. Combin. Inform. & Syst. Sci. , 15 (1990) pp. 79–84
[a9] D.R. Stinson, Y.J. Wei, "Some results on quadrilaterals in Steiner triple systems" Discr. Math. , 105 (1992) pp. 207–219
[a10] M.J. Grannell, T.S. Griggs, C.A. Whitehead, "The resolution of the anti-Pasch conjecture" J. Combin. Designs , 8 (2000) pp. 300–309
[a11] M.J. Grannell, T.S. Griggs, J.P. Murphy, "Twin Steiner triple systems" Discr. Math. , 167/8 (1997) pp. 341–352
[a12] M.J. Grannell, T.S. Griggs, J.P. Murphy, "Switching cycles in Steiner triple systems" Utilitas Math. , 56 (1999) pp. 3–21
How to Cite This Entry:
Pasch configuration. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pasch_configuration&oldid=42972
This article was adapted from an original article by M.J. GrannellT.S. Griggs (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article