Breadth-first search and the Andrews-Curtis conjecture

Andrews and Curtis conjectured in 1965 that every balanced presentation of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. Recent computational work by Miasnikov and Myasnikov on this problem has been based on genetic algorithms. We show that a computational attack based on a breadth-first search of the tree of equivalent presentations is also viable, and seems to outperform that based on genetic algorithms. It allows us to extract shorter proofs (in some cases, provably shortest) and to consider the length thirteen case for two generators. We prove that, up to equivalence, there is a unique minimum potential counterexample.

The Fa,b,c conjecture, I

In 1977 a five-part conjecture was made about a family of groups related to trivalent graphs and one part of the conjecture was proved. The conjecture completely determines all finite members of the family. Here we prove another part of the conjecture and foreshadow a paper which completes the proof of the other three parts.

The Fa,b,c conjecture is true, II

In 1977 a five-part conjecture was made about a family of groups related to trivalent graphs and subsequently two parts of the conjecture were proved. The conjecture completely determines all finite members of the family. Here we complete the proof of the conjecture by giving proofs for the remaining three parts. (c) 2006 Elsevier Inc. All rights reserved.

Irreducible cyclic presentations of the trivial group

We produce families of irreducible cyclic presentations of the trivial group. These families comprehensively answer questions about such presentations asked by Dunwoody and by Edjvet, Hammond, and Thomas. Our theorems are purely theoretical, but their derivation is based on practical computations. We explain how we chose the computations and how we deduced the theorems.

A refined solution to Earth's hidden niobium: implications for evolution of continental crust and mode of core formation

New high-precision niobium (Nb) and tantalum (Ta) concentration data are presented for early Archaean metabasalts, metabasaltic komatiites and their erosion products (mafic metapelites) from SW Greenland and the Acasta gneiss complex, Canada. Individual datasets consistently show sub-chondritic Nb/Ta ratios averaging 15.1+/-11.6. This finding is discussed with regard to two competing models for the solution of the Nb-deficit that characterises the accessible Earth. Firstly, we test whether Nb could have sequestered into the core due to its slightly siderophile (or chalcophile) character under very reducing conditions, as recently proposed from experimental evidence. We demonstrate that troilite inclusions of the Canyon Diablo iron meteorite have Nb and V concentrations in excess of typical chondrites but that the metal phase of the Grant, Toluca and Canyon Diablo iron meteorites do not have significant concentrations of these lithophile elements. We find that if the entire accessible Earth Nb-deficit were explained by Nb in the core, only ca. 17% of the mantle could be depleted and that by 3.7 Ga, continental crust would have already achieved ca. 50% of its present mass. Nb/Ta systematics of late Archaean metabasalts compiled from the literature would further require that by 2.5 Ga, 90% of the present mass of continental crust was already in existence. As an alternative to this explanation, we propose that the average Nb/Ta ratio (15.1+/-11.6) of Earth's oldest mafic rocks is a valid approximation for bulk silicate Earth. This would require that ca. 13% of the terrestrial Nb resided in the Ta-free core. Since the partitioning of Nb between silicate and metal melts depends largely on oxygen fugacity and pressure, this finding could mean that metal/silicate segregation did not occur at the base of a deep magma ocean or that the early mantle was slightly less reducing than generally assumed. A bulk silicate Earth Nb/Ta ratio of 15.1 allows for depletion of up to 40% of the total mantle. This could indicate that in addition to the upper mantle, a portion of the lower mantle is depleted also, or if only the upper mantle were depleted, an additional hidden high Nb/Ta reservoir must exist. Comparison of Nb/Ta systematics between early and late Archaean metabasalts supports the latter idea and indicates deeply subducted high Nb/Ta eclogite slabs could reside in the mantle transition zone or the lower mantle. Accumulation of such slabs appears to have commenced between 2.5 and 2.0 Ga. Regardless of these complexities of terrestrial Nb/Ta systematics, it is shown that the depleted mantle Nb/Th ratio is a very robust proxy for the amount of extracted continental crust, because the temporal evolution of this ratio is dominated by Th-loss to the continents and not Nb-retention in the mantle. We present a new parameterisation of the continental crust volume versus age curve that specifically explores the possibility of lithophile element loss to the core and storage of eclogite slabs in the transition zone. (C) 2003 Elsevier Science B.V. All rights reserved.

The source of the Great Dyke, Zimbabwe, and its tectonic significance: Evidence from Re-Os isotopes

