Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Artemisinin-based combination with curcumin adds a new dimension to malaria therapy

Malaria afflicts 300 million people worldwide, with over a million deaths every year. With no immediate prospect of a vaccine against the disease, drugs are the only choice to treat it. Unfortunately, the parasite has become resistant to most antimalarials, restricting the option to use artemisinins (ARTs) for effective cure. With the use of ARTs as the front-line antimalarials, reports are already available on the possible resistance development to these drugs as well. Therefore, it has become necessary to use ART-based combination therapies to delay emergence of resistance. It is also necessary to discover new pharmacophores to eventually replace ART. Studies in our laboratory have shown that curcumin not only synergizes with ART as an antimalarial to kill the parasite, but is also uniquely able to prime the immune system to protect against parasite recrudescence in the animal model. The results indicate a potential for the use of ART curcumin combination against recrudescence/relapse in falciparum and vivax malaria. In addition, studies have also suggested the use of curcumin as an adjunct therapy against cerebral malaria. In this review we have attempted to highlight these aspects as well as the studies directed to discover new pharmacophores as potential replacements for ART.

Synthesis and an Evaluation of Molecular Conformation and Crystal Packing in Two Substituted 4-Phenylquinolines

The title compounds, namely Methyl 2-methyl-4 -phenylquinoline-3-carboxylate (I), C18H15NO2, and (2E)-3-(3,4-dimethoxyphenyl)-1-(2-methyl-4 -phenylquinolin-3-yl)prop-2-en-1-one (II), C27H23NO3, comprising of the phenyl ring, exhibit differences in conformational behaviour with respect to the plane of the quinoline fragment. (I) contains the methyl ester moiety whereas (II) contains the chalcone fragment, consisting of a double bond and phenyl group containing dimethoxy groups as substituents. The dihedral angles between the phenyl group and the quinoline ring is 82.77 (7)A degrees in (I), and 79.02 (8)A degrees in (II) respectively. It is the weak C-H center dot center dot center dot O=C H-bond and C-H center dot center dot center dot pi interactions which dictate packing of molecules in (I). In (II), it is C-H center dot center dot center dot N and C-H center dot center dot center dot pi, involving the dimethoxy ring, which controls packing of molecules in the crystal lattice. In addition, pi center dot center dot center dot pi aromatic stacking interactions involving the quinoline fragment is present in all the molecules. The title compounds, namely methyl-2-methyl-4 -phenylquinoline-3-carboxylate (I), C18H15NO2, and (2E)-3-(3,4-dimethoxyphenyl)-1-(2-methyl-4 -phenylquinolin-3-yl)prop-2-en-1-one (II), C27H23NO3, comprising of the phenyl ring, exhibit differences in conformational behaviour with respect to the plane of the quinoline fragment. (I) contains the methyl ester moiety whereas (III) contains the chalcone fragment, consisting of a double bond and phenyl group containing dimethoxy groups as substituents. The dihedral angles between the phenyl group and the quinoline ring is 82.77 (7)A degrees in (I), and 79.02 (8)A degrees in (II) respectively. It is the weak C-H center dot center dot center dot O=C H-bond and C-H center dot center dot center dot pi interactions which dictate packing of molecules in (I). In (II), it is C-H center dot center dot center dot N and C-H center dot center dot center dot pi, involving the dimethoxy ring, which controls packing of molecules in the crystal lattice. In addition, pi center dot center dot center dot pi aromatic stacking interactions involving the quinoline fragment is present in all the molecules.

Estimating the Hausdorff-Besicovitch dimension of boundary of basin of attraction in helicopter trim

