Rainbow Connection Number and Connectivity

The 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. Our main result is that rc(G) <= inverted right perpendicularn/2inverted left perpendicular for any 2-connected graph with at least three vertices. We conjecture that rc(G) <= n/kappa + C for a kappa-connected graph G of order n, where C is a constant, and prove the conjecture for certain classes of graphs. We also prove that rc(G) < (2 + epsilon)n/kappa + 23/epsilon(2) for any epsilon > 0.

Tractable theories for the synthesis of neural networks

The Radius of Direct attraction of a discrete neural network is a measure of stability of the network. it is known that Hopfield networks designed using Hebb's Rule have a radius of direct attraction of Omega(n/p) where n is the size of the input patterns and p is the number of them. This lower bound is tight if p is no larger than 4. We construct a family of such networks with radius of direct attraction Omega(n/root plog p), for any p greater than or equal to 5. The techniques used to prove the result led us to the first polynomial-time algorithm for designing a neural network with maximum radius of direct attraction around arbitrary input patterns. The optimal synaptic matrix is computed using the ellipsoid method of linear programming in conjunction with an efficient separation oracle. Restrictions of symmetry and non-negative diagonal entries in the synaptic matrix can be accommodated within this scheme.

Bases and Ideal Generators for Projective Monomial Curves

In this article we study bases for projective monomial curves and the relationship between the basis and the set of generators for the defining ideal of the curve. We understand this relationship best for curves in P-3 and for curves defined by an arithmetic progression. We are able to prove that the latter are set theoretic complete intersections.

Dilations of Gamma-contractions by solving operator equations

For a contraction P and a bounded commutant S of P. we seek a solution X of the operator equation S - S*P = (1 - P* P)(1/2) X (1 - P* P)(1/2) where X is a bounded operator on (Ran) over bar (1 - P* P)(1/2) with numerical radius of X being not greater than 1. A pair of bounded operators (S, P) which has the domain Gamma = {(z(1) + z(2), z(2)): vertical bar z(1)vertical bar < 1, vertical bar z(2)vertical bar <= 1} subset of C-2 as a spectral set, is called a P-contraction in the literature. We show the existence and uniqueness of solution to the operator equation above for a Gamma-contraction (S, P). This allows us to construct an explicit Gamma-isometric dilation of a Gamma-contraction (S, P). We prove the other way too, i.e., for a commuting pair (S, P) with parallel to P parallel to <= 1 and the spectral radius of S being not greater than 2, the existence of a solution to the above equation implies that (S, P) is a Gamma-contraction. We show that for a pure F-contraction (S, P), there is a bounded operator C with numerical radius not greater than 1, such that S = C + C* P. Any Gamma-isometry can be written in this form where P now is an isometry commuting with C and C. Any Gamma-unitary is of this form as well with P and C being commuting unitaries. Examples of Gamma-contractions on reproducing kernel Hilbert spaces and their Gamma-isometric dilations are discussed. (C) 2012 Elsevier Inc. All rights reserved.

Martensite-like transition and spin-glass behavior in nanocrystalline Pr0.5Ca0.5MnO3

