Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

Molecular Dissection of Mycobacterium tuberculosis Integration Host Factor Reveals Novel Insights into the Mode of DNA Binding and Nucleoid Compaction

Background: mIHF belongs to a subfamily of proteins, distinct from E. coli IHF. Results: Functionally important amino acids of mIHF and the mechanism(s) underlying DNA binding, DNA bending, and site-specific recombination are distinct from that of E. coli IHF. Conclusion: mIHF functions could contribute beyond nucleoid compaction. Significance: Because mIHF is essential for growth, the molecular mechanisms identified here can be exploited in drug screening efforts. The annotated whole-genome sequence of Mycobacterium tuberculosis revealed that Rv1388 (Mtihf) is likely to encode for a putative 20-kDa integration host factor (mIHF). However, very little is known about the functional properties of mIHF or the organization of the mycobacterial nucleoid. Molecular modeling of the mIHF three-dimensional structure, based on the cocrystal structure of Streptomyces coelicolor IHF duplex DNA, a bona fide relative of mIHF, revealed the presence of Arg-170, Arg-171, and Arg-173, which might be involved in DNA binding, and a conserved proline (Pro-150) in the tight turn. The phenotypic sensitivity of Escherichia coli ihfA and ihfB strains to UV and methyl methanesulfonate could be complemented with the wild-type Mtihf but not its alleles bearing mutations in the DNA-binding residues. Protein-DNA interaction assays revealed that wild-type mIHF, but not its DNA-binding variants, binds with high affinity to fragments containing attB and attP sites and curved DNA. Strikingly, the functionally important amino acid residues of mIHF and the mechanism(s) underlying its binding to DNA, DNA bending, and site-specific recombination are fundamentally different from that of E. coli IHF. Furthermore, we reveal novel insights into IHF-mediated DNA compaction depending on the placement of its preferred binding sites; mIHF promotes DNA compaction into nucleoid-like or higher order filamentous structures. We therefore propose that mIHF is a distinct member of a subfamily of proteins that serve as essential cofactors in site-specific recombination and nucleoid organization and that these findings represent a significant advance in our understanding of the role(s) of nucleoid-associated proteins.

Effect of Line Defects on the Electrical Transport Properties of Monolayer MoS2 Sheet

We present a computational study on the impact of line defects on the electronic properties of monolayer MoS2. Four different kinds of line defects with Mo and S as the bridging atoms, consistent with recent theoretical and experimental observations, are considered herein. We employ the density functional tight-binding (DFTB) method with a Slater-Koster-type DFTB-CP2K basis set for evaluating the material properties of perfect and the various defective MoS2 sheets. The transmission spectra are computed with a DFTB-non-equilibrium Green's function formalism. We also perform a detailed analysis of the carrier transmission pathways under a small bias and investigate the phase of the transmission eigenstates of the defective MoS2 sheets. Our simulations show a two to four fold decrease in carrier conductance of MoS2 sheets in the presence of line defects as compared to that for the perfect sheet.

Influence of initial degree of saturation on swell pressures of compacted Barmer bentonite specimens

Densely compacted bentonite or bentonite-sand mixture has been identified as suitable buffer in deep geological repositories as its exceptionally high swelling capacity enables tight contact between the waste canister and surrounding rock. The degree of saturation of the compacted bentonite buffer can increase upon ingress of groundwater from the surrounding rock mass or decrease from evaporation due to high temperature (50-210 degrees C) derived from the waste canister. Available studies indicate that the influence of initial moisture content or degree of saturation on the swell pressure or swell potential of compacted bentonites is unclear. Some studies suggest that initial degree of saturation has an influence, while others suggest that it does not have bearing on the swell pressure of compacted bentonites. This paper examines the influence of initial degree of saturation in montmorillonite voids (termed,S-r,S-MF) on swell pressure of compacted Barmer bentonite-sand mixtures (dry density range: 1.4-2 Mg/m(3)) from micro-structural considerations. The experimental results bring out that, constant dry density specimens that developed similar number of hydration layers upon wetting developed comparable swell pressures and were unaffected by variations in initial S-r,S-MF values. Comparatively, constant dry density specimens that developed dis-similar number of hydration layers upon wetting established different swell pressures and were responsive to variations in initial S-r,S-MF. (C) 2015 Elsevier Ltd. All rights reserved.

