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.

Multi-agent Reinforcement Learning for Traffic Signal Control

Optimal control of traffic lights at junctions or traffic signal control (TSC) is essential for reducing the average delay experienced by the road users amidst the rapid increase in the usage of vehicles. In this paper, we formulate the TSC problem as a discounted cost Markov decision process (MDP) and apply multi-agent reinforcement learning (MARL) algorithms to obtain dynamic TSC policies. We model each traffic signal junction as an independent agent. An agent decides the signal duration of its phases in a round-robin (RR) manner using multi-agent Q-learning with either is an element of-greedy or UCB 3] based exploration strategies. It updates its Q-factors based on the cost feedback signal received from its neighbouring agents. This feedback signal can be easily constructed and is shown to be effective in minimizing the average delay of the vehicles in the network. We show through simulations over VISSIM that our algorithms perform significantly better than both the standard fixed signal timing (FST) algorithm and the saturation balancing (SAT) algorithm 15] over two real road networks.

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 .

Vacancy mediated clipping of multi-layered graphene: A precursor for 1, 2 and 3D carbon structures

Using first principles calculations, we show that the overlapping defects in bi-layer graphene (both AA-and AB-stacked) interact forming inter-layer covalent bonds, giving rise to two-dimensional (2D) clipped structures, without explicit use of functional groups. These clipped structures can be transformed into one-dimensional (1D) double wall nanotubes (DWCNT) or multi-layered three dimensional (3D) bulk structures. These clipped structures show good mechanical strength due to covalent bonding between multi-layers. Clipping also provides a unique way to simultaneously harness the conductivity of both walls of a double wall nanotube through covalently bonded scattering junctions. With additional conducting channels and improved mechanical stability, these clipped structures can lead to a myriad of applications in novel devices. (C) 2015 Elsevier Ltd. All rights reserved.

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.

The Structure of the Holo-Acyl Carrier Protein of Leishmania major Displays a Remarkably Different Phosphopantetheinyl Transferase Binding Interface

The genome of Leishmania major encodes a type II fatty acid biosynthesis pathway for which no structural or biochemical information exists. Here, for the first time, we have characterized the central player of the pathway, the acyl carrier protein (LmACP), using nuclear magnetic resonance (NMR). Structurally, the LmACP molecule is similar to other type II ACPs, comprising a four-helix bundle, enclosing a hydrophobic core. Dissimilarities in sequence, however, exist in helix II (recognition helix) of the protein. The enzymatic conversion of apo-LmACP into the holo form using type I (Escherichia coli AcpS) and type II (Sfp type) phosphopantetheinyl transferases (PPTs) is relatively slow. Mutagenesis studies underscore the importance of the residues present at the protein protein interaction interface of LmACP in modulating the activity of PPTs. Interestingly, the cognate PPT for this ACP, the L. major 4'-phosphopantetheinyl transferase (LmPPT), does not show any enzymatic activity toward it, though it readily converts other type I and type II ACPs into their holo forms. NMR chemical shift perturbation studies suggest a moderately tight complex between LmACP and its cognate PPT, suggesting inhibition. We surmise that the unique surface of LmACP might have evolved to complement its cognate enzyme (LmPPT), possibly for the purpose of regulation.

Structural characterization of a mitochondrial 3-ketoacyl-CoA (T1)-like thiolase from Mycobacterium smegmatis

