Quasi‐embeddings of Steiner triple systems, or Steiner triple systems of different orders with maximum intersection

In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u , v ≡ 1,3 (mod 6), u < v < 2 u  +  1, we ask for the minimum r such that there exists a Steiner triple system $(U,\,{\cal B}),\,|U|=u$ such that some partial system $(U,{\cal B}\,\backslash{\partial})$ can be completed to an STS $(v),\,(V,\,{\cal B}{^\prime})$ , where |∂| = r . In other words, in order to “quasi‐embed” an STS( u ) into an STS( v ), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity ( u ( u − 1)/6) − r as the maximum intersection of an STS( u ) and an STS( v ) with u < v . We conjecture that the necessary minimum r  =  ( v − u ) (2 u  +  1 − v )/6 can be achieved, except when u  =  6 t  +  1 and v = 6 t  +  3, in which case it is r  =  3 t for t ≠ 2, or r  =  7 when t  =  2. Using small examples and recursion, we solve the cases v − u  =  2 and 4, asymptotically solve the cases v − u  =  6, 8, and 10, and further show for given v − u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v − u ). Some results are obtained for v close to 2 u  +  1 as well. The cases where ≈ 3 u /2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.