[#P2788] Components of the Pasch-switch graph on STS(15) classes
Problem. Form a graph whose vertices are the \(80\) isomorphism classes of Steiner triple systems on 15 points. Join two distinct classes when labeled representatives differ by one Pasch switch. Determine all connected components and the diameter of each component.
1Context
Trade graphs organize local transformations between designs. A complete edge list remains useful for sampling, canonical augmentation, and testing broader trade sets even after the requested invariants are known.
2Problem setup
Definition 1 (A Steiner triple system STS(15). A Steiner triple system STS(15) is a family of triples on 15 points in which every pair occurs in exactly one triple.
Definition 2 (A Pasch switch replaces \(abc,ade,fbd,fce\) by \(abd,ace,fbc,fde\) on six distinct points; the two four-block families cover the same pairs). A Pasch switch replaces \(abc,ade,fbd,fce\) by \(abd,ace,fbc,fde\) on six distinct points; the two four-block families cover the same pairs.
Definition 3 (Two systems are identified when a permutation of the 15 points maps one block family to the other). Two systems are identified when a permutation of the 15 points maps one block family to the other.
Remark 1. Trade graphs organize local transformations between designs. A complete edge list remains useful for sampling, canonical augmentation, and testing broader trade sets even after the requested invariants are known.
3What counts as a solution
- Provide canonical representatives for all 80 classes, replay every Pasch-switch adjacency, list the connected components, and certify each reported diameter with paths and matching distance lower bounds.
1Status
Current status (Current status and unresolved remainder). OPEN (partially resolved): The Pasch-switch graph has two known connected components. One contains 79 isomorphism classes, and the unique anti-Pasch STS(15) class is an isolated vertex. The diameter of the 79-vertex component was not located in the 2026-07-31 literature audit and is the sole remaining question. Provide canonical representatives for all 80 classes, replay every Pasch-switch adjacency, list the connected components, and certify each reported diameter with paths and matching distance lower bounds.[1]
1Records
Notes and companion material
Original intake status. OPEN (partially resolved): The Pasch-switch graph has two known connected components. One contains 79 isomorphism classes, and the unique anti-Pasch STS(15) class is an isolated vertex. The diameter of the 79-vertex component was not located in the 2026-07-31 literature audit and is the sole remaining question.
- 2026-07-28: Gibbons' 1976 computational analysis established that 79 of the 80 STS(15) classes are connected by Pasch switches. The remaining class is the unique anti-Pasch system and therefore has no incident Pasch-switch edge.
- 2026-07-28: Colbourn et al., Section 2.3, explicitly state that all but one of the 80 classes contain a Pasch configuration and that any one of those 79 can be transformed to any other by Pasch switches. Klin, Reichard, and Woldar, Section 6.3, describe this exact quotient graph and record component sizes 79 and 1.
- 2026-07-28: Searches of the STS(15) catalogue, Pasch-switching papers, later cycle-switching literature, and exact phrases involving the graph diameter did not locate a published diameter for the 79-class component.
- A complete answer now needs the diameter of the 79-vertex component, supported by a replayable quotient edge list, shortest paths between an eccentric pair, and matching distance lower bounds.
Recorded example 1. The two four-block families in the definition give one local switch. Any STS containing the first family can be changed by replacing it with the second.
Computational notes
- Every STS(15) has \(15\cdot14/6=35\) blocks. No component enumeration was performed for this record.
How the 2 records connect
ProblemComponents of the Pasch-switch graph on STS(15) classes
2See also
- Orders of ternary row-orthogonal matrices with a full rowdesign theory
- Hadamard matrix conjecturedesign theory
- Largest cyclic 3-(31,5,1) packingdesign theory
How to cite
TheoremDB contributors, “Components of the Pasch-switch graph on STS(15) classes,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/sts15-pasch-switch-graphThis page as plain text: sts15-pasch-switch-graph.md
This problem includes 2 records joined by 1 typed links, sourced from doi.org[1], current as of July 31, 2026.
1References
- Packet source. F. N. Cole, Louise D. Cummings, and Henry S. White, The Complete Enumeration of Triad Systems in 15 Elements, Proceedings of the National Academy of Sciences 3(3) (1917), 197-199. Complete enumeration of the isomorphism classes on fifteen points. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Primary source for the fact that the quotient graph has exactly 80 vertices.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.For Components of the Pasch-switch graph on STS(15) classes: Primary source for the fact that the quotient graph has exactly 80 vertices.Source named by the research packet.
- Rudolf A. Mathon, Kevin T. Phelps, and Alexander Rosa, Small Steiner Triple Systems and Their Properties, Ars Combinatoria 15 (1983), 3-110. Catalogue and standard numbering of the 80 STS(15) classes. ↗website · primary source · checked 2026-07-31Source use: original summary.Provides the canonical representatives and class invariants needed to construct and audit every vertex of the quotient graph.For Components of the Pasch-switch graph on STS(15) classes: Provides the canonical representatives and class invariants needed to construct and audit every vertex of the quotient graph.
- Peter B. Gibbons, Computing Techniques for the Construction and Analysis of Block Designs, Ph.D. thesis, University of Toronto, Technical Report 92, 1976. Computational analysis of the STS(15) catalogue under four-cycle, or Pasch, trades. ↗website · primary source · checked 2026-07-31Source use: original summary.Primary computational source for the result that 79 of the 80 classes lie in one Pasch-switch component.Source used to assess the problem's recorded status.For Components of the Pasch-switch graph on STS(15) classes: Primary computational source for the result that 79 of the 80 classes lie in one Pasch-switch component.
- M. J. Grannell, T. S. Griggs, and J. P. Murphy, Switching Cycles in Steiner Triple Systems, Utilitas Mathematica 56 (1999), 3-21. Cycle-switching definitions and the four-cycle case. ↗website · primary source · checked 2026-07-31Source use: original summary.Develops the switching framework in which a Pasch switch is the shortest cycle trade and relates it to transformations among isomorphism classes.For Components of the Pasch-switch graph on STS(15) classes: Develops the switching framework in which a Pasch switch is the shortest cycle trade and relates it to transformations among isomorphism classes.
- Charles J. Colbourn, Anthony D. Forbes, Mike J. Grannell, Terry S. Griggs, Petteri Kaski, Patric R. J. Östergård, David A. Pike, and Olli Pottonen, Properties of the Steiner Triple Systems of Order 19, Electronic Journal of Combinatorics 17(1) (2010), R98. Section 2.3, especially pages 6-7. ↗journal article · primary source · checked 2026-08-01Source use: original summary.States explicitly that one STS(15) class is anti-Pasch and the other 79 are mutually reachable by Pasch switches, which determines the two connected components.Source used to assess the problem's recorded status.For Components of the Pasch-switch graph on STS(15) classes: States explicitly that one STS(15) class is anti-Pasch and the other 79 are mutually reachable by Pasch switches, which determines the two connected components.
- Mikhail Klin, Sven Reichard, and Andrew Woldar, Siamese Combinatorial Objects via Computer Algebra Experimentation, in Algorithmic Algebraic Combinatorics and Gröbner Bases, Springer, 2009, 67-112. Section 6.3, A Few Words About STS(15). ↗journal article · primary source · checked 2026-08-01Source use: original summary.Describes this exact graph on the 80 isomorphism classes and records its component sizes as 79 and 1, identifying the isolated class as STS(15) number 80.Source used to assess the problem's recorded status.For Components of the Pasch-switch graph on STS(15) classes: Describes this exact graph on the 80 isomorphism classes and records its component sizes as 79 and 1, identifying the isolated class as STS(15) number 80.
- M. J. Grannell and T. S. Griggs, The Pasch Configuration, Encyclopaedia of Mathematics, Supplement III, Kluwer, 2002, 299-300. Definition of the switch and the STS(15) paragraph. ↗website · primary source · checked 2026-07-31Source use: original summary.Concise reference for the local move, the unique anti-Pasch class, and connectivity of the remaining 79 classes.For Components of the Pasch-switch graph on STS(15) classes: Concise reference for the local move, the unique anti-Pasch class, and connectivity of the remaining 79 classes.
Original finite reconfiguration question using the classical Pasch trade.