An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

A NEW PROOF OF OKAJI'S THEOREM FOR A CLASS OF SUM OF SQUARES OPERATORS

Let P be a linear partial differential operator with analytic coefficients. We assume that P is of the form ""sum of squares"", satisfying Hormander's bracket condition. Let q be a characteristic point; for P. We assume that q lies on a symplectic Poisson stratum of codimension two. General results of Okaji Show that P is analytic hypoelliptic at q. Hence Okaji has established the validity of Treves' conjecture in the codimension two case. Our goal here is to give a simple, self-contained proof of this fact.

DJKM ALGEBRAS I: THEIR UNIVERSAL CENTRAL EXTENSION

The purpose of this paper is to explicitly describe in terms of generators and relations the universal central extension of the infinite dimensional Lie algebra, g circle times C[t, t(-1), u vertical bar u(2) = (t(2) - b(2))(t(2) - c(2))], appearing in the work of Date, Jimbo, Kashiwara and Miwa in their study of integrable systems arising from the Landau-Lifshitz differential equation.

THE LOWER CENTRAL AND DERIVED SERIES OF THE BRAID GROUPS OF THE SPHERE

In this paper, we determine the lower central and derived series for the braid groups of the sphere. We are motivated in part by the study of Fadell-Neuwirth short exact sequences, but the problem is important in its own right. The braid groups of the 2-sphere S(2) were studied by Fadell, Van Buskirk and Gillette during the 1960s, and are of particular interest due to the fact that they have torsion elements (which were characterised by Murasugi). We first prove that for all n epsilon N, the lower central series of the n-string braid group B(n)(S(2)) is constant from the commutator subgroup onwards. We obtain a presentation of Gamma(2)(Bn(S(2))), from which we observe that Gamma(2)(B(4)(S(2))) is a semi-direct product of the quaternion group Q(8) of order 8 by a free group F(2) of rank 2. As for the derived series of Bn(S(2)), we show that for all n >= 5, it is constant from the derived subgroup onwards. The group Bn(S(2)) being finite and soluble for n <= 3, the critical case is n = 4 for which the derived subgroup is the above semi-direct product Q(8) (sic) F(2). By proving a general result concerning the structure of the derived subgroup of a semi-direct product, we are able to determine completely the derived series of B(4)(S(2)) which from (B(4)(S(2)))(4) onwards coincides with that of the free group of rank 2, as well as its successive derived series quotients.

Induced Modules for Affine Lie Algebras

We study induced modules of nonzero central charge with arbitrary multiplicities over affine Lie algebras. For a given pseudo parabolic subalgebra P of an affine Lie algebra G, our main result establishes the equivalence between a certain category of P-induced G-modules and the category of weight P-modules with injective action of the central element of G. In particular, the induction functor preserves irreducible modules. If P is a parabolic subalgebra with a finite-dimensional Levi factor then it defines a unique pseudo parabolic subalgebra P(ps), P subset of P(ps). The structure of P-induced modules in this case is fully determined by the structure of P(ps)-induced modules. These results generalize similar reductions in particular cases previously considered by V. Futorny, S. Konig, V. Mazorchuk [Forum Math. 13 (2001), 641-661], B. Cox [Pacific J. Math. 165 (1994), 269-294] and I. Dimitrov, V. Futorny, I. Penkov [Comm. Math. Phys. 250 (2004), 47-63].

Polarity-Dependent Transcranial Direct Current Stimulation Effects on Central Auditory Processing

