The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Witten index of supersymmetric chiral theories

The Witten index can be defined in many supersymmetric theories by formulating them in the space-time R×S3. If the index is nonzero for any value of the radius of S3, it can be shown that the theory does not break supersymmetry in Minkowski space. This approach rules out supersymmetry breaking in a large class of models, chiral and otherwise. The index arguments are consistent with previous instanton calculations which indicate supersymmetry breaking in certain theories.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

RAD51C: a novel cancer susceptibility gene is linked to Fanconi anemia and breast cancer

Germline mutations in many of the genes that are involved in homologous recombination (HR)-mediated DNA double-strand break repair (DSBR) are associated with various human genetic disorders and cancer. RAD51 and RAD51 paralogs are important for HR and in the maintenance of genome stability. Despite the identification of five RAD51 paralogs over a decade ago, the molecular mechanism(s) by which RAD51 paralogs regulate HR and genome maintenance remains obscure. In addition to the known roles of RAD51C in early and late stages of HR, it also contributes to activation of the checkpoint kinase CHK2. One recent study identifies biallelic mutation in RAD51C leading to Fanconi anemia-like disorder. Whereas a second study reports monoallelic mutation in RAD51C associated with increased risk of breast and ovarian cancer. These reports show RAD51C is a cancer susceptibility gene. In this review, we focus on describing the functions of RAD51C in HR, DNA damage signaling and as a tumor suppressor with an emphasis on the new roles of RAD51C unveiled by these reports.

Analysis of continuum using boundary compatibility conditions of integrated force method

Static and vibration problems of an indeterminate continuum are traditionally analyzed by the stiffness method. The force method is more or less non-existent for such problems. This situation is primarily due to the incomplete state of development of the compatibility conditions which are essential for the analysis of indeterminate structures by the flexibility method. The understanding of the Compatibility Conditions (CC) has been substantially augmented. Based on the understanding of CC, a novel formulation termed the Integrated Force Method (IFM) has been established. In this paper IFM has been extended for the static and vibration analyses of a continuum. The IFM analysis is illustrated taking three examples: 1. (1) rectangular plate in flexure 2. (2) analysis of a cantilevered dam 3. (3) free vibration analysis of a beam. From the examples solved it is observed that the force response of an indeterminate continuum with mixed boundary conditions can be generated by IFM without any reference to displacements in the field or on the boundary. Displacements if required can be calculated by back substitution.

Theory of the effects of destruction of localization by inelastic scattering in the resistivity of pure thin potassium wires

Measurements of the electrical resistivity of thin potassium wires at temperatures near 1 K have revealed a minimum in the resistivity as a function of temperature. By proposing that the electrons in these wires have undergone localization, albeit with large localization length, and that inelastic-scattering events destroy the coherence of that state, we can explain both the magnitude and shape of the temperature-dependent resistivity data. Localization of electrons in these wires is to be expected because, due to the high purity of the potassium, the elastic mean free path is comparable to the diameters of the thinnest samples, making the Thouless length lT (or inelastic diffusion length) much larger than the diameter, so that the wire is effectively one dimensional. The inelastic events effectively break the wire into a series of localized segments, whose resistances can be added to obtain the total resistance of the wire. The ensemble-averaged resistance for all possible segmented wires, weighted with a Poisson distribution of inelastic-scattering lengths along the wire, yields a length dependence for the resistance that is proportional to [L3/lin(T)], provided that lin(T)?L, where L is the sample length and lin(T) is some effective temperature-dependent one-dimensional inelastic-scattering length. A more sophisticated approach using a Poisson distribution in inelastic-scattering times, which takes into account the diffusive motion of the electrons along the wire through the Thouless length, yields a length- and temperature-dependent resistivity proportional to (L/lT)4 under appropriate conditions. Inelastic-scattering lifetimes are inferred from the temperature-dependent bulk resistivities (i.e., those of thicker, effectively three-dimensional samples), assuming that a minimum amount of energy must be exchanged for a collision to be effective in destroying the phase coherence of the localized state. If the dominant inelastic mechanism is electron-electron scattering, then our result, given the appropriate choice of the channel number parameter, is consistent with the data. If electron-phason scattering were of comparable importance, then our results would remain consistent. However, the inelastic-scattering lifetime inferred from bulk resistivity data is too short. This is because the electron-phason mechanism dominates in the inelastic-scattering rate, although the two mechanisms may be of comparable importance for the bulk resistivity. Possible reasons why the electron-phason mechanism might be less effective in thin wires than in bulk are discussed.

Compressible MHD boundary layer in the stagnation region of a sphere

The steady laminar compressible boundary layer flow of an electrically conducting fluid in the stagnation region of a sphere with an applied magnetic field has been studied. The effects of the induced magnetic field, mass transfer, and viscous dissipation have been taken into account. Both isothermal and adiabatic wall conditions have been considered. The governing equations have been solved numerically using a shooting method. The skin friction and heat transfer are found to be strongly affected by the magnetic field, mass transfer, wall temperature and Mach number. It is found that the magnetic field reduces the heat transfer. This is a significant result which can be used in controlling the heat transfer rate. The boundary layer solutions break down as the magnetic parameter tends to a certain critical value.

