Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number eta(G) of a graph G is the largest integer n for which the complete graph K-n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, eta(G) >= chi(G), where chi(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product G square H of graphs. As the main result of this paper, we prove that eta(G(1) square G(2)) >= h root 1 (1 - o(1)) for any two graphs G(1) and G(2) with eta(G(1)) = h and eta(G(2)) = l. We show that the above lower bound is asymptotically best possible when h >= l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: 1. Let G be a connected graph. Let G = G(1) square G(2) square ... square G(k) be the ( unique) prime factorization of G. Then G satisfies Hadwiger's conjecture if k >= 2 log log chi(G) + c', where c' is a constant. This improves the 2 log chi(G) + 3 bound in [2] 2. Let G(1) and G(2) be two graphs such that chi(G1) >= chi(G2) >= clog(1.5)(chi(G(1))), where c is a constant. Then G1 square G2 satisfies Hadwiger's conjecture. 3. Hadwiger's conjecture is true for G(d) (Cartesian product of G taken d times) for every graph G and every d >= 2. This settles a question by Chandran and Sivadasan [2]. ( They had shown that the Hadiwger's conjecture is true for G(d) if d >= 3).

N,N′-Bis(aryl)pyridine-2,6-dicarboxamide complexes of ruthenium: Synthesis, structure and redox properties

Reaction of five N,N′-bis(aryl)pyridine-2,6-dicarboxamides (H2L-R, where H2 denotes the two acidic protons and R (R = OCH3, CH3, H, Cl and NO2) the para substituent in the aryl fragment) with [Ru(trpy)Cl3](trpy = 2,2′,2″-terpyridine) in refluxing ethanol in the presence of a base (NEt3) affords a group of complexes of the type [RuII(trpy)(L-R)], each of which contains an amide ligand coordinated to the metal center as a dianionic tridentate N,N,N-donor along with a terpyridine ligand. Structure of the [RuII(trpy)(L-Cl)] complex has been determined by X-ray crystallography. All the Ru(II) complexes are diamagnetic, and show characteristic 1H NMR signals and intense MLCT transitions in the visible region. Cyclic voltammetry on the [RuII(trpy)(L-R)] complexes shows a Ru(II)–Ru(III) oxidation within 0.16–0.33 V versus SCE. An oxidation of the coordinated amide ligand is also observed within 0.94–1.33 V versus SCE and a reduction of coordinated terpyridine ligand within −1.10 to −1.15 V versus SCE. Constant potential coulometric oxidation of the [RuII(trpy)(L-R)] complexes produces the corresponding [RuIII(trpy)(L-R)]+ complexes, which have been isolated as the perchlorate salts. Structure of the [RuIII(trpy)(L-CH3)]ClO4 complex has been determined by X-ray crystallography. All the Ru(III) complexes are one-electron paramagnetic, and show anisotropic ESR spectra at 77 K and intense LMCT transitions in the visible region. A weak ligand-field band has also been shown by all the [RuIII(trpy)(L-R)]ClO4 complexes near 1600 nm.

Avian diversification patterns across the K-Pg boundary: Influence of calibrations, datasets, and model misspecification

Birds represent the most diverse extant tetrapod clade, with ca. 10,000 extant species, and the timing of the crown avian radiation remains hotly debated. The fossil record supports a primarily Cenozoic radiation of crown birds, whereas molecular divergence dating analyses generally imply that this radiation was well underway during the Cretaceous. Furthermore, substantial differences have been noted between published divergence estimates. These have been variously attributed to clock model, calibration regime, and gene type. One underappreciated phenomenon is that disparity between fossil ages and molecular dates tends to be proportionally greater for shallower nodes in the avian Tree of Life. Here, we explore potential drivers of disparity in avian divergence dates through a set of analyses applying various calibration strategies and coding methods to a mitochondrial genome dataset and an 18-gene nuclear dataset, both sampled across 72 taxa. Our analyses support the occurrence of two deep divergences (i.e., the Palaeognathae/Neognathae split and the Galloanserae/Neoaves split) well within the Cretaceous, followed by a rapid radiation of Neoaves near the K-Pg boundary. However, 95% highest posterior density intervals for most basal divergences in Neoaves cross the boundary, and we emphasize that, barring unreasonably strict prior distributions, distinguishing between a rapid Early Paleocene radiation and a Late Cretaceous radiation may be beyond the resolving power of currently favored divergence dating methods. In contrast to recent observations for placental mammals, constraining all divergences within Neoaves to occur in the Cenozoic does not result in unreasonably high inferred substitution rates. Comparisons of nuclear DNA (nDNA) versus mitochondrial DNA (mtDNA) datasets and NT- versus RY-coded mitochondrial data reveal patterns of disparity that are consistent with substitution model misspecifications that result in tree compression/tree extension artifacts, which may explain some discordance between previous divergence estimates based on different sequence types. Comparisons of fully calibrated and nominally calibrated trees support a correlation between body mass and apparent dating error. Overall, our results are consistent with (but do not require) a Paleogene radiation for most major clades of crown birds.

