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.     

A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs

We prove a theorem that for an integer s?0, if 12s+7 is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of K_n, where n=(12s+7)(6s+7), is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least 2^αn?+o(n?), ?>1, nonisomorphic nonorientable triangular embeddings of K_n for n=6t+1, . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given.     

Biembedding Abelian groups with mates having transversals

A certain recursive construction for biembeddings of Latin squares has played a substantial role in generating large numbers of nonisomorphic triangular embeddings of complete graphs. In this article, we prove that, except for the groups and C ₄ , each Latin square formed from the Cayley table of an Abelian group appears in a biembedding in which the second Latin square has a transversal. Such biembeddings may then be freely used as ingredients in the recursive construction. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 20:81‐88, 2012     

Dihedral Biembeddings and Triangulations by Complete and Complete Tripartite Graphs

We construct biembeddings of some Latin squares which are Cayley tables of dihedral groups. These facilitate the construction of ${n^{an^2}}$ nonisomorphic face 2-colourable triangular embeddings of the complete tripartite graph K _n,n,n and the complete graph K _n for linear classes of values of n and suitable constants a. Previously the best known lower bounds for the number of such embeddings that are applicable to linear classes of values of n were of the form ${2^{an^2}.}$ We remark that trivial upper bounds are ${n^{n^2/3}}$ in the case of complete graphs K _n and ${n^{2n^2}}$ in the case of complete tripartite graphs K _n,n,n .     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

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.     

Cyclic Biembeddings of Twofold Triple Systems

We construct face two-colourable triangulations of the graph 2K _n in an orientable surface; equivalently biembeddings of two twofold triple systems of order n, for all n ≡ 4 (mod 12). The biembeddings have a cyclic automorphism and the construction employs index 1 current graphs.     

On a ramification bound of torsion semi-stable representations over a local field

Let p be a rational prime, k be a perfect field of characteristic p, W=W(k) be the ring of Witt vectors, K be a finite totally ramified extension of Frac(W) of degree e and r be a non-negative integer satisfying r<p−1. In this paper, we prove the upper numbering ramification group for j>u(K,r,n) acts trivially on the pn-torsion semi-stable GK-representations with Hodge-Tate weights in {0,…,r}, where u(K,0,n)=0, u(K,1,n)=1+e(n+1/(p−1)) and u(K,r,n)=1−p−n+e(n+r/(p−1)) for 1<r<p−1.     

Bounds on the number of autotopisms and subsquares of a Latin square

A subsquare of a Latin square L is a submatrix that is also a Latin square. An autotopism of L is a triplet of permutations (α, β, γ) such that L is unchanged after the rows are permuted by α, the columns are permuted by β and the symbols are permuted by γ. Let n!(n?1)!R _n be the number of n×n Latin squares. We show that an n×n Latin square has at most n ^{O(log k)} subsquares of order k and admits at most n ^{O(log n)} autotopisms. This enables us to show that {ie11-1} divides R _n for all primes p. We also extend a theorem by McKay and Wanless that gave a factorial divisor of R _n , and give a new proof that R _p ≠1 (mod p) for prime p.     

On geometric SDPS-sets of elliptic dual polar spaces

Let n∈N?{0,1} and let K and K^′ be fields such that K^′ is a quadratic Galois extension of K. Let Q⁻(2n+1,K) be a nonsingular quadric of Witt index n in PG(2n+1,K) whose associated quadratic form defines a nonsingular quadric Q⁺(2n+1,K^′) of Witt index n+1 in PG(2n+1,K^′). For even n, we define a class of SDPS-sets of the dual polar space DQ⁻(2n+1,K) associated to Q⁻(2n+1,K), and call its members geometric SDPS-sets. We show that geometric SDPS-sets of DQ⁻(2n+1,K) are unique up to isomorphism and that they all arise from the spin embedding of DQ⁻(2n+1,K). We will use geometric SDPS-sets to describe the structure of the natural embedding of DQ⁻(2n+1,K) into one of the half-spin geometries for Q⁺(2n+1,K^′).     

Regular orientable imbeddings of complete graphs