Given the polarity dependent effects of transcranial direct current stimulation (tDCS) in facilitating or inhibiting neuronal processing, and tDCS effects on pitch perception, we tested the effects of tDCS on temporal aspects of auditory processing. We aimed to change baseline activity of the auditory cortex using tDCS as to modulate temporal aspects of auditory processing in healthy subjects without hearing impairment. Eleven subjects received 2mA bilateral anodal, cathodal and sham tDCS over auditory cortex in a randomized and counterbalanced order. Subjects were evaluated by the Random Gap Detection Test (RGDT), a test measuring temporal processing abilities in the auditory domain, before and during the stimulation. Statistical analysis revealed a significant interaction effect of time vs. tDCS condition for 4000 Hz and for clicks. Post-hoc tests showed significant differences according to stimulation polarity on RGDT performance: anodal improved 22.5% and cathodal decreased 54.5% subjects' performance, as compared to baseline. For clicks, anodal also increased performance in 29.4% when compared to baseline. tDCS presented polarity-dependent effects on the activity of the auditory cortex, which results in a positive or negative impact in a temporal resolution task performance. These results encourage further studies exploring tDCS in central auditory processing disorders.

Continuous monitoring of ascorbate transport through neuroblastoma cells with a ruthenium oxide hexacyanoferrate modified microelectrode

The uptake of ascorbate by neuroblastoma cells using a ruthenium oxide hexacyanoferrate (RuOHCF)-modified carbon fiber disc (CFD) microelectrode (r = 14.5 mu m) was investigated. By use of the proposed electrochemical sensor the amperometric determination of ascorbate was performed at 0.0 V in minimum essential medium (MEM, pH = 7.2) with a limit of detection of 25 mu mol L(-1). Under the optimum experimental conditions, no interference from MEM constituents and reduced glutathione (used to prevent the oxidation of ascorbate during the experiments) was noticed. The stability of the RuOHCF-modified electrode response was studied by measuring the sensitivity over an extended period of time (120 h), a decrease of around 10% being noticed at the end of the experiment. The rate of ascorbate uptake by control human neuroblastoma SH-SY5Y cells, and cells transfected with wild-type Cu,Zn-superoxide dismutase (SOD WT) or with a mutant typical of familial amyotrophic lateral sclerosis (SOD G93A), was in agreement with the level of oxidative stress in these cells. The usefulness of the RuOHCF-modified microelectrode for in vivo monitoring of ascorbate inside neuroblastoma cells was also demonstrated.

Nitrogen availability patterns in white-sand vegetations of Central Brazilian Amazon

Addressing spatial variability in nitrogen (N) availability in the Central Brazilian Amazon, we hypothesized that N availability varies among white-sand vegetation types (campina and campinarana) and lowland tropical forests (dense terra-firme forests) in the Central Brazilian Amazon, under the same climate conditions. Accordingly, we measured soil and foliar N concentration and N isotope ratios (delta(15)N) throughout the campina-campinarana transect and compared to published dense terra-firme forest results. There were no differences between white-sand vegetation types in regard to soil N concentration, C:N ratio and delta(15)N across the transect. Both white-sand vegetation types showed very low foliar N concentrations and elevated foliar C:N ratios, and no significant difference between site types was observed. Foliar delta(15)N was depleted, varying from -9.6 to 1.6aEuro degrees in the white-sand vegetations. The legume Aldina heterophylla had the highest average delta(15)N values (-1.5aEuro degrees) as well as the highest foliar N concentration (2.1%) while the non-legume species had more depleted delta(15)N values and the average foliar N concentrations varied from 0.9 to 1.5% among them. Despite the high variation in foliar delta(15)N among plants, a significant and gradual (15)N-enrichment in foliar isotopic signatures throughout the campina-campinarana transect was observed. Individual plants growing in the campinarana were significantly enriched in (15)N compared to those in campina. In the white-sand N-limited ecosystems, the differentiation of N use seems to be a major cause of variations observed in foliar delta(15)N values throughout the campina-campinarana transect.

Change in central kinin B2 receptor density after exercise training in rats

