Namespaces
Variants
Actions

Difference between revisions of "Pasch configuration"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (texified)
 
Line 1: Line 1:
 
''quadrilateral''
 
''quadrilateral''
  
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 $\{a,b,c\}$, $\{a,y,z\}$, $\{x,b,z\}$, $\{x,y,c\}$. 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 $v$, $\text{STS}(v)$, is an ordered pair $(V,B)$ where $V$ is a set of cardinality $v$, called elements or points, and $B$ is a collection of triples, also called lines or blocks, which collectively have the property that every pair of distinct elements of $V$ occur in precisely one triple. $\text{STS}(v)$ exist if and only if $v\equiv 1$ or $3(\text{mod}6)$, [[#References|[a5]]] (cf. also [[Steiner system|Steiner system]]). To within isomorphism, the Steiner triple systems of orders $7$ and $9$ are unique, but for all greater orders the structure is not unique. A $(p,l)$-configuration in a Steiner triple system is a collection of $l$ lines whose union contains precisely $p$ points. A configuration whose number of occurrences in an $\text{STS}(v)$ depends only upon the order $v$ and not on the structure of the $\text{STS}(v)$ is called constant and otherwise variable. There are two configurations with $l=2$ and five with $l=3$, all of which are constant. There are $16$ configurations with $l=4$, of which the Pasch configuration or quadrilateral is the unique $(6,4)$-configuration and the one containing the least number of points. Five of the $4$-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 $4$-line configurations can be expressed in terms of the order $v$ and the number $c$ of Pasch configurations in the $\text{STS}(v)$.
  
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 $\text{STS}(v)$ containing no Pasch configurations, so-called anti-Pasch or quadrilateral free Steiner triple systems. A solution for $v\equiv3\text{mod}6$ was first given by A.E. Brouwer ([[#References|[a1]]], see also [[#References|[a8]]]) and it was a long-standing conjecture that anti-Pasch $\text{STS}(v)$ also exist for all $v\equiv1(\text{mod}6)$, $v\not=7$ or $13$. 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 $m\geq4$ there is an integer $v_m$ so that for every $v\geq v_m$, $v\equiv1$ or $3(\text{mod}6)$, there is an $\text{STS}(v)$ avoiding $(l+2,l)$-configurations for $4\leq l\leq m$. Anti-Pasch $\text{STS}(v)$ have application to erasure-correcting codes, [[#References|[a2]]]. The theoretical maximum number of Pasch configurations in an $\text{STS}(v)$ is $v(v-1)(v-3)/24$ but this is achieved only in the point-line designs obtained from the projective spaces $\text{PG}(n,2)$, [[#References|[a9]]].
  
The Pasch configuration is an example of a so-called trade. A pair of distinct collections of blocks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004052.png" /> is said to be mutually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004054.png" />-balanced if each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004055.png" />-element subset of the base set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004056.png" /> is contained in precisely the same number of blocks of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004057.png" /> as of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004058.png" />. Each collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004059.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004060.png" /> is then referred to as a trade. The Pasch configuration is the smallest trade that can occur in a Steiner triple system. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004061.png" /> is the collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004065.png" />, then, by replacing each triple with its complement, a collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004069.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004070.png" />, is obtained which contains precisely the same pairs as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004071.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004072.png" /> non-isomorphic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004073.png" />s, of which precisely one is anti-Pasch. It was shown in [[#References|[a4]]] that all of the remaining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p130/p130040/p13004074.png" /> systems can be obtained from one another by successive Pasch switches. Other relevant papers in this area are [[#References|[a11]]] and [[#References|[a12]]].
+
The Pasch configuration is an example of a so-called trade. A pair of distinct collections of blocks $(T_1,T_2)$ is said to be mutually $t$-balanced if each $t$-element subset of the base set $V$ is contained in precisely the same number of blocks of $T_1$ as of $T_2$. Each collection $T_1$, $T_2$ is then referred to as a trade. The Pasch configuration is the smallest trade that can occur in a Steiner triple system. If $T_1$ is the collection $\{a,b,c\}$, $\{a,y,z\}$, $\{x,b,z\}$, $\{x,y,c\}$, then, by replacing each triple with its complement, a collection $T_2$, $\{x,y,z\}$, $\{x,b,c\}$, $\{a,y,c\}$, $\{a,b,z\}$, is obtained which contains precisely the same pairs as $T_1$. 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 $80$ non-isomorphic $\text{STS}(15)$s, of which precisely one is anti-Pasch. It was shown in [[#References|[a4]]] that all of the remaining $79$ systems can be obtained from one another by successive Pasch switches. Other relevant papers in this area are [[#References|[a11]]] and [[#References|[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.
 
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.

Latest revision as of 10:53, 2 January 2021

quadrilateral

A collection of four triples isomorphic to $\{a,b,c\}$, $\{a,y,z\}$, $\{x,b,z\}$, $\{x,y,c\}$. Pasch configurations have been studied extensively in the context of Steiner triple systems.

A Steiner triple system of order $v$, $\text{STS}(v)$, is an ordered pair $(V,B)$ where $V$ is a set of cardinality $v$, called elements or points, and $B$ is a collection of triples, also called lines or blocks, which collectively have the property that every pair of distinct elements of $V$ occur in precisely one triple. $\text{STS}(v)$ exist if and only if $v\equiv 1$ or $3(\text{mod}6)$, [a5] (cf. also Steiner system). To within isomorphism, the Steiner triple systems of orders $7$ and $9$ are unique, but for all greater orders the structure is not unique. A $(p,l)$-configuration in a Steiner triple system is a collection of $l$ lines whose union contains precisely $p$ points. A configuration whose number of occurrences in an $\text{STS}(v)$ depends only upon the order $v$ and not on the structure of the $\text{STS}(v)$ is called constant and otherwise variable. There are two configurations with $l=2$ and five with $l=3$, all of which are constant. There are $16$ configurations with $l=4$, of which the Pasch configuration or quadrilateral is the unique $(6,4)$-configuration and the one containing the least number of points. Five of the $4$-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 $4$-line configurations can be expressed in terms of the order $v$ and the number $c$ of Pasch configurations in the $\text{STS}(v)$.

The above gives motivation to the problem of constructing $\text{STS}(v)$ containing no Pasch configurations, so-called anti-Pasch or quadrilateral free Steiner triple systems. A solution for $v\equiv3\text{mod}6$ was first given by A.E. Brouwer ([a1], see also [a8]) and it was a long-standing conjecture that anti-Pasch $\text{STS}(v)$ also exist for all $v\equiv1(\text{mod}6)$, $v\not=7$ or $13$. 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 $m\geq4$ there is an integer $v_m$ so that for every $v\geq v_m$, $v\equiv1$ or $3(\text{mod}6)$, there is an $\text{STS}(v)$ avoiding $(l+2,l)$-configurations for $4\leq l\leq m$. Anti-Pasch $\text{STS}(v)$ have application to erasure-correcting codes, [a2]. The theoretical maximum number of Pasch configurations in an $\text{STS}(v)$ is $v(v-1)(v-3)/24$ but this is achieved only in the point-line designs obtained from the projective spaces $\text{PG}(n,2)$, [a9].

The Pasch configuration is an example of a so-called trade. A pair of distinct collections of blocks $(T_1,T_2)$ is said to be mutually $t$-balanced if each $t$-element subset of the base set $V$ is contained in precisely the same number of blocks of $T_1$ as of $T_2$. Each collection $T_1$, $T_2$ is then referred to as a trade. The Pasch configuration is the smallest trade that can occur in a Steiner triple system. If $T_1$ is the collection $\{a,b,c\}$, $\{a,y,z\}$, $\{x,b,z\}$, $\{x,y,c\}$, then, by replacing each triple with its complement, a collection $T_2$, $\{x,y,z\}$, $\{x,b,c\}$, $\{a,y,c\}$, $\{a,b,z\}$, is obtained which contains precisely the same pairs as $T_1$. 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 $80$ non-isomorphic $\text{STS}(15)$s, of which precisely one is anti-Pasch. It was shown in [a4] that all of the remaining $79$ 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