View source for Pasch configuration

''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 [[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 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 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====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.E. Brouwer,   "Steiner triple systems without forbidden subconfigurations"  ''Rept. Math. Centrum Amsterdam'' , '''ZW104/77'''  (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P. Erdös,   "Problems and results in combinatorial analysis"  ''Creation in Math.'' , '''9'''  (1976)  pp. 25</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.B. Gibbons,   "Computing techniques for the construction and analysis of block designs"  ''Techn. Rept. Dept. Computer Sci. Univ. Toronto'' , '''92'''  (1976)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  T.P. Kirkman,   "On a problem in combinations"  ''Cambridge and Dublin Math. J.'' , '''2'''  (1847)  pp. 191–204</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  T.S. Griggs,   J.P. Murphy,   J.S. Phelan,   "Anti-Pasch Steiner triple systems"  ''J. Combin. Inform. &amp; Syst. Sci.'' , '''15'''  (1990)  pp. 79–84</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  D.R. Stinson,   Y.J. Wei,   "Some results on quadrilaterals in Steiner triple systems"  ''Discr. Math.'' , '''105'''  (1992)  pp. 207–219</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  M.J. Grannell,   T.S. Griggs,   C.A. Whitehead,   "The resolution of the anti-Pasch conjecture"  ''J. Combin. Designs'' , '''8'''  (2000)  pp. 300–309</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  M.J. Grannell,   T.S. Griggs,   J.P. Murphy,   "Twin Steiner triple systems"  ''Discr. Math.'' , '''167/8'''  (1997)  pp. 341–352</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  M.J. Grannell,   T.S. Griggs,   J.P. Murphy,   "Switching cycles in Steiner triple systems"  ''Utilitas Math.'' , '''56'''  (1999)  pp. 3–21</TD></TR></table>