Completing partial latin squares

It is shown that if a partial latin square of order n with fewer than n entries has all its entries in no more than $\text{(n + 3)}\text{2}$ rows, then it can be completed. This extends previous results of both Lindner and Wells, but lately Wells has improved this to $\text{(n + 5)}\text{2}$. We show that the number $\text{(n + 3)}\text{2}$ is the best obtainable by the method of completing one row at a time without regard for completing future rows.     

Symmetric latin square and complete graph analogues of the evans conjecture

With the proof of the Evans conjecture, it was established that any partial latin square of side n with a most n ? 1 nonempty cells can be completed to a latin square of side n. In this article we prove an analogous result for symmetric latin squares: a partial symmetric latin square of side n with an admissible diagonal and at most n ? 1 nonempty cells can be completed to a symmetric latin square of side n. We also characterize those partial symmetric latin squares of side n with exactly n or n + 1 nonempty cells which cannot be completed. From these results we deduce theorems about completing edge-colorings of complete graphs K_2m and K_{2m ? 1} with 2m ? 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

On a generalization of the Evans Conjecture

The Evans Conjecture states that a partial Latin square of order n with at most n-1 entries can be completed. In this paper we generalize the Evans Conjecture by showing that a partial r-multi Latin square of order n with at most n-1 entries can be completed. Using this generalization, we confirm a case of a conjecture of Häggkvist.     

Row complete squares and a problem of A. Kotzig concerning P-quasigroups and eulerian circuits

An n × n square L on n symbols is called row (column) complete if every ordered pair of the symbols of L occurs just once as an adjacent pair of elements in some row (column) of L. It is called row (column) latin if each symbol occurs exactly once in each row (column) of the square. A square which is both row latin and column latin is called a latin square. All known examples of row complete latin squares can be made column complete as well by suitable reordering of their rows and in the present paper we provide a sufficient condition that a given row complete latin square should have this property.Using row complete and column latin squares as a tool we follow this by showing how to construct code words on n symbols of the maximum possible length $\text{l =}\text{1}\text{2}\text{n(n ? 1) + 1}$ with the two properties that (i) no unordered pair of consecutive symbols is repeated more than once and (ii) no unordered pair of nearly consecutive symbols is repeated more than once. (Two symbols are said to be nearly consecutive if they are separated by a single symbol.) We prove that such code words exist whenever n = 4r + 3 with r ? 1 mod 6 and r ? 2 mod 5. We show that the existence of such a code word for a given value of n guarantees the existence of an Eulerian circuit in the complete undirected n-graph which corresponds to a P-quasigroup, thus answering a question raised by A. Kotzig in the affirmative. (Kotzig has defined a P-groupoid as a groupoid (G, ·) having the following three properties: (i) a . a = a for all a?G; (ii) a ≠ b implies a ≠ a . b and b ≠ a. b for all a, b?G; and (iii) a . b = c implies c. b = a for all a, b, c?G. Every decomposition of the complete undirected n-graph into disjoint closed circuits defines such a P-groupoid, as is easily seen by defining a . b = c if and only if a, b, c are consecutive edges of one such closed circuit. A P-groupoid whose multiplication table is a latin square is called a P-quasigroup.)     

Latin squares with restricted transversals

We prove that for all odd m ≥ 3 there exists a latin square of order 3 m that contains an ( m ? 1 ) × m latin subrectangle consisting of entries not in any transversal. We prove that for all even n ≥ 10 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 n ≥ 11 . Finally, we report on an extensive computational study of transversal‐free entries and sets of disjoint transversals in the latin squares of order n ? 9 . In particular, we count the number of species of each order that possess an orthogonal mate. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:124‐141, 2012     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

Bachelor latin squares with large indivisible plexes

In a latin square of order n , a k ‐plex is a selection of kn entries in which each row, column, and symbol occurs k times. A 1 ‐plex is also called a transversal. A k ‐plex is indivisible if it contains no c ‐plex for 0 < c < k . We prove that, for all n ≥ 4 , there exists a latin square of order n that can be partitioned into an indivisible ? n / 2 ?‐plex and a disjoint indivisible ? n / 2 ?‐plex. For all n ≥ 3 , we prove that there exists a latin square of order n with two disjoint indivisible ? n / 2 ?‐plexes. We also give a short new proof that, for all odd n ≥ 5 , there exists a latin square of order n with at least one entry not in any transversal. Such latin squares have no orthogonal mate. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:304‐312, 2011     

An inequality for pseudo-subplanes of sets of orthogonal latin squares

Let L₁, L₂,…, L_t be a given set of t mutually orthogonal order-n latin squares defined on a symbol set S, |S| = n. The squares are equivalent to a (t + 2)-netN of order n which has n² points corresponding to the n² cells of the squares. A line of the net N defined by the latin square L_i comprises the n points of the net which are specified by a set of n cells of L_i all of which contain the same symbol x of S. If we pick out a particular r × r block B of cells, a line which contains points corresponding to r of the cells of B will be called an r-cell line. If there exist r(r ? 1) such lines among the tn lines of N, we shall say that they form a pseudo-subplane of order r-the “pseudo” means that these lines need not belong to only r ? 1 of the latin squares. The purpose of the present note is to prove that the hypothesis that such a pseudo-plane exists in N implies that $\text{r}{}^3\text{? (t + 2)r}{}^2\text{+ r + nt ?}{}^1\text{0}$.     

