Pasch configuration

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