We report on isothermal pulsed (20 ms) field magnetization, temperature dependent AC - susceptibility, and the static low magnetic field measurements carried out on 10 nm sized Pr0.5Ca0.5MnO3 nanoparticles (PCMO10). The saturation field for the magnetization of PCMO10 (similar to 250 kOe) is found to be reduced in comparison with that of bulk PCMO (similar to 300 kOe). With increasing temperature, the critical magnetic field required to `melt' the residual charge-ordered phase decays exponentially while the field transition range broadens, which is indicative of a Martensite-like transition. The AC - susceptibility data indicate the presence of a frequency-dependent freezing temperature, satisfying the conventional Vogel-Fulcher and power laws, pointing to the existence of a spin-glass-like disordered magnetic phase. The present results lead to a better understanding of manganite physics and might prove helpful for practical applications. Copyright 2011 Author(s). This article is distributed under a Creative Commons Attribution 3.0 Unported License. doi:10.1063/1.3664786]

An Online Actor-Critic Algorithm with Function Approximation for Constrained Markov Decision Processes

We develop an online actor-critic reinforcement learning algorithm with function approximation for a problem of control under inequality constraints. We consider the long-run average cost Markov decision process (MDP) framework in which both the objective and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multi-stage queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance on this setting and converges to a feasible point.

On isometries of the Kobayashi and Caratheodory metrics

This article considers C-1-smooth isometries of the Kobayashi and Caratheodory metrics on domains in C-n and the extent to which they behave like holomorphic mappings. First we provide an example which suggests that B-n cannot be mapped isometrically onto a product domain. In addition, we prove several results on continuous extension of C-0-isometries f : D-1 -> D-2 to the closures under purely local assumptions on the boundaries. As an application, we show that there is no C-0-isometry between a strongly pseudoconvex domain in C-2 and certain classes of weakly pseudoconvex finite type domains in C-2.

Parallel Computation of 3D Morse-Smale Complexes

The Morse-Smale complex is a topological structure that captures the behavior of the gradient of a scalar function on a manifold. This paper discusses scalable techniques to compute the Morse-Smale complex of scalar functions defined on large three-dimensional structured grids. Computing the Morse-Smale complex of three-dimensional domains is challenging as compared to two-dimensional domains because of the non-trivial structure introduced by the two types of saddle criticalities. We present a parallel shared-memory algorithm to compute the Morse-Smale complex based on Forman's discrete Morse theory. The algorithm achieves scalability via synergistic use of the CPU and the GPU. We first prove that the discrete gradient on the domain can be computed independently for each cell and hence can be implemented on the GPU. Second, we describe a two-step graph traversal algorithm to compute the 1-saddle-2-saddle connections efficiently and in parallel on the CPU. Simultaneously, the extremasaddle connections are computed using a tree traversal algorithm on the GPU.

PocketAnnotate: towards site-based function annotation

A computational pipeline PocketAnnotate for functional annotation of proteins at the level of binding sites has been proposed in this study. The pipeline integrates three in-house algorithms for site-based function annotation: PocketDepth, for prediction of binding sites in protein structures; PocketMatch, for rapid comparison of binding sites and PocketAlign, to obtain detailed alignment between pair of binding sites. A novel scheme has been developed to rapidly generate a database of non-redundant binding sites. For a given input protein structure, putative ligand-binding sites are identified, matched in real time against the database and the query substructure aligned with the promising hits, to obtain a set of possible ligands that the given protein could bind to. The input can be either whole protein structures or merely the substructures corresponding to possible binding sites. Structure-based function annotation at the level of binding sites thus achieved could prove very useful for cases where no obvious functional inference can be obtained based purely on sequence or fold-level analyses. An attempt has also been made to analyse proteins of no known function from Protein Data Bank. PocketAnnotate would be a valuable tool for the scientific community and contribute towards structure-based functional inference. The web server can be freely accessed at http://proline.biochem.iisc.ernet.in/pocketannotate/.

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.

Acyclic Edge Coloring of Triangle-Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G) ? ? + 2, where ? = ?(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|-1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a'(G) ? ? + 3. Triangle-free planar graphs satisfy Property A. We infer that a'(G) ? ? + 3, if G is a triangle-free planar graph. Another class of graph which satisfies Property A is 2-fold graphs (union of two forests). (C) 2011 Wiley Periodicals, Inc. J Graph Theory

Nonuniform random geometric graphs with location-dependent radii

We propose a distribution-free approach to the study of random geometric graphs. The distribution of vertices follows a Poisson point process with intensity function n f(center dot), where n is an element of N, and f is a probability density function on R-d. A vertex located at x connects via directed edges to other vertices that are within a cut-off distance r(n)(x). We prove strong law results for (i) the critical cut-off function so that almost surely, the graph does not contain any node with out-degree zero for sufficiently large n and (ii) the maximum and minimum vertex degrees. We also provide a characterization of the cut-off function for which the number of nodes with out-degree zero converges in distribution to a Poisson random variable. We illustrate this result for a class of densities with compact support that have at most polynomial rates of decay to zero. Finally, we state a sufficient condition for an enhanced version of the above graph to be almost surely connected eventually.

Network approaches to drug discovery

Introduction: Advances in genomics technologies are providing a very large amount of data on genome-wide gene expression profiles, protein molecules and their interactions with other macromolecules and metabolites. Molecular interaction networks provide a useful way to capture this complex data and comprehend it. Networks are beginning to be used in drug discovery, in many steps of the modern discovery pipeline, with large-scale molecular networks being particularly useful for the understanding of the molecular basis of the disease. Areas covered: The authors discuss network approaches used for drug target discovery and lead identification in the drug discovery pipeline. By reconstructing networks of targets, drugs and drug candidates as well as gene expression profiles under normal and disease conditions, the paper illustrates how it is possible to find relationships between different diseases, find biomarkers, explore drug repurposing and study emergence of drug resistance. Furthermore, the authors also look at networks which address particular important aspects such as off-target effects, combination-targets, mechanism of drug action and drug safety. Expert opinion: The network approach represents another paradigm shift in drug discovery science. A network approach provides a fresh perspective of understanding important proteins in the context of their cellular environments, providing a rational basis for deriving useful strategies in drug design. Besides drug target identification and inferring mechanism of action, networks enable us to address new ideas that could prove to be extremely useful for new drug discovery, such as drug repositioning, drug synergy, polypharmacology and personalized medicine.

Analysis of an Interior Penalty Method for Fourth Order Problems on Polygonal Domains

Error analysis for a stable C (0) interior penalty method is derived for general fourth order problems on polygonal domains under minimal regularity assumptions on the exact solution. We prove that this method exhibits quasi-optimal order of convergence in the discrete H (2), H (1) and L (2) norms. L (a) norm error estimates are also discussed. Theoretical results are demonstrated by numerical experiments.

A note on the inverse mode shape problem for bars, beams, and plates

Motivated by the idea of designing a structure for a desired mode shape, intended towards applications such as resonant sensors, actuators and vibration confinement, we present the inverse mode shape problem for bars, beams and plates in this work. The objective is to determine the cross-sectional profile of these structures, given a mode shape, boundary condition and the mass. The contribution of this article is twofold: (i) A numerical method to solve this problem when a valid mode shape is provided in the finite element framework for both linear and nonlinear versions of the problem. (ii) An analytical result to prove the uniqueness and existence of the solution in the case of bars. This article also highlights a very important question of the validity of a mode shape for any structure of given boundary conditions.