Phase Diagram for the System RuO2-TiO2 in Air

There are conflicting reports in the literature regarding solid solubility in the system RuO2-TiO2. To resolve this issue a few experiments were conducted in air at 1673, 1723, and 1773 K. The results show limited terminal solid solubility. There is an extended solid-state miscibility gap that intersects the decomposition curve for the RuO2-rich solid solution generating a peritectoid reaction at 1698 K. The measured equilibrium compositions of the solid solutions are used to develop a thermodynamic description of the oxide solid solution with rutile structure. Using the subregular solution model, the enthalpy of mixing can be represented by the expression, Delta H-M/J center dot mol(-1) = XTiO2XRuO2 ( 34,100X(TiO2) + 30,750X(RuO2)). The binodal and spinodal curves and T-X phase diagram in air are computed using this datum and Gibbs energy of formation of RuO2 available in the literature. The computed results suggest that equilibrium was not attained during solubility measurements at lower temperatures reported in the literature.

Solubilities of Hexadecanoic and Octadecanoic Acids in Supercritical CO2 With and Without Cosolvents

The solubilities of hexadecanoic acid (palmitic acid) and octadecanoic acid (stearic acid) in supercritical carbon dioxide without cosolvents and with two cosolvents, namely, ethanol and 3-methyl-1-butanol, were determined at (308 and 318) K at pressures varying from (12.8 to 22.6) MPa. The solubility data, in both the absence and presence of cosolvents, were correlated by a model proposed by Mendez-Santiago and Teja.

Phosphorus Partition between Liquid Steel and CaO-SiO2-P2O5-MgO Slag Containing Low FeO

CaO-SiO2-FeOx-P2O5-MgO bearing slags are typical in the basic oxygen steelmaking (BOS) process. The partition ratio of phosphorus between slag and steel is an index of the phosphorus holding capacity of the slag, which determines the phosphorus content achievable in the finished steel. The influences of FeO concentration and basicity on the equilibrium phosphorus partition ratios were experimentally determined at temperatures of 1873 and 1923 K, for conditions of MgO saturation. The partition ratio initially increased with basicity but attained a constant value beyond basicity of 2.5. An increase in FeO concentration up to approximately 13 to 14 mass pet was beneficial for phosphorus partition.

Thermodynamic Properties and Phase Diagram for the System MoO2–TiO2

The activity of molybdenum dioxide (MoO2) in the MoO2–TiO2 solid solutions was measured at 1600 K using a solid-state cell incorporating yttria-doped thoria as the electrolyte. For two compositions, the emf was also measured as a function of temperature. The cell was designed such that the emf is directly related to the activity of MoO2 in the solid solution. The results show monotonic variation of activity with composition, suggesting a complete range of solid solutions between the end members and the occurrence of MoO2 with a tetragonal structure at 1600 K. A large positive deviation from Raoult's law was found. Excess Gibbs energy of mixing is an asymmetric function of composition and can be represented by the subregular solution model of Hardy as follows.The temperature dependence of the emf for two compositions is reasonably consistent with ideal entropy of mixing. A miscibility gap is indicated at a lower temperature with the critical point characterized by Tc (K)=1560 and . Recent studies indicate that MoO2 undergoes a transition from a monoclinic to tetragonal structure at 1533 K with a transition entropy of 9.91 J·(mol·K)−1. The solid solubility of TiO2 with rutile structure in MoO2 with a monoclinic structure is negligible. These features give rise to a eutectoid reaction at 1412 K. The topology of the computed phase diagram differs significantly from that suggested by Pejryd.

Thermodynamic activities in the Pb(Zr1-XTiX)O-3 solid solution at 1373 K

