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.

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.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.

Dynamos driven by weak thermal convection and heterogeneous outer boundary heat flux

We use numerical dynamo models with heterogeneous core-mantle boundary (CMB) heat flux to show that lower mantle lateral thermal variability may help support a dynamo under weak thermal convection. In our reference models with homogeneous CMB heat flux, convection is either marginally supercritical or absent, always below the threshold for dynamo onset. We find that lateral CMB heat flux variations organize the flow in the core into patterns that favour the growth of an early magnetic field. Heat flux patterns symmetric about the equator produce non-reversing magnetic fields, whereas anti-symmetric patterns produce polarity reversals. Our results may explain the existence of the geodynamo prior to inner core nucleation under a tight energy budget. Furthermore, in order to sustain a strong geomagnetic field, the lower mantle thermal distribution was likely dominantly symmetric about the equator. (C) 2015 Elsevier B.V. All rights reserved.

Tunability of 1/f Noise at Multiple Dirac Cones in hBN Encapsulated Graphene Devices

The emergence of multiple Dirac cones in hexagonal boron nitride (hBN)-graphene heterostructures is particularly attractive because it offers potentially better landscape for higher and versatile transport properties than the primary Dirac cone. However, the transport coefficients of the cloned Dirac cones is yet not fully characterized and many open questions, including the evolution of charge dynamics and impurity scattering responsible for them, have remained unexplored. Noise measurements, having the potential to address these questions, have not been performed to date in dual-gated hBN graphene hBN devices. Here, we present the low frequency 1/f noise measurements at multiple Dirac cones in hBN encapsulated single and bilayer graphene in dual-gated geometry. Our results reveal that the low-frequency noise in graphene can be tuned by more than two-orders of magnitude by changing carrier concentration as well as by modifying the band structure in bilayer graphene. We find that the noise is surprisingly suppressed at the cloned Dirac cone compared to the primary Dirac cone in single layer graphene device, while it is strongly enhanced for the bilayer graphene with band gap opening. The results are explained with the calculation of dielectric function using tight-binding model. Our results also indicate that the 1/f noise indeed follows the Hooge's empirical formula in hBN-protected devices in dual-gated geometry. We also present for the first time the noise data in bipolar regime of a graphene device.

Effect of current density on the microstructure and corrosion properties of plasma electrolytic oxidation (PEO) coatings on AM50 Mg alloy produced in an electrolyte containing clay additives

Plasma electrolytic oxidation coatings were produced on AM50 Mg alloy in alkaline phosphate based electrolyte with montmorillonite clay additives employing current densities of 30, 60, and 120 mA/cm(2). The effect of current density on the microstructure and corrosion properties of the coating was investigated. The clay additives got melted and reactively incorporated into the coating forming an amorphous phase, at all the current densities. However, the coating was predominantly amorphous only at 30 mA/cm(2) and with increasing current density, increasing fractions of crystalline phases were formed. Higher current densities resulted in increased thickness of the coating, but reduced the compactness of the coatings. Electrochemical impedance spectroscopy tests in 0.5 wt.% (0.08 M) and 3.5 wt.% (0.6 M) NaCl solution revealed that the coatings processed at 30 mA/cm(2) exhibited a relatively better initial corrosion resistance owing to its relatively defect-free barrier layer and compactness of the coating. However, the presence of amorphous phases in significant amounts and lack of MgO in the coating resulted in increased rate of dissolution of the coatings and degradation of corrosion resistance. Coatings produced at higher current densities exhibited initial inferior corrosion resistance due to a more defective barrier layer and increased porosity in pore band and outer porous layer. However, the increased amount of crystalline phases and an increased amount of MgO, which resisted dissolution, counterbalanced the negative effects of defective barrier and increased porosity resulting in a relatively lower rate of the degradation of the corrosion resistance. Thus, the corrosion resistance of all the coatings continuously decreased with time and became similar after prolonged immersion in NaCl solution. Increasing current density, therefore, did not prove to be beneficial for the improvement of the corrosion performance of the PEO coatings. (C) 2016 Elsevier B.V. All rights reserved.