# Pasch configuration

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.

How to Cite This Entry:
Pasch configuration. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pasch_configuration&oldid=51165
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