On semi-planar Steiner quasigroups

A Steiner triple system (briefly ST) is in 1-1 correspondence with a Steiner quasigroup or squag (briefly SQ) [B. Ganter, H. Werner, Co-ordinatizing Steiner systems, Ann. Discrete Math. 7 (1980) 3-24; C.C. Lindner, A. Rosa, Steiner quadruple systems: A survey, Discrete Math. 21 (1979) 147-181]. It is well known that for each n≡1 or 3 (mod 6) there is a planar squag of cardinality n [J. Doyen, Sur la structure de certains systems triples de Steiner, Math. Z. 111 (1969) 289-300]. Quackenbush expected that there should also be semi-planar squags [R.W. Quackenbush, Varieties of Steiner loops and Steiner quasigroups, Canad. J. Math. 28 (1976) 1187-1198]. A simple squag is semi-planar if every triangle either generates the whole squag or the 9-element squag. The first author has constructed a semi-planar squag of cardinality 3n for all n>3 and n≡1 or 3 (mod 6) [M.H. Armanious, Semi-planar Steiner quasigroups of cardinality 3n, Australas. J. Combin. 27 (2003) 13-27]. In fact, this construction supplies us with semi-planar squags having only nontrivial subsquags of cardinality 9. Our aim in this article is to give a recursive construction as n→3n for semi-planar squags. This construction permits us to construct semi-planar squags having nontrivial subsquags of cardinality >9. Consequently, we may say that there are semi-planar (or semi-planar ) for each positive integer m and each n≡1 or 3 (mod 6) with n>3 having only medial subsquags at most of cardinality 3^ν (sub-) for each ν∈{1,2,…,m+1}.     

On the number of triangular embeddings of complete graphs and complete tripartite graphs

We prove that for every prime number p and odd m>1, as s→∞, there are at least w face 2‐colorable triangular embeddings of K_{w, w, w}, where w = m·p^s. For both orientable and nonorientable embeddings, this result implies that for infinitely many infinite families of z, there is a constant c>0 for which there are at least z nonisomorphic face 2‐colorable triangular embeddings of K_z. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs

We prove that, for a certain positive constant a and for an infinite set of values of n, the number of nonisomorphic triangular embeddings of the complete graph K_n is at least n^an2. A similar lower bound is also given, for an infinite set of values of n, on the number of nonisomorphic triangular embeddings of the complete regular tripartite graph K_n,n,n.     

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 < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , 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) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t 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 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.     

A proof of Lindner's conjecture on embeddings of partial Steiner triple systems

Lindner's conjecture that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if and is proved. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 63–89, 2009     

Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete

Deciding whether an arbitrary partial commutative quasigroup can be completed is known to be NP-complete. Here, we prove that it remains NP-complete even if the partial quasigroup is constructed, in the standard way, from a partial Steiner triple system. This answers a question raised by Rosa in [A. Rosa, On a class of completable partial edge-colourings, Discrete Appl. Math. 35 (1992) 293-299]. To obtain this result, we prove necessary and sufficient conditions for the existence of a partial Steiner triple system of odd order having a leave L such that E(L)=E(G) where G is any given graph.     

The spectrum for quasigroups with cyclic automorphisms and additional symmetries

We determine necessary and sufficient conditions for the existence of a quasigroup of order n having an automorphism consisting of a single cycle of length m and n−m fixed points, and having any combination of the additional properties of being idempotent, unipotent, commutative, semi-symmetric or totally symmetric. Quasigroups with such additional properties and symmetries are equivalent to various classes of triple systems.     

Orientable biembeddings of cyclic Steiner triple systems from current assignments on Möbius ladder graphs

We give a characterization of a current assignment on the bipartite Möbius ladder graph with 2n+1 rungs. Such an assignment yields an index one current graph with current group Z_12n+7 that generates an orientable face 2-colorable triangular embedding of the complete graph K_12n+7 or, equivalently, an orientable biembedding of two cyclic Steiner triple systems of order 12n+7. We use our characterization to construct Skolem sequences that give rise to such current assignments. These produce many nonisomorphic orientable biembeddings of cyclic Steiner triple systems of order 12n+7.     

Surface embeddings of Steiner triple systems

A Steiner triple system of order n (STS(n)) is said to be embeddable in an orientable surface if there is an orientable embedding of the complete graph K_n whose faces can be properly 2-colored (say, black and white) in such a way that all black faces are triangles and these are precisely the blocks of the STS(n). If, in addition, all white faces are triangular, then the collection of all white triangles forms another STS(n); the pair of such STS(n)s is then said to have an (orientable) bi-embedding. We study several questions related to embeddings and bi-embeddings of STSs. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 325–336, 1998     

Small Embeddings of Partial Steiner Triple Systems

It was proved in 2009 that any partial Steiner triple system of order u has an embedding of order v for each admissible . This result is best possible in the sense that, for each , there exists a partial Steiner triple system of order u that does not have an embedding of order v for any . Many partial Steiner triple systems do have embeddings of orders smaller than , but much less is known about when these embeddings exist. In this paper, we detail a method for constructing such embeddings. We use this method to show that each member of a wide class of partial Steiner triple systems has an embedding of order v for at least half (or nearly half) of the orders for which an embedding could exist. For some members of this class we are able to completely determine the set of all orders for which the member has an embedding.     

Cyclic bi‐embeddings of Steiner triple systems on 12s + 7 points