Remark on a theorem of Lindström

Let Ω denote the set of all n by n doubly stochastic matrices and let m be a positive integer. Then the set $\text{Ω}{}_{\mathrm{m}}\text{= {A ? Ω : 0 ? a}{}_{\mathrm{ij}}\text{?}\text{1}\text{m}\text{, 1 ? i, j ≤ n}}$ is the convex hull of the matrices in $\text{Ω}{}_{\mathrm{m}}$ having exactly m entries equal to $\text{1}\text{m}$ in each row and column and the other entries equal to zero.     

Convex sets of some doubly stochastic matrices

Let Ω denote the set of all n by n doubly stochastic matrices. Let t be a real number such that $\text{1}\text{t}\text{?}\text{1}\text{n}$ and let m be a real number such that $\text{1}\text{m}\text{? 1 ?}\text{1}\text{t}$. The set $\text{Ω}{}_{\mathrm{s}}\text{= {A ? Ω :}\text{1}\text{m}\text{? a}{}_{\mathrm{ij}}\text{?}\text{1}\text{t}\text{, 1 ? i, j ? n}}$ is the convex hull of the matrices in $\text{Ω}{}_{\mathrm{s}}$ having as many largest entries, namely, $\text{1}\text{t}$, as possible in each row and column while filling out the remaining entries with the value $\text{1}\text{m}$ and if necessary at most one entry in each row and column which has a value between $\text{1}\text{m}$ and $\text{1}\text{t}$.     

Covering tori with squares

We find that an n × n toroidal checkerboard can be covered with $\text{?}\text{n}\text{k}\text{?}\text{n}\text{k}\text{??}$k × k squares, and no fewer. To prove this result we also need to prove that the unit Euclidean torus can be covered with ?α^?1?α^?1?? squares of side α, and no fewer.     

On the asymptotic normality and independence of the sample partial autocorrelations for an autoregressive process

For a stationary autoregressive model of order s, the partial autocorrelation coefficients of order $\text{j}$, $\text{j}$=0,1,2,…,s?1, are defined; the partial autocorrelation coefficient of order zero being the same as the autocorrelation coefficient of order one. Denoting these s parameters by ?₁,π₁,…,π_s?1, it is shown that their sample images, namely r₁,$\text{P}$₁,…,$\text{P}$_s?1, are asymptotically independently normally distributed with means equal to the corresponding population values and asymptotic variances given by

$\text{var(r}{}_1\text{)=}\text{(1 ? ?}\text{2}\text{1}\text{)(1 ? π}\text{2}\text{1}\text{?(1 ? π}\text{2}\text{s ?1}\text{)}\text{n}\text{,}$

$\text{var(}\text{P}{}_{\mathrm{<mtext>j</mtext>}}\text{)=}\text{(1 ? π}\text{2}\text{j}\text{(1 ? π}\text{2}\text{j}\text{+1}\text{)?(1 ? π}\text{2}\text{s ?1}\text{)}\text{n}$

,

$\text{j}\text{=1,2,…,s?1,}$

where n is the size of the sample from the autoregressive process of order s. The partial correlogram of the model and application of the result are discussed.     

Some advances in the no-three-in-line problem

It is shown that for any n there exist subsets of an n × n square array containing n points, of which no three lie in a line, and that for sufficiently large n there exist such subsets containing ($\text{3}\text{2}\text{? ?)n}$ points.     

Nonnegative factorization of completely positive matrices

Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with $\text{m?}\text{1}\text{2}\text{k(k+1)?N}$, where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is $\text{(k+1)}{}^2\text{4}$ (k odd),$\text{k(k+2)}\text{4}$ (k even).     

Common solutions to the Lyapunov equations

Let A be an n×n matrix with complex entries. A necessary and sufficient condition is established for the existence of a Hermitian solution H to the equations

$\text{AH+HA}{}^1\text{=HA+A}{}^1\text{H=I}$

.     

An infinite class of generalized room squares

A generalized Room square $\text{G}$ of order n and degree k is an ${}^{\mathrm{n?1}}{}^{\mathrm{k?1}}\text{×}{}^{\mathrm{n?1}}{}^{\mathrm{k?1}}$ array, each cell of which is either empty or contains an unordered k-tuple of a set S, |S| = n, such that each row and each column of the array contains each element of S exactly once and $\text{G}$ contains each unordered k-tuple of S exactly once. Using a class of Steiner systems and a generalized Room square of order 18 and degree 3 constructed by ad hoc methods, an infinite class of degree 3 squares is constructed.     

Completion of partial matrices to contractions

An n-by-m partially specified complex matrix is called a partial contraction if every rectangular submatrix consisting entirely of specified entries is itself a contraction. Necessary and sufficient condition are given for the pattern of specified entries such that any n-by-m partial contraction with this pattern may be completed to a full n-by-m contraction.     

Monogamous latin squares

We show for all n∉{1,2,4} that there exists a latin square of order n that contains two entries γ₁ and γ₂ such that there are some transversals through γ₁ but they all include γ₂ as well. We use this result to show that if n>6 and n is not of the form 2p for a prime p?11 then there exists a latin square of order n that possesses an orthogonal mate but is not in any triple of MOLS. Such examples provide pairs of 2-maxMOLS.