Cardiovascular responses elicited by the stimulation of kinin B2 receptors in the IV cerebral ventricle paratrigeminal nucleus or in the thoracic spinal cord are similar to those observed during an exercise bout Considering that the kalikrein-kinin system (KKS) could act on the cardiovascular modulation during behavioral responses as physical exercise or stress this study evaluated the central B2 receptor densities of Wistar (W) and spontani ously hypertensive rats (SHR) after chronic moderate exercise Animals we re exercise-trained for ten weeks on a treadmill Afterwards systolic blood pressure decreased in both trained strains Animals were killed and the medulla and spinal cord extracted for B2 receptor autoradiography Trained animals were compared to their sedentary controls Sedentary groups showed specific binding sites for Hoe-140 (fmol/mg of tissue) in laminas 1 and 2 of the spinal cord nucleus of the solitary tract (NTS) area postrema (AP) spinal trigeminal tract (sp5) and paratrigeminal nucleus (Pa5) In trained W a significant increase (p<0 05) in specific binding was observed in the Pa5 (31 3%) and NTS (28 2%) Trained SHR showed a significant decrease in n ceptor density in lamina 2 (21 9%) of the thoracic spinal cord and an increase in specific binding in Pa5 (36 1%) We suggest that in the medulla chronic exercise could hyper stimulate the KKS enhancing their efficiency through the increase of B2 receptor density involving this receptor in central cardiovascular control during exercise or stress In the lamina 2 B2 receptor might be involved in the exercise-induced hypotension (C) 2010 Elsevier BV All rights reserved

Regulating industrial forest concessions in Central Africa and South America

Tropical countries face special specific problems in implementing sustainable forest management (SFM). In many countries, questions are raised on whether tropical forests should be publicly, commonly or privately owned and managed in order to enhance sustainability. Other debates also focus on whether small-scale enterprises are better positioned than large-scale industrial concessions to reduce poverty and attain sustainable management. In countries where large tracts of forest are state-owned, concessions are viewed as a means of delivering services of public and collective interest through an association of private investment and public regulation. However, the success of an industrial concession model in countries with large forest resource endowment to achieve multiple goals such as sustainable forest management and local/regional development depends on two critical assumptions. First, forest functions and services should be managed and maintained as public goods. In many cases, additional uses - and corresponding rights - can take place alongside logging activities. Industrial concessions can be more efficient than other tenure models (such as community-based forest management and small-scale enterprises) in achieving SFM, add value to raw material and comply with growing environmental norms. This is especially the case in market-remote areas with low population density and poor infrastructure. Secondly, to achieve these different outcomes, any concession system needs to be monitored and regulated, especially in contexts dominated by asymmetrical information between regulating authorities and concessionaires. New institutional responses have recently been put forward in several countries, providing valuable materials to design a renewed policy mix which associates public and private incentives. This paper provides a survey of the experience of forest concessions in several Central African and South American countries. The concession system is examined in order to clarify the issues involved, the problems encountered, and what can be learned from the shared experience of these countries in the last decade. This paper argues that despite a sometimes patchy record, concessions can help promote SFM so long as they are packaged with a certain number of specific measures. (C) 2008 Elsevier B.V. All rights reserved.

The central role of human resource management in the search for sustainable organizations

The aim of this article is to present the main contributions of human resource management to develop sustainable organizations. The relationship between human resources and organizational sustainability, which is based on economical, social and environmental performance, involves some important aspects concerning management such as innovation, cultural diversity and the environment. The integration of items from the triple bottom line approach leads to developing a model based on a strategic and central posture of human resource management. Based on this model, propositions and recommendations for future research on this theme are presented.

Failure assessments of corroded pipelines with axial defects using stress-based criteria: Numerical studies and verification analyses

