Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Superconductivity in the 100–120 K region in oxides of the Tl-Ca-Ba-Cu-O system

Oxides with different cation ratios 2122, 2212, 2213 and 2223 in the Ti-Ca-Ba-Cu-O system exhibit onset of superconductivity in the 110–125 K range with zero-resistance in the 95–105 K range. Electron microscopic studies show dislocations, layered morphology and other interesting features. These oxides absorb electromagnetic radiation (9.11 GHz) in the superconducting phase.

Thermodynamic measurements of b.c.c. Cr-Mn solid solutions at 1373 K

Thermodynamics of Cr-Mn alloys have been studied by Eremenko et al (l) using a fused salt e.m.f.technique. Their results indicate positive deviations from ideality at 1023 K. Kaufman (2) has independently estimated negative enthaipy and excess entropy for the b.c.c. Cr-Mn alloys, such that at high temperatures, the entropy term predominates over the enthalpy term giving positive deviations from ideality. Recently the thermodynamic properties of the alloys have been measured by 3acob (3) using a Knudsen cell technique in the temperature range of 1200 to 1500 K. The results indicate mild negative deviations from ideality over the entire composition range. Because of the differences in the reported results and Mn being a volatile component in the alloys which leads to surface depletion under a dynamic set up, an isopiestic technique is used to measure the properties of the alloys.

Activity–Composition Relations in the Nickel Oxide–Magnesium Oxide System at 1300 K by the Solid-State Galvanic Cell Technique

The activity of NiO in NiO-MgO rock salt solid solution has been measured at 1300 K by employing a solid-state galvanic cell: Pt,Ni+ NiO||(CaO)ZrO2||Ni + (Nix,Mgl-x)O, Pt. A high-density tube of Zr02-15 mol% CaO has been used as the solid electrolyte for the emf measurements. The activities of the component oxides in the rock salt solid solution exhibit negative deviation from ideality at the temperature of investigation. The solid solution obeys regular solution behavior at 1300 K. The value of the regular solution parameter is found to be -12000 ((l000) J mol-1. The composition dependence of ΔGEx obtained in this study agrees reasonably well with the calorimetric data reported in the literature for NiO-MgO solid solution.

A XANES study of the K-absorption edge of copper in some of its compounds and use of the same in the determination of bond length

XANES in the K-edge of copper in the systems CuO, Cu(OH)2, La2CuO4, Cu3AsO4 and CuOHF have been investigated and transitions have been assigned to the observed structures. The measurements have been used for calculating the first coordination bond distance in the above systems. It is observed that the values so determined agree fairly well with crystallographic values.

High-Temperature (1023 K to 1273 K 750 degrees C to 1000 degrees C]) Plastic Deformation Behavior of B-Modified Ti-6Al-4V Alloys: Temperature and Strain Rate Effects

A minor addition of B to the Ti-6Al-4V alloy, by similar to 0.1 wt pct, reduces its as-cast prior beta grain size by an order of magnitude, whereas higher B content leads to the presence of in situ formed TiB needles in significant amounts. An experimental investigation into the role played by these microstructural modifications on the high-temperature deformation behavior of Ti-6Al-4V-xB alloys, with x varying between 0 wt pct and 0.55 wt pct, was conducted. Uniaxial compression tests were performed in the temperature range of 1023 K to 1273 K (750 degrees C to 1000 degrees C) and in the strain rate range of 10(-3) to 10(+1) s(-1). True stress-true strain responses of all alloys exhibit flow softening at lower strain rates and oscillations at higher strain rates. The flow softening is aided by the occurrence of dynamic recrystallization through lath globularization in high temperature (1173 K to 1273 K 900 degrees C to 1000 degrees C]) and a lower strain rate (10(-2) to 10(-3) s(-1)) regime. The grain size refinement with the B addition to Ti64, despite being marked, had no significant effect on this. Oscillations in the flow curve at a higher strain rate (10(0) to 10(+1) s(-1)), however, are associated with microstructural instabilities such as bending of laths, breaking of lath boundaries, generation of cavities, and breakage of TiB needles. The presence of TiB needles affected the instability regime. Microstructural evidence suggests that the matrix cavitation is aided by the easy fracture of TiB needles.

Origin of nonmetallicity in PrBa2Cu3O7 from a study of Gd1−xPrxBa2Cu3O7 using soft x-ray absorption at the oxygen K-edge

We present the x-ray absorption data at the oxygen K-edge using total yield technique for Gd1−xPrxba2Cu3O7 (x= 0.0, 0.2, 0.4, 0.6, 0.8, and 1.0). The data clearly to oxygen that the holes doped in the GdBa2Cu3O7 due to oxygen composition are not removed by Pr doping even for the x = 1.0 sample, suggesting that Pr is predominantly in the formally trivalent state. However, the data also clearly indicate the evidence of hybridization effects between the Pr3+ and the adjacent CuO2 layers. This is suggested to be responsible for the progressive suppression of Tc and the metallicity with Pr doping in these systems.

Phase relations in the system BiO1.5–SrO–CuO at 1123 K