This paper classifies the regular imbeddings of the complete graphs K_n in orientable surfaces. Biggs showed that these exist if and only if n is a prime power p^e, his examples being Cayley maps based on the finite field F = GF(n). We show that these are the only examples, and that there are $\text{φ(n ? 1)}\text{e}$ isomorphism classes of such maps (where φ is Euler's function), each corresponding to a conjugacy class of primitive elements of F, or equivalently to an irreducible factor of the cyclotomic polynomial Φ_{n ? 1}(z) over GF(p). We show that these maps are all equivalent under Wilson's map-operations H_i, and we determined for which n they are reflexible or self-dual.     

Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor

In this paper, we prove that cyclic hamiltonian cycle systems of the complete graph minus a 1-factor, K_n-I, exist if and only if and n≠2p^α with p an odd prime and α?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     

K 4-free graphs without large induced triangle-free subgraphs

Let f _3,4(n), for a natural number n, be the largest integer m such that every K ₄-free graph of order n contains an induced triangle-free subgraph of order m. We prove that for every suffciently large n, f _3,4(n)≤n ^1/2(lnn)¹²⁰. By known results, this bound is tight up to a polylogarithmic factor.     

Regularity of patterns in the factorization of n!

Consider the multiplicities ep₁(n),ep₂(n),…,epk(n) in which the primes p₁,p₂,…,pk appear in the factorization of n!. We show that these multiplicities are jointly uniformly distributed modulo (m₁,m₂,…,mk) for any fixed integers m₁,m₂,…,mk, thus improving a result of Luca and St?nic? [F. Luca, P. St?nic?, On the prime power factorization of n!, J. Number Theory 102 (2003) 298-305]. To prove the theorem, we obtain a result regarding the joint distribution of several completely q-additive functions, which seems to be of independent interest.     

K 1,p k-factorization of complete bipartite graphs

Abstract. In this paper, it is shown that a sufficient condition for the existence of a     

New families of atomic Latin squares and perfect 1-factorisations

A perfect 1-factorisation of a graph G is a decomposition of G into edge disjoint 1-factors such that the union of any two of the factors is a Hamiltonian cycle. Let p?11 be prime. We demonstrate the existence of two non-isomorphic perfect 1-factorisations of K_p+1 (one of which is well known) and five non-isomorphic perfect 1-factorisations of K_p,p. If 2 is a primitive root modulo p, then we show the existence of 11 non-isomorphic perfect 1-factorisations of K_p,p and 5 main classes of atomic Latin squares of order p. Only three of these main classes were previously known. One of the two new main classes has a trivial autotopy group.     

On a Normal Integral Basis Problem over Cyclotomic Zp-extensions, II

Let p be an odd prime number, K an imaginary abelian field with ζ_p∈K^×, and K_∞/K the cyclotomic Z_p-extension with its nth layer K_n. In the previous paper, we showed that for any n and any unramified cyclic extension L/K_n of degree p, LK_n+1/K_n+1 does have a normal integral basis (NIB) even if L/K_n has no NIB, under the assumption that p does not divide the class number of the maximal real subfield K⁺ (and some additional assumptions on K). In this paper, we show that similar but more delicate phenomena occur for a certain class of tamely ramified extensions of degree p.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

On a conjecture of E. Rapaport Strasser about knot-like groups and its pro-p version

A group G is knot-like if it is finitely presented of deficiency 1 and has abelianization G/G^′?Z. We prove the conjecture of E. Rapaport Strasser that if a knot-like group G has a finitely generated commutator subgroup G^′ then G^′ should be free in the special case when the commutator G^′ is residually finite. It is a corollary of a much more general result : if G is a discrete group of geometric dimension n with a finite K(G,1)-complex Y of dimension n, Y has Euler characteristics 0, N is a normal residually finite subgroup of G, N is of homological type FP_n-1 and G/N?Z then N is of homological type FP_n and hence G/N has finite virtual cohomological dimension vcd(G/N)=cd(G)-cd(N). In particular either N has finite index in G or cd(N)?cd(G)-1.Furthermore we show a pro-p version of the above result with the weaker assumption that G/N is a pro-p group of finite rank. Consequently a pro-p version of Rapaport's conjecture holds.