Latin Squares with Restricted Transversals

The original article to which this erratum refers was correctly published online on 1 December 2011. Due to an error at the publisher, it was then published in Journal of Combinatorial Designs 20: 124–141, 2012 without the required shading in several examples. To correct this, the article is here reprinted in full. The publisher regrets this error. We prove that for all odd there exists a latin square of order 3m that contains an latin subrectangle consisting of entries not in any transversal. We prove that for all even there exists a latin square of order n in which there is at least one transversal, but all transversals coincide on a single entry. A corollary is a new proof of the existence of a latin square without an orthogonal mate, for all odd orders . Finally, we report on an extensive computational study of transversal‐free entries and sets of disjoint transversals in the latin squares of order . In particular, we count the number of species of each order that possess an orthogonal mate. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 344–361, 2012     

Hadamard Matrices Modulo 5

In this paper, we introduce modular symmetric designs and use them to study the existence of Hadamard matrices modulo 5. We prove that there exist 5‐modular Hadamard matrices of order n if and only if or . In particular, this solves the 5‐modular version of the Hadamard conjecture.     

Transversality on locally pseudocompact groups

Two non-discrete Hausdorff group topologies \tau and \delta on a group G are called transversal if the least upper bound \tau \vee \delta of \tau and \delta is the discrete topology. In this paper, we discuss the existence of transversal group topologies on locally pseudocompact, locally precompact, or locally compact groups. We prove that each locally pseudocompact, connected topological group satisfies central subgroup paradigm, which gives an affrmative answer to a problem posed by Dikranjan, Tkachenko, and Yaschenko [Topology Appl., 2006, 153:3338-3354]. For a compact normal subgroup K of a locally compact totally disconnected group G, if G admits a transversal group topology, then G/K admits a transversal group topology, which gives a partial answer again to a problem posed by Dikranjan, Tkachenko, and Yaschenko in 2006. Moreover, we characterize some classes of locally compact groups that admit transversal group topologies.     

Quasilinear Schrödinger equations with unbounded or decaying potentials

We study the existence of nonnegative and nonzero solutions for the following class of quasilinear Schrödinger equations: where V and Q are potentials that can be singular at the origin, unbounded or vanishing at infinity. In order to prove our existence result we used minimax techniques in a suitable weighted Orlicz space together with regularity arguments and we need to obtain a symmetric criticality type result.     

Transversals in Latin Arrays with Many Distinct Symbols

An array is row‐Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row‐Latin. A transversal in an array is a selection of n different symbols from different rows and different columns. We prove that every Latin array containing at least distinct symbols has a transversal. Also, every row‐Latin array containing at least distinct symbols has a transversal. Finally, we show by computation that every Latin array of order 7 has a transversal, and we describe all smaller Latin arrays that have no transversal.     

No hexavalent half-arc-transitive graphs of order twice a prime square exist

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set and edge set, but not arc set. Let p be a prime. Wang and Feng (Discrete Math. 310 (2010) 1721–1724) proved that there exists no tetravalent half-arc-transitive graphs of order \(2p^2\). In this paper, we extend this result to prove that no hexavalent half-arc-transitive graphs of order \(2p^2\) exist.     

Multidimensional Permanents and an Upper Bound on the Number of Transversals in Latin Squares

The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. A nonnegative matrix whose every 1‐dimensional plane sums to 1 is called polystochastic. A latin square of order n is an array of n symbols in which each symbol occurs exactly once in each row and each column. A transversal of such a square is a set of n entries such that no two entries share the same row, column, or symbol. Let T(n) be the maximum number of transversals over all latin squares of order n. Here, we prove that over the set of multidimensional polystochastic matrices of order n the permanent has a local extremum at the uniform matrix for whose every entry is equal to . Also, we obtain an asymptotic value of the maximal permanent for a certain set of nonnegative multidimensional matrices. In particular, we get that the maximal permanent of polystochastic matrices is asymptotically equal to the permanent of the uniform matrix, whence as a corollary we have an upper bound on the number of transversals in latin squares      

The width of quadrangulations of the projective plane

We show that every 4‐chromatic graph on n vertices, with no two vertex‐disjoint odd cycles, has an odd cycle of length at most . Let G be a nonbipartite quadrangulation of the projective plane on n vertices. Our result immediately implies that G has edge‐width at most , which is sharp for infinitely many values of n. We also show that G has face‐width (equivalently, contains an odd cycle transversal of cardinality) at most , which is a constant away from the optimal; we prove a lower bound of . Finally, we show that G has an odd cycle transversal of size at most inducing a single edge, where Δ is the maximum degree. This last result partially answers a question of Nakamoto and Ozeki.     

Arc‐Disjoint Directed and Undirected Cycles in Digraphs