Strongly minimal triangulations of (S (3) x S (1))(#3) and (S (3) x S (1))(#3)

A triangulated d-manifold K, satisfies the inequality for da parts per thousand yen3. The triangulated d-manifolds that meet the bound with equality are called tight neighbourly. In this paper, we present tight neighbourly triangulations of 4-manifolds on 15 vertices with as an automorphism group. One such example was constructed by Bagchi and Datta (Discrete Math. 311 (citeyearbd102011) 986-995). We show that there are exactly 12 such triangulations up to isomorphism, 10 of which are orientable.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

Maximum group velocity in a one-dimensional model with a sinusoidally varying staggered potential

We use Floquet theory to study the maximum value of the stroboscopic group velocity in a one-dimensional tight-binding model subjected to an on-site staggered potential varying sinusoidally in time. The results obtained by numerically diagonalizing the Floquet operator are analyzed using a variety of analytical schemes. In the low-frequency limit we use adiabatic theory, while in the high-frequency limit the Magnus expansion of the Floquet Hamiltonian turns out to be appropriate. When the magnitude of the staggered potential is much greater or much less than the hopping, we use degenerate Floquet perturbation theory; we find that dynamical localization occurs in the former case when the maximum group velocity vanishes. Finally, starting from an ``engineered'' initial state where the particles (taken to be hard-core bosons) are localized in one part of the chain, we demonstrate that the existence of a maximum stroboscopic group velocity manifests in a light-cone-like spreading of the particles in real space.

Detection of a quantum particle on a lattice under repeated projective measurements

We consider a quantum particle, moving on a lattice with a tight-binding Hamiltonian, which is subjected to measurements to detect its arrival at a particular chosen set of sites. The projective measurements are made at regular time intervals tau, and we consider the evolution of the wave function until the time a detection occurs. We study the probabilities of its first detection at some time and, conversely, the probability of it not being detected (i.e., surviving) up to that time. We propose a general perturbative approach for understanding the dynamics which maps the evolution operator, which consists of unitary transformations followed by projections, to one described by a non-Hermitian Hamiltonian. For some examples of a particle moving on one-and two-dimensional lattices with one or more detection sites, we use this approach to find exact expressions for the survival probability and find excellent agreement with direct numerical results. A mean-field model with hopping between all pairs of sites and detection at one site is solved exactly. For the one-and two-dimensional systems, the survival probability is shown to have a power-law decay with time, where the power depends on the initial position of the particle. Finally, we show an interesting and nontrivial connection between the dynamics of the particle in our model and the evolution of a particle under a non-Hermitian Hamiltonian with a large absorbing potential at some sites.

Molecular Dissection of Mycobacterium tuberculosis Integration Host Factor Reveals Novel Insights into the Mode of DNA Binding and Nucleoid Compaction

The annotated whole-genome sequence of Mycobacterium tuberculosis indicated that Rv1388 (Mtihf) likely encodes a putative 20 kDa integration host factor (mIHF). However, very little is known about the functional properties of mIHF or organization of mycobacterial nucleoid. Molecular modeling of the mIHF three-dimensional structure, based on the cocrystal structure of Streptomyces coelicolor IHF-duplex DNA, a bona fide relative of mIHF, revealed the presence of Arg170, Arg171, and Arg173, which might be involved in DNA binding, and a conserved proline (P150) in the tight turn. The phenotypic sensitivity of Escherichia coli Delta ihfA and Delta ihfB strains to UV and methylmethanesulfonate could be complemented with the wild-type Mtihf, but not its alleles bearing mutations in the DNA-binding residues. Protein DNA interaction assays revealed that wild-type mIHF, but not its DNA-binding variants, bind with high affinity to fragments containing attB and attP sites and curved DNA. Strikingly, the functionally important amino acid residues of mIHF and the mechanism(s) underlying its binding to DNA, DNA bending, and site-specific recombination are fundamentally different from that of E. coli IHF alpha beta. Furthermore, we reveal novel insights into IHF-mediated DNA compaction depending on the placement of its preferred binding sites; mIHF promotes compaction of DNA into nucleoid-like or higher-order filamentous structures. We hence propose that mIHF is a distinct member of a subfamily of proteins that serve as essential cofactors in site-specific recombination and nucleoid organization and that these findings represent a significant advance in our understanding of the role(s) of nucleoid-associated proteins.

Generalized Spatial Modulation in Large-Scale Multiuser MIMO Systems

Generalized spatial modulation (GSM) uses n(t) transmit antenna elements but fewer transmit radio frequency (RF) chains, n(rf). Spatial modulation (SM) and spatial multiplexing are special cases of GSM with n(rf) = 1 and n(rf) = n(t), respectively. In GSM, in addition to conveying information bits through n(rf) conventional modulation symbols (for example, QAM), the indices of the n(rf) active transmit antennas also convey information bits. In this paper, we investigate GSM for large-scale multiuser MIMO communications on the uplink. Our contributions in this paper include: 1) an average bit error probability (ABEP) analysis for maximum-likelihood detection in multiuser GSM-MIMO on the uplink, where we derive an upper bound on the ABEP, and 2) low-complexity algorithms for GSM-MIMO signal detection and channel estimation at the base station receiver based on message passing. The analytical upper bounds on the ABEP are found to be tight at moderate to high signal-to-noise ratios (SNR). The proposed receiver algorithms are found to scale very well in complexity while achieving near-optimal performance in large dimensions. Simulation results show that, for the same spectral efficiency, multiuser GSM-MIMO can outperform multiuser SM-MIMO as well as conventional multiuser MIMO, by about 2 to 9 dB at a bit error rate of 10(-3). Such SNR gains in GSM-MIMO compared to SM-MIMO and conventional MIMO can be attributed to the fact that, because of a larger number of spatial index bits, GSM-MIMO can use a lower-order QAM alphabet which is more power efficient.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Separation index of graphs and stacked 2-spheres

In 1987, Kalai proved that stacked spheres of dimension d >= 3 are characterised by the fact that they attain equality in Barnette's celebrated Lower Bound Theorem. This result does not extend to dimension d = 2. In this article, we give a characterisation of stacked 2-spheres using what we call the separation index. Namely, we show that the separation index of a triangulated 2-sphere is maximal if and only if it is stacked. In addition, we prove that, amongst all n-vertex triangulated 2-spheres, the separation index is minimised by some n-vertex flag sphere for n >= 6. Furthermore, we apply this characterisation of stacked 2-spheres to settle the outstanding 3-dimensional case of the Lutz-Sulanke-Swartz conjecture that ``tight-neighbourly triangulated manifolds are tight''. For dimension d >= 4, the conjecture has already been proved by Effenberger following a result of Novik and Swartz. (C) 2015 Elsevier Inc. All rights reserved.