Helicopter trim involves solution of nonlinear force equilibrium equations. As in many nonlinear dynamic systems, helicopter trim problem can show chaotic behavior. This chaotic behavior is found in the basin of attraction of the nonlinear trim equations which have to be solved to determine the main rotor control inputs given by the pilot. This study focuses on the boundary of the basin of attraction obtained for a set of control inputs. We analyze the boundary by considering it at different magnification levels. The magnified views reveal intricate geometries. It is also found that the basin boundary exhibits the characteristic of statistical self-similarity, which is an essential property of fractal geometries. These results led the authors to investigate the fractal dimension of the basin boundary. It is found that this dimension is indeed greater than the topological dimension. From all the observations, it is evident that the boundary of the basin of attraction for helicopter trim problem is fractal in nature. (C) 2012 Elsevier Inc. All rights reserved.

Multiuser detection in large-dimension multicode MIMO-CDMA systems with higher-order modulation

In this paper, we are interested in high spectral efficiency multicode CDMA systems with large number of users employing single/multiple transmit antennas and higher-order modulation. In particular, we consider a local neighborhood search based multiuser detection algorithm which offers very good performance and complexity, suited for systems with large number of users employing M-QAM/M-PSK. We apply the algorithm on the chip matched filter output vector. We demonstrate near-single user (SU) performance of the algorithm in CDMA systems with large number of users using 4-QAM/16-QAM/64-QAM/8-PSK on AWGN, frequency-flat, and frequency-selective fading channels. We further show that the algorithm performs very well in multicode multiple-input multiple-output (MIMO) CDMA systems as well, outperforming other linear detectors and interference cancelers reported in the literature for such systems. The per-symbol complexity of the search algorithm is O(K2n2tn2cM), K: number of users, nt: number of transmit antennas at each user, nc: number of spreading codes multiplexed on each transmit antenna, M: modulation alphabet size, making the algorithm attractive for multiuser detection in large-dimension multicode MIMO-CDMA systems with M-QAM.

Packing in molten globules and native states

Close packing of hydrophobic residues in the protein interior is an important determinant of protein stability. Cavities introduced by large to small substitutions are known to destabilize proteins. Conversely, native states of proteins and protein fragments can be stabilized by filling in existing cavities. Molten globules (MGs) were initially used to describe a state of protein which has well-defined secondary structure but little or no tertiary packing. Subsequent studies have shown that MGs do have some degree of native-like topology and specific packing. Wet molten globules (WMGs) with hydrated cores and considerably decreased packing relative to the native state have been studied extensively. Recently there has been renewed interest in identification and characterization of dry molten globules (DMGs). These are slightly expanded forms of the native state which show increased conformational flexibility, native-like main-chain hydrogen bonding and dry interiors. The generality of occurrence of DMGs during protein unfolding and the extent and nature of packing in DMGs remain to be elucidated. Packing interactions in native proteins and MGs can be probed through mutations. Next generation sequencing technologies make it possible to determine relative populations of mutants in a large pool. When this is coupled to phenotypic screens or cell-surface display, it becomes possible to rapidly examine large panels of single-site or multi-site mutants. From such studies, residue specific contributions to protein stability and function can be estimated in a highly parallelized fashion. This complements conventional biophysical methods for characterization of packing in native states and molten globules.

On Selection of Search Space Dimension in Compressive Sampling Matching Pursuit

Compressive Sampling Matching Pursuit (CoSaMP) is one of the popular greedy methods in the emerging field of Compressed Sensing (CS). In addition to the appealing empirical performance, CoSaMP has also splendid theoretical guarantees for convergence. In this paper, we propose a modification in CoSaMP to adaptively choose the dimension of search space in each iteration, using a threshold based approach. Using Monte Carlo simulations, we show that this modification improves the reconstruction capability of the CoSaMP algorithm in clean as well as noisy measurement cases. From empirical observations, we also propose an optimum value for the threshold to use in applications.

Analysis of designed beta-hairpin peptides: molecular conformation and packing in crystals

