Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R(1)x...xR(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. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least pi(alpha-1/alpha) for some alpha is an element of N(>= 2), then box(G) <= alpha (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree Delta < [n(alpha-1)/2 alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. We also demonstrate a graph having box(G) > alpha but with Delta = n (alpha-1)/2 alpha + n/2 alpha(alpha+1) + (alpha+2). For a proper circular arc graph G, we show that if Delta < [n(alpha-1)/alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) <= r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k <= 3 arcs covers the circle, then box(G) <= 3 and if G admits a circular arc representation in which no family of k <= 4 arcs covers the circle, then box(G) <= 2. We also show that both these bounds are tight.

Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Role of Nonplanar Peptide Unit in Regular Polypeptide Helices - New Model for Pply-Beta-Benzyl-L-Aspartate

The effect of non-planarity of the peptide unit on helical structures stabilized by intrachain hydrogen bonds is discussed. While the present calculations generally agree with those already reported in the literature for right-handed helical structures, it is found that the most stable left-handed structure is a novel helix, called the delta-helix. Its helical parameters are close to these reported for poly-beta-benzyl-L -aspartate. Conformational energy calculations show that poly-beta-benzyl-L -aspartate with the delta-helical structure is considerably more stable than the structure it is generally believed to take up (the omega-helix) by about 15 kcal/mol-residue.

Exact entanglement studies of strongly correlated systems: role of long-range interactions and symmetries of the system

We study the bipartite entanglement of strongly correlated systems using exact diagonalization techniques. In particular, we examine how the entanglement changes in the presence of long-range interactions by studying the Pariser-Parr-Pople model with long-range interactions. We compare the results for this model with those obtained for the Hubbard and Heisenberg models with short-range interactions. This study helps us to understand why the density matrix renormalization group (DMRG) technique is so successful even in the presence of long-range interactions. To better understand the behavior of long-range interactions and why the DMRG works well with it, we study the entanglement spectrum of the ground state and a few excited states of finite chains. We also investigate if the symmetry properties of a state vector have any significance in relation to its entanglement. Finally, we make an interesting observation on the entanglement profiles of different states (across the energy spectrum) in comparison with the corresponding profile of the density of states. We use isotropic chains and a molecule with non-Abelian symmetry for these numerical investigations.

Role of water contamination within the GC column of a GasBench II peripheral on the reproducibility of O-18/O-16 ratios in water samples

The GasBench II peripheral along with MAT 253 combination provides a more sensitive platform for the determination of water isotope ratios. Here, we examined the role of adsorbed moisture within the gas chromatography (GC) column of the GasBench II on measurement uncertainties. The uncertainty in O-18/O-16 ratio measurements is determined by several factors, including the presence of water in the GC. The contamination of GC with water originating from samples as water vapour over a longer timeframe is a critical factor in determining the reproducibility of O-18/O-16 ratios in water samples. The shift in isotope ratios observed in the experiment under dry and wet conditions correlates strongly with the retention time of analyte CO2, indicating the effect of accumulated moisture. Two possible methods to circumvent or minimise the effect of adsorbed water on isotope ratios are presented here. The proposed methodology includes either the regular baking of the GC column at a higher temperature (120 degrees C) after analysis of a batch of 32 sample entries or conducting the experiment at a low GC column temperature (22.5 degrees C). The effects of water contamination on long-term reproducibility of reference water, with and without baking protocol, have been described.

Tuning DNA-amphiphile condensate architecture with strongly binding counterions

Electrostatic self-assembly of colloidal and nanoparticles has attracted a lot of attention in recent years, since it offers the possibility of producing novel crystalline structures that have the potential to be used as advanced materials for photonic and other applications. The stoichiometry of these crystals is not constrained by charge neutrality of the two types of particles due to the presence of counterions, and hence a variety of three-dimensional structures have been observed depending on the relative sizes of the particles and their charge. Here we report structural polymorphism of two-dimensional crystals of oppositely charged linear macroions, namely DNA and self-assembled cylindrical micelles of cationic amphiphiles. Our system differs from those studied earlier in terms of the presence of a strongly binding counterion that competes with DNA to bind to the micelle. The presence of these counterions leads to novel structures of these crystals, such as a square lattice and a root 3 x root 3 superlattice of an underlying hexagonal lattice, determined from a detailed analysis of the small-angle diffraction data. These lower-dimensional equilibrium systems can play an important role in developing a deeper theoretical understanding of the stability of crystals of oppositely charged particles. Further, it should be possible to use the same design principles to fabricate structures on a longer length-scale by an appropriate choice of the two macroions.

Probing strongly interacting W's at the ILC with polarized beams

We study the possibility of finger printing a strongly interacting W boson sector which is consistent with present day LHC searches at the ILC with longitudinal as well as transversely polarized electron and positron beams. We account for the final state interaction using a suitable Omnes formalism in terms of a plausible resonance description, and carry out thorough analyses of cross sections, asymmetries and angular distributions of the W's. We carry out a comparison with other extensions of the Standard Model, where heavy additional Z' bosons arise naturally. We also consider the effect of the strong final state interaction on a correlation that depends on (phi(-) -phi(+)),where the phi-(+) are the azimuthal angles of decay leptons, and find that it is a useful discriminant.

Percolation and connectivity in AB random geometric graphs

Given two independent Poisson point processes Phi((1)), Phi((2)) in R-d, the AB Poisson Boolean model is the graph with the points of Phi((1)) as vertices and with edges between any pair of points for which the intersection of balls of radius 2r centered at these points contains at least one point of Phi((2)). This is a generalization of the AB percolation model on discrete lattices. We show the existence of percolation for all d >= 2 and derive bounds fora critical intensity. We also provide a characterization for this critical intensity when d = 2. To study the connectivity problem, we consider independent Poisson point processes of intensities n and tau n in the unit cube. The AB random geometric graph is defined as above but with balls of radius r. We derive a weak law result for the largest nearest-neighbor distance and almost-sure asymptotic bounds for the connectivity threshold.

Tight co-degree condition for perfect matchings in 4-graphs

We will give a tight minimum co-degree condition for a 4-uniform hypergraph to contain a perfect matching.

Strongly magnetized cold degenerate electron gas: Mass-radius relation of the magnetized white dwarf

We consider a relativistic, degenerate electron gas at zero temperature under the influence of a strong, uniform, static magnetic field, neglecting any form of interactions. Since the density of states for the electrons changes due to the presence of the magnetic field (which gives rise to Landau quantization), the corresponding equation of state also gets modified. In order to investigate the effect of very strong magnetic field, we focus only on systems in which a maximum of either one, two, or three Landau level(s) is/are occupied. This is important since, if a very large number of Landau levels are filled, it implies a very low magnetic field strength which yields back Chandrasekhar's celebrated nonmagnetic results. The maximum number of occupied Landau levels is fixed by the correct choice of two parameters, namely, the magnetic field strength and the maximum Fermi energy of the system. We study the equations of state of these one-level, two-level, and three-level systems and compare them by taking three different maximum Fermi energies. We also find the effect of the strong magnetic field on the mass-radius relation of the underlying star composed of the gas stated above. We obtain an exciting result that it is possible to have an electron-degenerate static star, namely, magnetized white dwarfs, with a mass significantly greater than the Chandrasekhar limit in the range 2.3-2.6M(circle dot), provided it has an appropriate magnetic field strength and central density. In fact, recent observations of peculiar type Ia supernovae-SN 2006gz, SN 2007if, SN 2009dc, SN 2003fg-seem to suggest super-Chandrasekhar-mass white dwarfs with masses up to 2.4-2.8M(circle dot) as their most likely progenitors. Interestingly, our results seem to lie within these observational limits.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

Unconventional metallicity and giant thermopower in a strongly interacting two-dimensional electron system

We present thermal and electrical transport measurements of low-density (10(14) m(-2)), mesoscopic two-dimensional electron systems (2DESs) in GaAs/AlGaAs heterostructures at sub-Kelvin temperatures. We find that even in the supposedly strongly localized regime, where the electrical resistivity of the system is two orders of magnitude greater than the quantum of resistance h/e(2), the thermopower decreases linearly with temperature indicating metallicity. Remarkably, the magnitude of the thermopower exceeds the predicted value in noninteracting metallic 2DESs at similar carrier densities by over two orders of magnitude. Our results indicate a new quantum state and possibly a novel class of itinerant quasiparticles in dilute 2DESs at low temperatures where the Coulomb interaction plays a pivotal role.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.

Molecular probe dynamics reveals suppression of ice-like regions in strongly confined supercooled water

The structure of the hydrogen bond network is a key element for understanding water's thermodynamic and kinetic anomalies. While ambient water is strongly believed to be a uniform, continuous hydrogen-bonded liquid, there is growing consensus that supercooled water is better described in terms of distinct domains with either a low-density ice-like structure or a high-density disordered one. We evidenced two distinct rotational mobilities of probe molecules in interstitial supercooled water of polycrystalline ice Banerjee D, et al. (2009) ESR evidence for 2 coexisting liquid phases in deeply supercooled bulk water. Proc Natl Acad Sci USA 106: 11448-11453]. Here we show that, by increasing the confinement of interstitial water, the mobility of probe molecules, surprisingly, increases. We argue that loose confinement allows the presence of ice-like regions in supercooled water, whereas a tighter confinement yields the suppression of this ordered fraction and leads to higher fluidity. Compelling evidence of the presence of ice-like regions is provided by the probe orientational entropy barrier which is set, through hydrogen bonding, by the configuration of the surrounding water molecules and yields a direct measure of the configurational entropy of the same. We find that, under loose confinement of supercooled water, the entropy barrier surmounted by the slower probe fraction exceeds that of equilibrium water by the melting entropy of ice, whereas no increase of the barrier is observed under stronger confinement. The lower limit of metastability of supercooled water is discussed.