3,5-cycle decompositions

For all odd integers n and all non-negative integers r and s satisfying 3r + 5s = n(n -1)/2 it is shown that the edge set of the complete graph on n vertices can be partitioned into r 3-cycles and s 5-cycles. For all even integers n and all non-negative integers r and s satisfying 3r + 5s = n(n-2)/2 it is shown that the edge set of the complete graph on n vertices with a 1-factor removed can be partitioned into r 3-cycles and s 5-cycles. (C) 1998 John Wiley & Sons, Inc.

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n greater than or equal to 1, let G(n) denote the complete graph of order n, and for all even integers n greater than or equal to 2 let G,, denote the complete graph of order n with the edges of a 1-factor removed. It is shown that for all non-negative integers h and t and all positive integers n, G, can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G(n). (C) 2004 Wiley Periodicals, Inc.

On a generalization of the Oberwolfach problem

Let e(1),e(2),... e(n) be a sequence of nonnegative integers Such that the first non-zero term is not one. Let Sigma(i=1)(n) e(i) = (q - 1)/2, where q = p(n) and p is an odd prime. We prove that the complete graph on q vertices can be decomposed into e(1) C-pn-factors, e(2) C-pn (1)-factors,..., and e(n) C-p-factors. (C) 2004 Elsevier Inc. All rights reserved.

A scheme for efficient quantum computation wtih linear optics

Quantum computers promise to increase greatly the efficiency of solving problems such as factoring large integers, combinatorial optimization and quantum physics simulation. One of the greatest challenges now is to implement the basic quantum-computational elements in a physical system and to demonstrate that they can be reliably and scalably controlled. One of the earliest proposals for quantum computation is based on implementing a quantum bit with two optical modes containing one photon. The proposal is appealing because of the ease with which photon interference can be observed. Until now, it suffered from the requirement for non-linear couplings between optical modes containing few photons. Here we show that efficient quantum computation is possible using only beam splitters, phase shifters, single photon sources and photo-detectors. Our methods exploit feedback from photo-detectors and are robust against errors from photon loss and detector inefficiency. The basic elements are accessible to experimental investigation with current technology.

The intersection problem for star designs

We determine those triples (m, II, k) of integers for which there are two m-star designs on the same n-set having exactly k stars in common.

Critical sets for families of Latin squares

In this paper I give details of new constructions for critical sets in latin squares. These latin squares, of order n, are such that they can be partitioned into four subsquares each of which is based on the addition table of the integers module n/2, an isotopism of this or a conjugate.

Extended GCD and Hermite normal form algorithms via lattice basis reduction

Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x(1), ..., x(m) for the equation s = gcd (s(1), ..., s(m)) = x(1)s(1) + ... + x(m)s(m), where s1, ... , s(m) are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

(m,n)-cycle systems

We describe a method which, in certain circumstances, may be used to prove that the well-known necessary conditions for partitioning the edge set of the complete graph on an odd number of vertices (or the complete graph on an even number of vertices with a 1-factor removed) into cycles of lengths m(1),m(2),...,m(t) are sufficient in the case \{m(1), m(2), ..., m(t)}\=2. The method is used to settle the case where the cycle lengths are 4 and 5. (C) 1998 Elsevier Science B.V. All rights reserved.

Quasistationarity of continuous-time Markov chains with positive drift

We shall study continuous-time Markov chains on the nonnegative integers which are both irreducible and transient, and which exhibit discernible stationarity before drift to infinity sets in. We will show how this 'quasi' stationary behaviour can be modelled using a limiting conditional distribution: specifically, the limiting state probabilities conditional on not having left 0 for the last time. By way of a dual chain, obtained by killing the original process on last exit from 0, we invoke the theory of quasistationarity for absorbing Markov chains. We prove that the conditioned state probabilities of the original chain are equal to the state probabilities of its dual conditioned on non-absorption, thus allowing us to establish the simultaneous existence and then equivalence, of their limiting conditional distributions. Although a limiting conditional distribution for the dual chain is always a quasistationary distribution in the usual sense, a similar statement is not possible for the original chain.

Maximum packings of K-v-K-u with triples

We construct, for all positive integers u, and v with u less than or equal to v, a decomposition of K-v - K-u (the complete graph on v vertices with a. hole of size u) into the maximum possible number of edge disjoint triangles.

A family of perfect factorisations of complete bipartite graphs

A 1-factorisation of a graph is perfect if the union of any two of its 1-factors is a Hamiltonian cycle. Let n = p(2) for an odd prime p. We construct a family of (p-1)/2 non-isomorphic perfect 1-factorisations of K-n,K-n. Equivalently, we construct pan-Hamiltonian Latin squares of order n. A Latin square is pan-Hamiltoilian if the permutation defined by any row relative to any other row is a single Cycle. (C) 2002 Elsevier Science (USA).

Critical sets in direct products of back circulant Latin squares

To date very Few families of critical sets for latin squares are known. The only previously known method for constructing critical sets involves taking a critical set which is known to satisfy certain strong initial conditions and using a doubling construction. This construction can be applied to the known critical sets in back circulant latin squares of even order. However, the doubling construction cannot be applied to critical sets in back circulant latin squares of odd order. In this paper a family of critical sets is identified for latin squares which are the product of the latin square of order 2 with a back circulant latin square of odd order. The proof that each element of the critical set is an essential part of the reconstruction process relies on the proof of the existence of a large number of latin interchanges.

A low-temperature insulating phase at v=1.5 for 2D holes in high-mobility SiSi1-xGex heterostructures with Landau level degeneracy

Magneto-transport measurements of the 2D hole system (2DHS) in p-type Si-Si1-xGex heterostructures identify the integer quantum Hall effect (IQHE) at dominantly odd-integer filling factors v and two low-temperature insulating phases (IPs) at v = 1.5 and v less than or similar to 0.5, with re-entrance to the quantum Hall effect at v = 1. The temperature dependence, current-voltage characteristics, and tilted field and illumination responses of the IP at v = 1.5 indicate that the important physics is associated with an energy degeneracy of adjacent Landau levels of opposite spin, which provides a basis for consideration of an intrinsic, many-body origin.