The crystal structures of several designed peptide hairpins have been determined in order to establish features of molecular conformations and modes of aggregation in the crystals. Hairpin formation has been induced using a centrally positioned (D)Pro-Xxx segment (Xxx = (L)Pro, Aib, Ac(6)c, Ala; Aib = alpha-aminoisobutyric acid; Ac(6)c = 1-aminocyclohexane-1-carboxylic acid). Structures of the peptides Boc-Leu-Phe-Val-(D)Pro-(L)Pro-Leu-Phe-Val-OMe (1), Boc-Leu-Tyr-Val-(D)Pro-(L)Pro-Leu-Phe-Val-OMe (2, polymorphic forms labeled as 2a and 2b), Boc-Leu-Val-Val-(D)Pro-(L)Pro-Leu-Val-Val-OMe (3), Boc-Leu-Phe-Val-(D)Pro-Aib-Leu-Phe-Val-OMe (4, polymorphic forms labeled as 4a and 4b), Boc-Leu-Phe-Val-(D)Pro-Ac(6)c-Leu-Phe-Val-OMe (5) and Boc-Leu-Phe-Val-(D)Pro-Ala-Leu-Phe-Val-OMe (6) are described. All the octapeptides adopt type II' beta-turn nucleated hairpins, stabilized by three or four cross-strand intramolecular hydrogen bonds. The angle of twist between the two antiparallel strands lies in the range of -9.8 degrees to -26.7 degrees. A detailed analysis of packing motifs in peptide hairpin crystals is presented, revealing three broad modes of association: parallel packing, antiparallel packing and orthogonal packing. An attempt to correlate aggregation modes in solution with observed packing motifs in crystals has been made by indexing of crystal faces in the case of three of the peptide hairpins. The observed modes of hairpin aggregation may be of relevance in modeling multiple modes of association, which may provide insights into the structure of insoluble polypeptide aggregates.

On the SIG-dimension of trees under the L (a)-metric

Let where be a set of points in d-dimensional space with a given metric rho. For a point let r (p) be the distance of p with respect to rho from its nearest neighbor in Let B(p,r (p) ) be the open ball with respect to rho centered at p and having the radius r (p) . We define the sphere-of-influence graph (SIG) of as the intersection graph of the family of sets Given a graph G, a set of points in d-dimensional space with the metric rho is called a d-dimensional SIG-representation of G, if G is isomorphic to the SIG of It is known that the absence of isolated vertices is a necessary and sufficient condition for a graph to have a SIG-representation under the L (a)-metric in some space of finite dimension. The SIG-dimension under the L (a)-metric of a graph G without isolated vertices is defined to be the minimum positive integer d such that G has a d-dimensional SIG-representation under the L (a)-metric. It is denoted by SIG (a)(G). We study the SIG-dimension of trees under the L (a)-metric and almost completely answer an open problem posed by Michael and Quint (Discrete Appl Math 127:447-460, 2003). Let T be a tree with at least two vertices. For each let leaf-degree(v) denote the number of neighbors of v that are leaves. We define the maximum leaf-degree as leaf-degree(x). Let leaf-degree{(v) = alpha}. If |S| = 1, we define beta(T) = alpha(T) - 1. Otherwise define beta(T) = alpha(T). We show that for a tree where beta = beta (T), provided beta is not of the form 2 (k) - 1, for some positive integer k a parts per thousand yen 1. If beta = 2 (k) - 1, then We show that both values are possible.

Product Dimension of Forests and Bounded Treewidth Graphs

The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has product dimension at most 1.441 log n + 3. This improves the best known upper bound of 3 log n for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on n vertices with treewidth at most t has product dimension at most (t + 2) (log n + 1). We also show that every k-degenerate graph on n vertices has product dimension at most inverted right perpendicular5.545 k log ninverted left perpendicular + 1. This improves the upper bound of 32 k log n for the same by Eaton and Rodl.

Classification calibration dimension for general multiclass losses

