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

✍ Scribed by Peter Dukes; Eric Mendelsohn

• Publisher: John Wiley and Sons
• Year: 2005
• Tongue: English
• Weight: 182 KB
• Volume: 13
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20033

✦ Synopsis

Abstract

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.