Although Pb(Zr1-XTiX)O-3 solid solution is the cornerstone of the piezoelectric ceramics, there is no information in the literature on thermodynamic activities of the component phases in the solid solution. Using inter-crystalline ion exchange equilibria between Pb(Zr1-XTiX)O-3 solid solution with cubic perovskite structure and (Zr1-YTiY)O-2 solid solutions with monoclinic and tetragonal structures, activities of PbTiO3 and PbZrO3 in the perovskite solid solution have been derived at 1373 K using the modified Gibbs-Duhem integration technique of Jacob and Jeffes. Tie-lines from the cubic solid solution are skewed towards the ZrO2 corner. Activities in the zirconia-rich (Zr1-YTiY)02 solid solutions are taken from a recent emf study. The results for the perovskite solid solution at 1373 K can be represented by a sub-regular solution model: Delta G(E.M) (J mol(-1)) = X-PbTiO3 X-PbZrO3(5280X(PbTiO3) - 1980X(PbZrO3)) where Delta G(E.M) is the excess Gibbs energy of mixing of the cubic solid solution and Xi represents the mole fraction of component i. There is a significant positive deviation from ideality for PbTiO3-rich compositions and mild negative deviation near the PbZrO3 corner. The cubic solid solution is intrinsically stable against composition fluctuations at temperatures down to 840 K. The results contrast sharply with the recent calorimetric data on enthalpy of mixing which signal instability of the cubic perovskite solid solution. (C) 2007 Elsevier B.V. All rights reserved.

Dielectric, Ferroelectric and Relaxor Behavior of BaLaxBi4-xTi4O15 Ceramics

Monophasic BaLaxBi4-xTi4O15 (x = 0, 0.2, 0.4, 0.6 and 0.8) ceramics, fabricated from the powders synthesized via the solid-state reaction route exhibited relaxor behavior. Dielectric properties of the well sintered ceramics were measured in a wide frequency range (1 kHz-1 MHz) at different temperatures (300-750 K). The temperature of dielectri maximum (T-m) was found to decrease significantly from 696 K for an undoped sample (x = 0) to 395 K for the sample corresponding to the composition x = 0.8 accompanied by a decrease in the magnitude ofdielectric maximum (epsilon(m)). The temperature variation of the dielectric constant on the high temperature slope of the peak (T > T-m) was analyzed by using the Lorentz-ype quadratic law and the diffuseness of the peak was found to increase with increasing x. Vogel-Fulcher modelling of dielectric relaxation showed a decrease in freezing temperature (T-VF) (from 678 to 340 K) and an increase in the activation energy (5 to 24 meV) for the frequency dispersion with increase in x (La-3 divided by content). Strength of frequency dispersion of the phase transition increased with lanthanum content. Polarization (P)-electric field (E) hysteresis loops recorded at 373 showed a transition from a nearly squarish to slim loop hysteresis behavior with increasing lanthanum content.

Profiling k-Iteration Paths : A Generalization of the Ball-Larus Profiling Algorithm

The Ball-Larus path-profiling algorithm is an efficient technique to collect acyclic path frequencies of a program. However, longer paths -those extending across loop iterations - describe the runtime behaviour of programs better. We generalize the Ball-Larus profiling algorithm for profiling k-iteration paths - paths that can span up to to k iterations of a loop. We show that it is possible to number suchk-iteration paths perfectly, thus allowing for an efficient profiling algorithm for such longer paths. We also describe a scheme for mixed-mode profiling: profiling different parts of a procedure with different path lengths. Experimental results show that k-iteration profiling is realistic.

Dimensional Reduction Near the Deconfinement Transition

When ordinary nuclear matter is heated to a high temperature of ~ 10^12 K, it undergoes a deconfinement transition to a new phase, strongly interacting quark-gluon plasma. While the color charged fundamental constituents of the nuclei, the quarks and gluons, are at low temperatures permanently confined inside color neutral hadrons, in the plasma the color degrees of freedom become dominant over nuclear, rather than merely nucleonic, volumes. Quantum Chromodynamics (QCD) is the accepted theory of the strong interactions, and confines quarks and gluons inside hadrons. The theory was formulated in early seventies, but deriving first principles predictions from it still remains a challenge, and novel methods of studying it are needed. One such method is dimensional reduction, in which the high temperature dynamics of static observables of the full four-dimensional theory are described using a simpler three-dimensional effective theory, having only the static modes of the various fields as its degrees of freedom. A perturbatively constructed effective theory is known to provide a good description of the plasma at high temperatures, where asymptotic freedom makes the gauge coupling small. In addition to this, numerical lattice simulations have, however, shown that the perturbatively constructed theory gives a surprisingly good description of the plasma all the way down to temperatures a few times the transition temperature. Near the critical temperature, the effective theory, however, ceases to give a valid description of the physics, since it fails to respect the approximate center symmetry of the full theory. The symmetry plays a key role in the dynamics near the phase transition, and thus one expects that the regime of validity of the dimensionally reduced theories can be significantly extended towards the deconfinement transition by incorporating the center symmetry in them. In the introductory part of the thesis, the status of dimensionally reduced effective theories of high temperature QCD is reviewed, placing emphasis on the phase structure of the theories. In the first research paper included in the thesis, the non-perturbative input required in computing the g^6 term in the weak coupling expansion of the pressure of QCD is computed in the effective theory framework at an arbitrary number of colors. The two last papers on the other hand focus on the construction of the center-symmetric effective theories, and subsequently the first non-perturbative studies of these theories are presented. Non-perturbative lattice simulations of a center-symmetric effective theory for SU(2) Yang-Mills theory show --- in sharp contrast to the perturbative setup --- that the effective theory accommodates a phase transition in the correct universality class of the full theory. This transition is seen to take place at a value of the effective theory coupling constant that is consistent with the full theory coupling at the critical temperature.