The dicycle transversal number of a digraph D is the minimum size of a dicycle transversal of D, that is a set of vertices of D, whose removal from D makes it acyclic. An arc a of a digraph D with at least one cycle is a transversal arc if a is in every directed cycle of D (making acyclic). In [3] and [4], we completely characterized the complexity of following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C in its underlying undirected graph such that . It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where ). In the remaining case (allowing arbitrarily many transversal vertices) the problem is NP‐complete. In this article, we classify the complexity of the arc‐analog of this problem, where we ask for a dicycle B and a cycle C that are arc‐disjoint, but not necessarily vertex‐disjoint. We prove that the problem is polynomially solvable for strong digraphs and for digraphs with a constantly bounded number of transversal arcs (but possibly an unbounded number of transversal vertices). In the remaining case (allowing arbitrarily many transversal arcs) the problem is NP‐complete.     

Models of : when two elements are necessarily order automorphic

We are interested in the question of how much the order of a non‐standard model of can determine the model. In particular, for a model M, we want to characterize the complete types of non‐standard elements such that the linear orders and are necessarily isomorphic. It is proved that this set includes the complete types such that if the pair realizes it (in M) then there is an element c such that for all standard n, , , , and . We prove that this is optimal, because if holds, then there is M of cardinality ?₁ for which we get equality. We also deal with how much the order in a model of may determine the addition.     

On the decomposition of λK into regular tournaments of order 5

An RTD[5,λ; v] is a decomposition of the complete symmetric directed multigraph, denoted by λK, into regular tournaments of order 5. In this article we show that an RTD[5,λ; v] exists if and only if (v?1)λ ≡ 0 (mod 2) and v(v?1)λ ≡ 0 (mod 10), except for the impossible case (v,λ) = (15,1). Furthermore, we show that for each v ≡ 1,5 (mod 20), v ≠ 5, there exists a B[5,2; v] which is not RT₅-directable. © 1994 John Wiley & Sons, Inc.     

Normalized difference set tiling conjecture

A difference set tiling in a group G is a collection of its difference sets that partition . It can exist in an abelian as well as in a nonabelian group. A tiling is normalized if a product of elements in each difference set equals 1. All known cases in abelian groups are normalized. Ćustić, Krčadinac, and Zhou made a conjecture that this is necessary. We will call it a normalized tiling conjecture (NTC). Using character theory, we prove that NTC is true for where v is odd. Also, if difference set has a multiplier, we prove that NTC is also true.     

The Classification of Symmetric Transversal Designs <Emphasis Type="Italic">STD</Emphasis><Subscript>4</Subscript>[12; 3]’s

In this article we prove that there is only one symmetric transversal design STD₄[12;3] up to isomorphism. We also show that the order of the full automorphism group of STD₄[12; 3] is 2⁵· 3³ and Aut STD₄[12;3] has a regular subgroup as a permutation group on the point set. We used a computer for our research.Communicated by: C.J. Colbourn     

Normal cirulant graphs with noncyclic regular subroups

We prove that any circulant graph of order n with connection set S such that n and the order of ?(S), the subgroup of ? that fixes S set‐wise, are relatively prime, is also a Cayley graph on some noncyclic group, and shows that the converse does not hold in general. In the special case of normal circulants whose order is not divisible by 4, we classify all such graphs that are also Cayley graphs of a noncyclic group, and show that the noncyclic group must be metacyclic, generated by two cyclic groups whose orders are relatively prime. We construct an infinite family of normal circulants whose order is divisible by 4 that are also normal Cayley graphs on dihedral and noncyclic abelian groups. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the Smith normal form of a skew‐symmetric d‐optimal design of order

We show that the Smith normal form of a skew‐symmetric D ‐optimal design of order is determined by its order. Furthermore, we show that the Smith normal form of such a design can be written explicitly in terms of the order , thereby proving a recent conjecture of Armario. We apply our result to show that certain D ‐optimal designs of order are not equivalent to any skew‐symmetric D ‐optimal design. We also provide a correction to a result in the literature on the Smith normal form of D ‐optimal designs.     

First and second order error estimates for the Upwind Source at Interface method

The Upwind Source at Interface (U.S.I.) method for hyperbolic conservation laws with source term introduced by Perthame and Simeoni is essentially first order accurate. Under appropriate hypotheses of consistency on the finite volume discretization of the source term, we prove -error estimates, , in the case of a uniform spatial mesh, for which an optimal result can be obtained. We thus conclude that the same convergence rates hold as for the corresponding homogeneous problem. To improve the numerical accuracy, we develop two different approaches of dealing with the source term and we discuss the question of deriving second order error estimates. Numerical evidence shows that those techniques produce high resolution schemes compatible with the U.S.I. method.

     

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     

The order of a meridian of a knotted Klein bottle

We consider the order of a meridian (of the group) of a Klein bottle smoothly embedded in the -sphere . The order of a meridian of a Klein bottle in is a non-negative even integer. Conversely, we prove that, for every non-negative even integer , there exists a Klein bottle in whose meridian has order .

     

Pentavalent symmetric graphs of order 16p

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, a complete classification of connected pentavalent symmetric graphs of order 16p is given for each prime p. It follows from this result that a connected pentavalent symmetric graph of order 16p exists if and only if p = 2 or 31, and that up to isomorphism, there are three such graphs.