A cyclic face 2‐colourable triangulation of the complete graph K_n in an orientable surface exists for n ≡ 7 (mod 12). Such a triangulation corresponds to a cyclic bi‐embedding of a pair of Steiner triple systems of order n, the triples being defined by the faces in each of the two colour classes. We investigate in the general case the production of such bi‐embeddings from solutions to Heffter's first difference problem and appropriately labelled current graphs. For n = 19 and n = 31 we give a complete explanation for those pairs of Steiner triple systems which do not admit a cyclic bi‐embedding and we show how all non‐isomorphic solutions may be identified. For n = 43 we describe the structures of all possible current graphs and give a more detailed analysis in the case of the Heawood graph. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 92–110, 2002; DOI 10.1002/jcd.10001     

Nonorientable triangular embeddings of complete graphs with arbitrarily large looseness

The looseness of a triangular embedding of a complete graph in a closed surface is the minimum integer m such that for every assignment of m colors to the vertices of the embedding (such that all m colors are used) there is a face incident with vertices of three distinct colors. In this paper we show that for every p?3 there is a nonorientable triangular embedding of a complete graph with looseness at least p.     

Coloring Cubic Graphs by Point‐Intransitive Steiner Triple Systems

An ‐coloring of a cubic graph G is an edge coloring of G by points of a Steiner triple system such that the colors of any three edges meeting at a vertex form a block of . A Steiner triple system that colors every simple cubic graph is said to be universal. It is known that every nontrivial point‐transitive Steiner triple system that is neither projective nor affine is universal. In this article, we present the following results.

相似文献   

Embedding partial Steiner triple systems so that their automorphisms extend

It is shown that there is a function g on the natural numbers such that a partial Steiner triple system U on u points can be embedded in a Steiner triple system V on ν points, in such a way that all automorphisms of U can be extended to V, for every admissible ν satisfying ν > g(u). We find exponential upper and lower bounds for g. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Large monochromatic components in 3‐edge‐colored Steiner triple systems

It is known that in any r‐coloring of the edges of a complete r‐uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3‐coloring of the edges? Gyárfás proved that $\left(2n+3\right)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $\left(1?o\left(1\right)\right)n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest 3‐partite hole (ie, disjoint sets $X_1,X_2,X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1,X_2,X_3$) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the structure of the Steiner triple system and the coloring of its edges are restricted in a certain way. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.     

Cycle structure of autotopisms of quasigroups and latin squares

An autotopism of a Latin square is a triple (α, β, γ) of permutations such that the Latin square is mapped to itself by permuting its rows by α, columns by β, and symbols by γ. Let Atp(n) be the set of all autotopisms of Latin squares of order n. Whether a triple (α, β, γ) of permutations belongs to Atp(n) depends only on the cycle structures of α, β, and γ. We establish a number of necessary conditions for (α, β, γ) to be in Atp(n), and use them to determine Atp(n) for n?17. For general n, we determine if (α, α, α)∈Atp(n) (that is, if αis an automorphism of some quasigroup of order n), provided that either αhas at most three cycles other than fixed points or that the non‐fixed points of α are in cycles of the same length. © 2011 Wiley Periodicals, Inc. J Combin Designs     

A conjecture on small embeddings of partial Steiner triple systems

A well‐known, and unresolved, conjecture states that every partial Steiner triple system of order u can be embedded in a Steiner triple system of order υ for all υ ≡ 1 or 3, (mod 6), υ ≥ 2u + 1. However, some partial Steiner triple systems of order u can be embedded in Steiner triple systems of order υ <2u + 1. A more general conjecture that considers these small embeddings is presented and verified for some cases. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 313–321, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10017     

Doyen–Wilson theorem for nested Steiner triple systems

The obvious necessary conditions for the existence of a nested Steiner triple system of order v containing a nested subsystem of order w are v ≥ 3w + 4 and v ≡ w ≡ 1 (mod 6). We show that these conditions are also sufficient. © 2004 Wiley Periodicals, Inc.     

Biembeddings of Abelian groups

We prove that, with the single exception of the 2‐group C, the Cayley table of each Abelian group appears in a face 2‐colorable triangular embedding of a complete regular tripartite graph in an orientable surface. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 71–83, 2010     

1‐Rotational Steiner triple systems over arbitrary groups

Phelps and Rosa introduced the concept of 1‐rotational Steiner triple system, that is an STS(ν) admitting an automorphism consisting of a fixed point and a single cycle of length ν ? 1 [Discrete Math. 33 ( 12 ), 57–66]. They proved that such an STS(ν) exists if and only if ν ≡ 3 or 9 (mod 24). Here, we speak of a 1‐rotational STS(ν) in a more general sense. An STS(ν) is 1‐rotational over a group G when it admits G as an automorphism group, fixing one point and acting regularly on the other points. Thus the STS(ν)'s by Phelps and Rosa are 1‐rotational over the cyclic group. We denote by ??_1r, ??_1r, ??_1r, ??_1r, the spectrum of values of ν for which there exists a 1‐rotational STS(ν) over an abelian, a cyclic, a dicyclic, and an arbitrary group, respectively. In this paper, we determine ??_1r and find partial answers about ??_1r and ??_1r. The smallest 1‐rotational STSs have orders 9, 19, 25 and are unique up to isomorphism. In particular, the only 1‐rotational STS(25) is over SL₂(3), the special linear group of dimension 2 over Z₃. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 215–226, 2001