Consistency limits behavior of bentonites exposed to sea water

This article examines the changes in interparticle forces brought about on prolonged contact (1 year period) of a bentonite clay with artificial seawater. The study is undertaken with the purpose of identifying the physico-chemical factors that impart a nonswelling character to smectite clays deposited in marine environments. Results show that equilibration of the bentonite clay with artificial seawater (total pore salinity approximately 42 gL-1) for a 1 year period does not lead to any mineralogical changes in the clay specimens; however, their exchangeable cation positions become prominently dominated by magnesium ions. The consistency limits of the seawater-equilibrated bentonite was determined on stepwise leaching to lower salinities. The predominance of diffuse double-layer repulsion forces in the pore salt concentration range of 42 gL-1 to 1.1 gL-1 caused an increase in the liquid limits of the seawater-equilibrated bentonite specimens on reducing the salinity in the corresponding range (42 gL-1 to 1.1 gL-1). The attraction forces, however, prevail over the repulsion forces at salt concentrations <1.1 gL-1 and cause a decrease in liquid limit of the clay specimens with reduction in pore salinity, which is typical of nonswelling clays. The attraction forces cause aggregation of the clay unit layers into domains that break down on sodium saturation of the clay specimens. It is inferred that the physico-chemical factors responsible for the nonswelling character of the seawater-equilibrated bentonite specimens at pore salt concentrations below 1.1 gL-1 are inadequate to explain the nonswelling character of smectite-rich Ariake marine clays. The lower consistency limits of the Ariake marine clays in comparison to the nonswelling character, seawater-equilibrated bentonite specimens is attributed to a relative deficiency of interparticle forces in the Ariake marine clay.

A monolithic strategy for fluid-structure interaction problems

In this work, we present a new monolithic strategy for solving fluid-structure interaction problems involving incompressible fluids, within the context of the finite element method. This strategy, similar to the continuum dynamics, conserves certain properties, and thus provides a rational basis for the design of the time-stepping strategy; detailed proofs of the conservation of these properties are provided. The proposed algorithm works with displacement and velocity variables for the structure and fluid, respectively, and introduces no new variables to enforce velocity or traction continuity. Any existing structural dynamics algorithm can be used without change in the proposed method. Use of the exact tangent stiffness matrix ensures that the algorithm converges quadratically within each time step. An analytical solution is presented for one of the benchmark problems used in the literature, namely, the piston problem. A number of benchmark problems including problems involving free surfaces such as sloshing and the breaking dam problem are used to demonstrate the good performance of the proposed method. Copyright (C) 2010 John Wiley & Sons, Ltd.

Extended gravitational action and novel consequences

It is found that the inclusion of higher derivative terms in the gravitational action along with concepts of phase transition and spontaneous symmetry breaking leads to some novel consequence. The Ricci scalar plays the dual role, like a physical field as well as a geometrical field. One gets Klein-Gordon equation for the emerging field and the corresponding quanta of geometry are called Riccions. For the early universe the model removes singularity along with inflation. In higher dimensional gravity the Riccions can break into spin half particle and antiparticle along with breaking of left-right symmetry. Most tantalizing consequences is the emergence of the physical universe from the geometry in the extreme past. Riccions can Bose condense and may account for the dark matter.

Scroll-Wave Dynamics in Human Cardiac Tissue: Lessons from a Mathematical Model with Inhomogeneities and Fiber Architecture

Cardiac arrhythmias, such as ventricular tachycardia (VT) and ventricular fibrillation (VF), are among the leading causes of death in the industrialized world. These are associated with the formation of spiral and scroll waves of electrical activation in cardiac tissue; single spiral and scroll waves are believed to be associated with VT whereas their turbulent analogs are associated with VF. Thus, the study of these waves is an important biophysical problem. We present a systematic study of the combined effects of muscle-fiber rotation and inhomogeneities on scroll-wave dynamics in the TNNP (ten Tusscher Noble Noble Panfilov) model for human cardiac tissue. In particular, we use the three-dimensional TNNP model with fiber rotation and consider both conduction and ionic inhomogeneities. We find that, in addition to displaying a sensitive dependence on the positions, sizes, and types of inhomogeneities, scroll-wave dynamics also depends delicately upon the degree of fiber rotation. We find that the tendency of scroll waves to anchor to cylindrical conduction inhomogeneities increases with the radius of the inhomogeneity. Furthermore, the filament of the scroll wave can exhibit drift or meandering, transmural bending, twisting, and break-up. If the scroll-wave filament exhibits weak meandering, then there is a fine balance between the anchoring of this wave at the inhomogeneity and a disruption of wave-pinning by fiber rotation. If this filament displays strong meandering, then again the anchoring is suppressed by fiber rotation; also, the scroll wave can be eliminated from most of the layers only to be regenerated by a seed wave. Ionic inhomogeneities can also lead to an anchoring of the scroll wave; scroll waves can now enter the region inside an ionic inhomogeneity and can display a coexistence of spatiotemporal chaos and quasi-periodic behavior in different parts of the simulation domain. We discuss the experimental implications of our study.