Metal-spinel-corundum three phase equilibria in the system Ni-Cr-Al-O at 1373 K

The tie-lines representing the inter-crystalline ion exchange equilibria between the NiCr2O4-NiAl2O4 spinet solid solution and Cr2O3-Al2O3 corundum solid solution are determined by electron microprobe andEDAX pointcountanalysis of the oxide phases equilibrated with metallic Ni at 1373 K. The component activities in the spinet solid solution are derived from the tie-lines and thermodynamic data for Cr2O3-Al2O3 solid solution available in the literature. The Gibbs energy of mixing of the spinet solid solution calculated from the experimental data is discussed in relation to the values derived from the cation distribution models which assume random mixing of cations on both tetrahedral and octahedral sites. Positive deviation from the models is observed indicating significant positive enthalpy contribution arising form the size mismatch between Al+3 and Ni+2 ions on the tetrahedral site and Al+3, Ni+2 and Cr+3 on the octahedral site. Variation of the oxygen potential for threephase equilibrium involving metallic nickel, spinet solid solution and corundum solid solution is computed as a function of composition of the solid solutions at 1373 K. The oxygen potential exhibits a minimum at aluminum cationic fraction eta(Al)/(eta(Al) + eta(Cr)) = 0.524 in the oxide solid solutions.

If dung beetles (Scarabaeidae: Scarabaeinae) arose in association with dinosaurs, did they also suffer a mass co-extinction at the K-Pg boundary?

The evolutionary success of beetles and numerous other terrestrial insects is generally attributed to co-radiation with flowering plants but most studies have focused on herbivorous or pollinating insects. Non-herbivores represent a significant proportion of beetle diversity yet potential factors that influence their diversification have been largely unexamined. In the present study, we examine the factors driving diversification within the Scarabaeidae, a speciose beetle family with a range of both herbivorous and non-herbivorous ecologies. In particular, it has been long debated whether the key event in the evolution of dung beetles (Scarabaeidae: Scarabaeinae) was an adaptation to feeding on dinosaur or mammalian dung. Here we present molecular evidence to show that the origin of dung beetles occurred in the middle of the Cretaceous, likely in association with dinosaur dung, but more surprisingly the timing is consistent with the rise of the angiosperms. We hypothesize that the switch in dinosaur diet to incorporate more nutritious and less fibrous angiosperm foliage provided a palatable dung source that ultimately created a new niche for diversification. Given the well-accepted mass extinction of non-avian dinosaurs at the Cretaceous-Paleogene boundary, we examine a potential co-extinction of dung beetles due to the loss of an important evolutionary resource, i.e., dinosaur dung. The biogeography of dung beetles is also examined to explore the previously proposed "out of Africa" hypothesis. Given the inferred age of Scarabaeinae as originating in the Lower Cretaceous, the major radiation of dung feeders prior to the Cenomanian, and the early divergence of both African and Gondwanan lineages, we hypothesise that that faunal exchange between Africa and Gondwanaland occurred during the earliest evolution of the Scarabaeinae. Therefore we propose that both Gondwanan vicariance and dispersal of African lineages is responsible for present day distribution of scarabaeine dung beetles and provide examples.

RACK: RApid Clustering using K-means algorithm

The k-means algorithm is an extremely popular technique for clustering data. One of the major limitations of the k-means is that the time to cluster a given dataset D is linear in the number of clusters, k. In this paper, we employ height balanced trees to address this issue. Specifically, we make two major contributions, (a) we propose an algorithm, RACK (acronym for RApid Clustering using k-means), which takes time favorably comparable with the fastest known existing techniques, and (b) we prove an expected bound on the quality of clustering achieved using RACK. Our experimental results on large datasets strongly suggest that RACK is competitive with the k-means algorithm in terms of quality of clustering, while taking significantly less time.