Thiolases catalyze the degradation and synthesis of 3-ketoacyl-CoA molecules. Here, the crystal structures of a T1-like thiolase (MSM-13 thiolase) from Mycobacterium smegmatis in apo and liganded forms are described. Systematic comparisons of six crystallographically independent unliganded MSM-13 thiolase tetramers (dimers of tight dimers) from three different crystal forms revealed that the two tight dimers are connected to a rigid tetramerization domain via flexible hinge regions, generating an asymmetric tetramer. In the liganded structure, CoA is bound to those subunits that are rotated towards the tip of the tetramerization loop of the opposing dimer, suggesting that this loop is important for substrate binding. The hinge regions responsible for this rotation occur near Val123 and Arg149. The L alpha 1-covering loop-L alpha 2 region, together with the N beta 2-N alpha 2 loop of the adjacent subunit, defines a specificity pocket that is larger and more polar than those of other tetrameric thiolases, suggesting that MSM-13 thiolase has a distinct substrate specificity. Consistent with this finding, only residual activity was detected with acetoacetyl-CoA as the substrate in the degradative direction. No activity was observed with acetyl-CoA in the synthetic direction. Structural comparisons with other well characterized thiolases suggest that MSM-13 thiolase is probably a degradative thiolase that is specific for 3-ketoacyl-CoA molecules with polar, bulky acyl chains.

Baryon squishing in synthetic dimensions by effective SU(M) gauge fields

The ``synthetic dimension'' proposal A. Celi et al., Phys. Rev. Lett. 112, 043001 (2014)] uses atoms with M internal states (''flavors'') in a one-dimensional (1D) optical lattice, to realize a hopping Hamiltonian equivalent to the Hofstadter model (tight-binding model with a given magnetic flux per plaquette) on an M-sites-wide square lattice strip. We investigate the physics of SU(M) symmetric interactions in the synthetic dimension system. We show that this system is equivalent to particles with SU(M) symmetric interactions] experiencing an SU(M) Zeeman field at each lattice site and a non-Abelian SU(M) gauge potential that affects their hopping. This equivalence brings out the possibility of generating nonlocal interactions between particles at different sites of the optical lattice. In addition, the gauge field induces a flavor-orbital coupling, which mitigates the ``baryon breaking'' effect of the Zeeman field. For M particles, concomitantly, the SU(M) singlet baryon which is site localized in the usual 1D optical lattice, is deformed to a nonlocal object (''squished baryon''). We conclusively demonstrate this effect by analytical arguments and exact (numerical) diagonalization studies. Our study promises a rich many-body phase diagram for this system. It also uncovers the possibility of using the synthetic dimension system to laboratory realize condensed-matter models such as the SU(M) random flux model, inconceivable in conventional experimental systems.

Intrinsic large gap quantum anomalous Hall insulators in LaX (X = Br,Cl,I)

We report a theoretical prediction of a new class of bulk and intrinsic quantum anomalous Hall (QAH) insulators LaX (X=Br, Cl, and I) via relativistic first-principles calculations. We find that these systems are innate long-ranged ferromagnets which, with the help of intrinsic spin-orbit coupling, become QAH insulators. A low-energy multiband tight-binding model is developed to understand the origin of the QAH effect. Finally, integer Chern number is obtained via Berry phase computation for each two-dimensional plane. These materials have the added benefit of a sizable band gap of as large as similar to 25 meV, with the flexibility of enhancing it to above 75 meV via strain engineering. The synthesis of LaX materials will provide the impurity-free single crystals and thin-film QAH insulators for versatile experiments and functionalities.

A unique uracil-DNA binding protein of the uracil DNA glycosylase superfamily

Uracil DNA glycosylases (UDGs) are an important group of DNA repair enzymes, which pioneer the base excision repair pathway by recognizing and excising uracil from DNA. Based on two short conserved sequences (motifs A and B), UDGs have been classified into six families. Here we report a novel UDG, UdgX, from Mycobacterium smegmatis and other organisms. UdgX specifically recognizes uracil in DNA, forms a tight complex stable to sodium dodecyl sulphate, 2-mercaptoethanol, urea and heat treatment, and shows no detectable uracil excision. UdgX shares highest homology to family 4 UDGs possessing Fe-S cluster. UdgX possesses a conserved sequence, KRRIH, which forms a flexible loop playing an important role in its activity. Mutations of H in the KRRIH sequence to S, G, A or Q lead to gain of uracil excision activity in MsmUdgX, establishing it as a novel member of the UDG superfamily. Our observations suggest that UdgX marks the uracil-DNA for its repair by a RecA dependent process. Finally, we observed that the tight binding activity of UdgX is useful in detecting uracils in the genomes.