Intraseasonal Variation of the Summer Monsoon I:Observational Aspects

Within the summer monsoon, the circulation and rainfall over the Indian region exhibit large variations over the synoptic scale of 3-7 days and the supersynoptic scales of 10 days and longer. In this paper we discuss some facets of intraseasonal variation on the supersynoptic scale on the basis of existing observational studies and some new analysis. The major variation of the summer monsoon rainfall on this scale is the active-break cycle. The deep convection over the Indian region on a typical day in the active phase is organized over thousands of kilometers in the zonal direction and is associated with a tropical convergence zone (TCZ). The intraseasonal variations on the supersynoptic scale are also coherent on these scales and are related to the space-time variation of the large-scale TCZ. The latitudinal distribution of the occurrence of the TCZ is bimodal with the primary mode over the heated continent and a secondary mode over the ocean. The variation of the continental TCZ is generally out of phase with that of the oceanic TCZ. During the active spells, the TCZ persists over the continent in the monsoon zone. The revival from breaks occurs either by northward propagation of the TCZ over the equatorial Indian Ocean or by genesis of a disturbance in the monsoon zone (often as a result of westward propagations from W. Pacific). The mechanisms governing the fluctuation between active spells and breaks, the interphase transition and the complex interactions of the TCZ over the Indian subcontinent with the TCZ over the equatorial Indian Ocean and the W. Pacific, have yet to be completely understood.

Jet interaction in liquid-liquid coaxial injectors

Interaction between two conical sheets of liquid formed by a coaxial swirl injector has been studied using water in the annular orifice and potassium permanganate solution in the inner orifice. Experiments using photographic techniques have been conducted to study the influence of the inner jet on outer conical sheet spray characteristics such as spray cone angle and break-up length. The core spray has a strong influence on the outer sheet when the pressure drop in the latter is low. This is attributed to the pressure variations caused by ejector effects. This paper also discusses the merging and separation behavior of the liquid sheets which exhibits hysteresis effect while injector pressure drop is varied.

Critical earthquake input power spectral density function models for engineering structures

The problem of determining optimal power spectral density models for earthquake excitation which satisfy constraints on total average power, zero crossing rate and which produce the highest response variance in a given linear system is considered. The solution to this problem is obtained using linear programming methods. The resulting solutions are shown to display a highly deterministic structure and, therefore, fail to capture the stochastic nature of the input. A modification to the definition of critical excitation is proposed which takes into account the entropy rate as a measure of uncertainty in the earthquake loads. The resulting problem is solved using calculus of variations and also within linear programming framework. Illustrative examples on specifying seismic inputs for a nuclear power plant and a tall earth dam are considered and the resulting solutions are shown to be realistic.

Primary Sequence That Determines the Functional Overlap between Mitochondrial Heat Shock Protein 70 Ssc1 and Ssc3 of Saccharomyces cerevisiae

The evolutionary diversity of the HSP70 gene family at the genetic level has generated complex structural variations leading to altered functional specificity and mode of regulation in different cellular compartments. By utilizing Saccharomyces cerevisiae as a model system for better understanding the global functional cooperativity between Hsp70 paralogs, we have dissected the differences in functional properties at the biochemical level between mitochondrial heat shock protein 70 (mtHsp70) Ssc1 and an uncharacterized Ssc3 paralog. Based on the evolutionary origin of Ssc3 and a high degree of sequence homology with Ssc1, it has been proposed that both have a close functional overlap in the mitochondrial matrix. Surprisingly, our results demonstrate that there is no functional cross-talk between Ssc1 and Ssc3 paralogs. The lack of in vivo functional overlap is due to altered conformation and significant lower stability associated with Ssc3. The substrate-binding domain of Ssc3 showed poor affinity toward mitochondrial client proteins and Tim44 due to the open conformation in ADP-bound state. In addition to that, the nucleotide-binding domain of Ssc3 showed an altered regulation by the Mge1 co-chaperone due to a high degree of conformational plasticity, which strongly promotes aggregation. Besides, Ssc3 possesses a dysfunctional inter-domain interface thus rendering it unable to perform functions similar to generic Hsp70s. Moreover, we have identified the critical amino acid sequence of Ssc1 and Ssc3 that can ``make or break'' mtHsp70 chaperone function. Together, our analysis provides the first evidence to show that the nucleotide-binding domain of mtHsp70s plays a critical role in determining the functional specificity among paralogs and orthologs across kingdoms.