Conventional procedures used to assess the integrity of corroded piping systems with axial defects generally employ simplified failure criteria based upon a plastic collapse failure mechanism incorporating the tensile properties of the pipe material. These methods establish acceptance criteria for defects based on limited experimental data for low strength structural steels which do not necessarily address specific requirements for the high grade steels currently used. For these cases, failure assessments may be overly conservative or provide significant scatter in their predictions, which lead to unnecessary repair or replacement of in-service pipelines. Motivated by these observations, this study examines the applicability of a stress-based criterion based upon plastic instability analysis to predict the failure pressure of corroded pipelines with axial defects. A central focus is to gain additional insight into effects of defect geometry and material properties on the attainment of a local limit load to support the development of stress-based burst strength criteria. The work provides an extensive body of results which lend further support to adopt failure criteria for corroded pipelines based upon ligament instability analyses. A verification study conducted on burst testing of large-diameter pipe specimens with different defect length shows the effectiveness of a stress-based criterion using local ligament instability in burst pressure predictions, even though the adopted burst criterion exhibits a potential dependence on defect geometry and possibly on material`s strain hardening capacity. Overall, the results presented here suggests that use of stress-based criteria based upon plastic instability analysis of the defect ligament is a valid engineering tool for integrity assessments of pipelines with axial corroded defects. (C) 2008 Elsevier Ltd. All rights reserved.

Using indicators of deforestation and land-use dynamics to support conservation strategies: A case study of central Rondonia, Brazil

In Rondonia State, Brazil, settlement processes have cleared 68,000 km 2 of tropical forests since the 1970s. The intensity of deforestation has differed by region depending on driving factors like roads and economic activities. Different histories of land-use activities and rates of change have resulted in mosaics of forest patches embedded in an agricultural matrix. Yet, most assessments of deforestation and its effects on vegetation, soil and water typically focus on landscape patterns of current conditions, yet historical deforestation dynamics can influence current conditions strongly. Here, we develop and describe the use of four land-use dynamic indicators to capture historical land-use changes of catchments and to measure the rate of deforestation (annual deforestation rate), forest regeneration level (secondary forest mean proportion), time since disturbance (mean time since deforestation) and deforestation profile (deforestation profile curvature). We used the proposed indices to analyze a watershed located in central Rondonia. Landsat TM and ETM+ images were used to produce historical land-use maps of the last 18 years, each even year from 1984 to 2002 for 20 catchments. We found that the land-use dynamics indicators are able to distinguish catchments with different land-use change profiles. Four categories of historical land-use were identified: old and dominant pasture cover on small properties, recent deforestation and dominance of secondary growth, old extensive pastures and large forest remnants and, recent deforestation, pasture and large forest remnants. Knowing historical deforestation processes is important to develop appropriate conservation strategies and define priorities and actions for conserving forests currently under deforestation. (C) 2009 Elsevier B.V. All rights reserved.

Cattle depredation by puma (Puma concolor) and jaguar (Panthera onca) in central-western Brazil

In this study, data on cattle depredation by puma (Puma concolor) and jaguar (Panthera onca) were recorded for six years (1998 - 2003) in a cattle ranch in central-western Brazil. Depredation represented 18.9% of the overall cattle mortality, being predominant on calves. in biomass, kills represented 0.4% (63.8 kg/km(2)) of the ranch`s annual stock. in economic loss, kills represented 0.3% of the cattle stock value. Depredation was mainly associated with cattle`s age class and location along with the time of birth of calves. The proportion of pastures next to forest with depredation (n=33, 48.5%) was not distinguished to the proportion of pastures not bordering forest with depredation (n=35, 51.5%). However, the proportion of pastures next to forest with depredation represented 54% (n=33) of the 61 total pastures that were at least partially surrounded by forest patches or riparian forests that comprised eight continuum blocks of forest fragments of different sizes in the ranch and adjacent areas. No kills occurred in the central portion (main house) of the farm, close to the headquarters where the pastures not bordering forest. The distances of the kills in relation to areas of native forest was 1317.48 +/- 941.03 m. In order to reduce depredation, calves should be kept as far as possible from forest areas and concentrated cattle breeding and calving seasons should be encouraged. (c) 2007 Elsevier Ltd. All rights reserved.