Phase relations in the system Bi-Sr-Cu-O at 1123 K have been investigated using optical microscopy, electron-probe microanalysis (EPMA) and powder X-ray diffraction (XRD) of equilibrated samples. Differential thermal analysis (DTA) was used to confirm liquid formation for compositions rich in BiO1.5. Compositions along the three pseudo-binary sections and inside the pseudo-ternary triangle have been examined. The attainment of equilibrium was facilitated by the use of freshly prepared SrO as the starting material. The loss of Bi2O3 from the sample was minimized by double encapsulation. A complete phase diagram at 1123 K is presented. It differs significantly from versions of the phase diagram published recently.

Roofed polyquinanes: synthesis and electronic structure

Starting from readily available norbornenobenzoquinone 7 and employing a photothermal metathesis reaction as the main strategy, novel "roofed" polyquinane bisenones 3 and 13 have been synthesized. Among these, the former is potentially serviceable for further elaboration to dodecahedrane 1. Catalytic hydrogenation of 3 provided the dione 12, which fully inscribes the circumference of dodecahedrane sphere. The "roofed" C-16-bisenone 3 has been successfully annulated to C19-bisenone 24 and C19-trisenone 26 by employing the Greene methodology and Pauson-Khand reaction, respectively. The molecular structures of 3 and 13 were computed using molecular mechanics and semiempirical MO methods. The nonbonded distances between the double bonds vary strongly with the method employed. The interactions between the pi-MO's were, therefore, probed by means of photoelectron (PE) spectroscopy. Comparison with the PE spectra of a series of model systems with increasing complexity enabled an unambiguous assignment of the observed peaks. The symmetric and antisymmetric combinations of the pi-MO's of the enone moieties of 3 and 13 show large splittings, characteristic of propano-bridged systems in which through-space and through-bond effects act in concert.

Complete Pick positivity and unitary invariance

The characteristic function for a contraction is a classical complete unitary invariant devised by Sz.-Nagy and Foias. Just as a contraction is related to the Szego kernel k(S) (z, w) = (1 - z (w) over tilde)(-1) for |z|, |w| < 1, by means of (1/k(S))(T,T*) >= 0, we consider an arbitrary open connected domain Omega in C-n, a complete Pick kernel k on Omega and a tuple T = (T-1, ..., T-n) of commuting bounded operators on a complex separable Hilbert space H such that (1/k)(T,T*) >= 0. For a complete Pick kernel the 1/k functional calculus makes sense in a beautiful way. It turns out that the model theory works very well and a characteristic function can be associated with T. Moreover, the characteristic function is then a complete unitary invariant for a suitable class of tuples T.

Chemical Shift of the X-Ray K-Absorption Edge of Cu in Some of Its Compounds, Complexes and Superconductors

Chemical shifts, ΔE, of the X-ray K-absorption edge in several compounds, complexes of copper including its superconducting oxides possessing formal oxidation states +1 and +2 have been measured. It has been shown that the chemical shift is primarily governed by the effective ionic charge on the absorbing ion and the nature of the atoms in the first coordination shell around the absorbing ion. The relation between the chemical shift, ΔE , and the effective charge q on the absorbing ion is found to be ΔE=Aq+Bq2+Cq3+Dq4 (A, B, C and D are constants). The effects of electronegativity, atomic number, oxidation state, crystal structure, the valence d-orbital electrons, etc. on the X-ray absorption chemical shift have been discussed. ©1990 The Physical Society of Japan

Phase Relations in the System CaO-Fe2O3-Y2O3 at 1273 K and Compatibility Between Y1-xCaxFeO3-0.5x and Stabilized Zirconia

Phase relations in the system CaO-Fe2O3-Y2O3 in air (P-O2/P-o = 0.21) were explored by equilibrating samples representing eleven compositions in the ternary at 1273 K, followed by quenching to room temperature and phase identification using XRD. Limited mutual solubility was observed between YFeO3 and Ca2Fe2O5. No quaternary oxide was identified. An isothermal section of the phase diagram at 1273 K was constructed from the results. Five three-phase regions and four extended two-phase regions were observed. The extended two-phase regions arise from the limited solid solutions based on the ternary oxides YFeO3 and Ca2Fe2O5. Activities of CaO, Fe2O3 and Y2O3 in the three-phase fields were computed using recently measured thermodynamic data on the ternary oxides. The experimental phase diagram is consistent with thermodynamic data. The computed activities of CaO indicate that compositions of CaO-doped YFeO3 exhibiting good electrical conductivity are not compatible with zirconia-based electrolytes; CaO will react with ZrO2 to form CaZrO3.

An automated thermal relaxation calorimeter for operation at low temperature (0.5 K

We describe an automated calorimeter for measurement of specific heat in the temperature range 10 K>T>0.5 K. It uses sample of moderate size (100–1000 mg), has a moderate precision and accuracy (2%–5%), is easy to operate and the measurements can be done quickly with He4 economy. The accuracy of this calorimeter was checked by measurement of specific heat of copper and that of aluminium near its superconducting transition temperature.