We study consistency properties of surrogate loss functions for general multiclass classification problems, defined by a general loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning problems), to the general multiclass setting, and derive necessary and sufficient conditions for a surrogate loss to be classification calibrated with respect to a loss matrix in this setting. We then introduce the notion of \emph{classification calibration dimension} of a multiclass loss matrix, which measures the smallest `size' of a prediction space for which it is possible to design a convex surrogate that is classification calibrated with respect to the loss matrix. We derive both upper and lower bounds on this quantity, and use these results to analyze various loss matrices. In particular, as one application, we provide a different route from the recent result of Duchi et al.\ (2010) for analyzing the difficulty of designing `low-dimensional' convex surrogates that are consistent with respect to pairwise subset ranking losses. We anticipate the classification calibration dimension may prove to be a useful tool in the study and design of surrogate losses for general multiclass learning problems.

Cooperative Particle Swarm Optimization Based Receiver for Large-Dimension MIMO-ZPSC Systems

In this paper, we propose a cooperative particle swarm optimization (CPSO) based channel estimation/equalization scheme for multiple-input multiple-output zero-padded single-carrier (MIMO-ZPSC) systems with large dimensions in frequency selective channels. We estimate the channel state information at the receiver in time domain using a PSO based algorithm during training phase. Using the estimated channel, we perform information symbol detection in the frequency domain using FFT based processing. For this detection, we use a low complexity OLA (OverLap Add) likelihood ascent search equalizer which uses minimum mean square (MMSE) equalizer solution as the initial solution. Multiple iterations between channel estimation and data detection are carried out which significantly improves the mean square error and bit error rate performance of the receiver.

Fractal dimension method for delamination detection in composite beams

A new delaminated composite beam element is formulated for Timoshenko as well as Euler-Bernoulli beam models. Shape functions are derived from Timoshenko functions; this provides a unified formulation for slender to moderately deep beam analyses. The element is simple and easy to implement, results are on par with those from free mode delamination models. Katz fractal dimension method is applied on the mode shapes obtained from finite element models, to detect the delamination in the beam. The effect of finite element size on fractal dimension method of delamination detection is quantified.

Mud-packing frog: A novel breeding behaviour and parental care in a stream dwelling new species of Nyctibatrachus (Amphibia, Anura, Nyctibatrachidae)

Reproductive modes are diverse and unique in anurans. Selective pressures of evolution, ecology and environment are attributed to such diverse reproductive modes. Globally forty different reproductive modes in anurans have been described to date. The genus Nyctibatrachus has been recently revised and belongs to an ancient lineage of frog families in the Western Ghats of India. Species of this genus are known to exhibit mountain associated clade endemism and novel breeding behaviours. The purpose of this study is to present unique reproductive behaviour, oviposition and parental care in a new species Nyctibatrachus kumbara sp. nov. which is described in the paper. Nyctibatrachus kumbara sp. nov. is a medium sized stream dwelling frog. It is distinct from the congeners based on a suite of morphological characters and substantially divergent in DNA sequences of the mitochondrial 16S rRNA gene. Males exhibit parental care by mud packing the egg clutch. Such parental care has so far not been described from any other frog species worldwide. Besides this, we emphasize that three co-occurring congeneric species of Nyctibatrachus, namely N. jog, N. kempholeyensis and Nyctibatrachus kumbara sp. nov. from the study site differ in breeding behaviour, which could represent a case of reproductive character displacement. These three species are distinct in their size, call pattern, reproductive behaviour, maximum number of eggs in a clutch, oviposition and parental care, which was evident from the statistical analysis. The study throws light on the reproductive behaviour of Nyctibatrachus kumbara sp. nov. and associated species to understand the evolution and adaptation of reproductive modes of anurans in general, and Nyctibatrachus in particular from the Western Ghats.

DIMENSION FREE BOUNDEDNESS OF RIESZ TRANSFORMS FOR THE GRUSHIN OPERATOR

Let G = -Delta(xi) - vertical bar xi vertical bar(2) partial derivative(2)/partial derivative eta(2) be the Grushin operator on R-n x R. We prove that the Riesz transforms associated to this operator are bounded on L-p(Rn+1), 1 < p < infinity, and their norms are independent of dimension n.