Re-Os data for chromite separates from 10 massive chromitite seams sampled along the 550-km length of the 2.58-Ga Great Dyke layered igneous complex, Zimbabwe, record initial 187Os/188Os ratios in the relatively narrow range between 0.1106 and 0.1126. This range of initial 187Os/188Os values is only slightly higher than the value for the coeval primitive upper mantle (0.1107) as modeled from the Re-Os evolution of chondrites and data of modern mantle melts and mantle derived xenoliths. Analyses of Archean granitoid and gneiss samples from the Zimbabwe Craton show extremely low Os concentrations (3-9 ppt) with surprisingly unradiogenic present-day 187Os/188Os signatures between 0.167 and 0.297. Only one sample yields an elevated 187Os/188Os ratio of 1.008. Using these data, the range of crustal contamination of the Great Dyke magma would be minimally 0%-33% if the magma source was the primitive upper mantle, whereas the range estimated from Nd and Pb isotope systematics is 5%-25%. If it is assumed that the primary Great Dyke magma derived from an enriched deep mantle reservoir (via a plume), a better agreement can be obtained. A significant contribution from a long-lived subcontinental lithospheric mantle (SCLM) reservoir with subchondritic Re/Os to the Great Dyke melts cannot be reconciled with the Os isotope results at all. However, Os isotope data on pre-Great Dyke ultramafic complexes of the Zimbabwe Craton and thermal modeling show that such an SCLM existed below the Zimbabwe Craton at the time of the Great Dyke intrusion. It is therefore concluded that large melt volumes such as that giving rise to the Great Dyke were able to pass lithospheric mantle keels without significant contamination in the late Archean. Because the ultramafic-mafic melts forming the Great Dyke must have originated below the SCLM (which extends to at least a 200-km depth ), the absence of an SCLM signature precludes a subduction-related magma-generation process.

Testing integrability with a single bit of quantum information

We show that deterministic quantum computing with a single bit can determine whether the classical limit of a quantum system is chaotic or integrable using O(N) physical resources, where N is the dimension of the Hilbert space of the system under study. This is a square-root improvement over all known classical procedures. Our study relies strictly on the random matrix conjecture. We also present numerical results for the nonlinear kicked top.

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.

A note on execution costs for stock index futures: Information versus liquidity effects

This paper examines execution costs and the impact of trade size for stock index futures using price-volume transaction data from the London International Financial Futures and Options Exchange. Consistent with Subrahmanyam [Rev. Financ. Stud. 4 (1991) 11] we find that effective half spreads in the stock index futures market are small compared to stock markets, and that trades in stock index futures have only a small permanent price impact. This result is important as it helps to better understand the success of equity index products such as index futures and Exchange Traded Funds. We also find that there is no asymmetry in the post-trade price reaction between purchases and sales for stock index futures across various trade sizes. This result is consistent with the conjecture in Chan and Lakonishok [J. Financ. Econ. 33 (1993) 173] that the asymmetry surrounding block trades in stock markets is due to the high cost of short selling and the general reluctance of traders to short sell on stock markets. (C) 2004 Elsevier B.V. All rights reserved.

Quantum entanglement and fixed-point bifurcations

How does the classical phase-space structure for a composite system relate to the entanglement characteristics of the corresponding quantum system? We demonstrate how the entanglement in nonlinear bipartite systems can be associated with a fixed-point bifurcation in the classical dynamics. Using the example of coupled giant spins we show that when a fixed point undergoes a supercritical pitchfork bifurcation, the corresponding quantum state-the ground state-achieves its maximum amount of entanglement near the critical point. We conjecture that this will be a generic feature of systems whose classical limit exhibits such a bifurcation.

Cliona minuscula, sp nov (Hadromerida : Clionaidae) and other bioeroding sponges that only contain tylostyles

A new bioeroding sponge belonging to the genus Cliona is described from the Australian Great Barrier Reef, Cliona minuscula, sp. nov. As the sponge lacked microscleres, comparison with existing clionaid species was difficult. We considered 15 other species of Cliona with only tylostyles: C. alderi, C. arenosa. C. caesia nov. comb., C. californiana, C. celata, C. delitrix, C. dissimilis, C. ecaudis, C. insidiosa, C. janitrix, C. kempi, C. laticavicola, C. macgeachii, C. millepunctata and C. peponaca. Characters of all species are presented in table-form to facilitate comparison during future studies. We listed additional species of Cliona that were not directly compared to the new species, because they were either invalid, insufficiently described, or they may not be obligate bioeroders. The form and dimensions of the megascleres of C. minuscula, sp. nov. indicated that it is distinct from all considered species. Its mean tylostyle dimensions were 225.3 mu m length, 4.5 mu m shaft width and 6.8 mu m tyle width, which is comparatively small. Because other morphological features were small as well ( erosion chambers, papillar diameter), this species was named C. minuscula. The species record for sponges of the genus Cliona reported from Australia is now 11.

Decomposition of complete graphs into 5-cubes

Necessary conditions for the complete graph on n vertices to have a decomposition into 5-cubes are that 5 divides it - 1 and 80 divides it (it - 1)/2. These are known to be sufficient when n is odd. We prove them also sufficient for it even, thus completing the spectrum problem for the 5-cube and lending further weight to a long-standing conjecture of Kotzig. (c) 2005 Wiley Periodicals, Inc.