On graphs with few disjoint t-stars

"Vegeu el resum a l'inici del document del fitxer adjunt."

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.

Comparing Multilevel Clustering Methods on Weighted Graphs : The Case of Worldwide Air Passenger Traffic 2000-2004

Specific properties emerge from the structure of large networks, such as that of worldwide air traffic, including a highly hierarchical node structure and multi-level small world sub-groups that strongly influence future dynamics. We have developed clustering methods to understand the form of these structures, to identify structural properties, and to evaluate the effects of these properties. Graph clustering methods are often constructed from different components: a metric, a clustering index, and a modularity measure to assess the quality of a clustering method. To understand the impact of each of these components on the clustering method, we explore and compare different combinations. These different combinations are used to compare multilevel clustering methods to delineate the effects of geographical distance, hubs, network densities, and bridges on worldwide air passenger traffic. The ultimate goal of this methodological research is to demonstrate evidence of combined effects in the development of an air traffic network. In fact, the network can be divided into different levels of âeurooecohesionâeuro, which can be qualified and measured by comparative studies (Newman, 2002; Guimera et al., 2005; Sales-Pardo et al., 2007).

On a family of strongly regular graphs with λ = 1

Vegeu el resum a l'inici del document del fitxer adjunt.

Linking temperature estimates and microstructures in deformed polymineralic mantle rocks

To constrain deformation temperatures of mantle shear zones, we studied a strike-slip shear zone (Hilti massif, Semail ophiolite, Oman) and focused on the interaction between microstructural mechanisms and chemical equilibration processes. Quantitative microfabric analysis on harzburgites with different deformation intensity (porphyroclastic tectonite, mylonite, and ultramylonite) was combined with orthopyroxene geothermometry. The average grain size of all phases decreases with decreasing shear zone thickness. Dynamic recrystallization of porphyroclasts in combination with dissolution-precipitation and nucleation result in small-sized, chemically equilibrated pyroxenes. The composition of orthopyroxene was used to calculate deformation temperatures. In the case of the porphyroclastic tectonites, the chemical composition of orthopyroxene has been reset by diffusion yielding temperature estimates of 880-900 degrees C. The mylonites were deformed by dislocation creep of olivine and show a broad range of calculated temperatures, which result from a combination of grain size reduction and inheritance of equilibrium compositions from earlier high-temperature events and diffusion. In mylonites, diffusion profiles combined with geothermometry and grain size analysis indicate a mylonitic deformation temperature of 800-900 degrees C possibly followed by diffusion. In ultramylonites, the smallest grains (<30 mu m) reveal equilibration at temperatures of similar to 700 degrees C during the last stages of ductile deformation, which was dominated by diffusion creep of olivine. Our results provide a crucial link between temperature and evolution of microstructures from dislocation creep to diffusion creep in mantle shear zones.

Heterogeneous 40Ar* distributions in naturally deformed muscovite: in situ UV-laser ablation evidence for micro structurally controlled intragrain diffusion

Micas are commonly used in Ar-40/Ar-39 thermochronological studies of variably deformed rocks yet the physical basis by which deformation may affect radiogenic argon retention in mica is poorly constrained. This study examines the relationship between deformation and deformation-induced microstructures on radiogenic argon retention in muscovite, A combination of furnace step-heating and high-spatial resolution in situ UV-laser ablation Ar-40/Ar-39 analyses are reported for deformed muscovites sampled from a granitic pegmatite vein within the Siviez-Mischabel Nappe, western Swiss Alps (Penninic domain, Brianconnais unit). The pegmatite forms part of the Variscan (similar to 350 Ma) Alpine basement and exhibits a prominent Alpine S-C fabric including numerous mica `fish' that developed under greenschist facies metamorphic conditions, during the dominant Tertiary Alpine tectonic phase of nappe emplacement. Furnace step-heating of milligram quantities of separated muscovite grains yields an Ar-40/Ar-39 age spectrum with two distinct staircase segments but without any statistical plateau, consistent with a previous study from the same area. A single (3 X 5 mm) muscovite porphyroclast (fish) was investigated by in situ UV-laser ablation. A histogram plot of 170 individual Ar-40/Ar-39 UV-laser ablation ages exhibit a range from 115 to 387 Ma with modes at approximately 340 and 260 Ma. A variogram statistical treatment of the (40)Ad/Ar-39 results reveals ages correlated with two directions; a highly correlated direction at 310 degrees and a lesser correlation at 0 degrees relative to the sense of shearing. Using the highly correlated direction a statistically generated (Kriging method) age contour map of the Ar-40/Ar-39 data reveals a series of elongated contours subparallel to the C-surfaces which where formed during Tertiary nappe emplacement. Similar data distributions and slightly younger apparent ages are recognized in a smaller mica fish. The observed intragrain age variations are interpreted to reflect the partial loss of radiogenic argon during Alpine (similar to 35 Ma) greenschist facies metamorphism. One-dirnensional diffusion modelling results are consistent with the idea that the zones of youngest apparent age represent incipient shear band development within the mica porphyroclasts, thus providing a network of fast diffusion pathways. During Alpine greenschist facies metamorphism the incipient shear bands enhanced the intragrain loss of radiogenic argon. The structurally controlled intragrain age variations observed in this investigation imply that deformation has a direct control on the effective length scale for argon diffusion, which is consistent with the heterogeneous nature of deformation. (C) 2001 Elsevier Science B.V. All rights reserved.

The evolution of helping and harming on graphs: the return of the inclusive fitness effect.

Evolutionary graph theory has been proposed as providing new fundamental rules for the evolution of co-operation and altruism. But how do these results relate to those of inclusive fitness theory? Here, we carry out a retrospective analysis of the models for the evolution of helping on graphs of Ohtsuki et al. [Nature (2006) 441, 502] and Ohtsuki & Nowak [Proc. R. Soc. Lond. Ser. B Biol. Sci (2006) 273, 2249]. We show that it is possible to translate evolutionary graph theory models into classical kin selection models without disturbing at all the mathematics describing the net effect of selection on helping. Model analysis further demonstrates that costly helping evolves on graphs through limited dispersal and overlapping generations. These two factors are well known to promote relatedness between interacting individuals in spatially structured populations. By allowing more than one individual to live at each node of the graph and by allowing interactions to vary with the distance between nodes, our inclusive fitness model allows us to consider a wider range of biological scenarios leading to the evolution of both helping and harming behaviours on graphs.

Interactome mapping of the phosphatidylinositol 3-kinase-mammalian target of rapamycin pathway identifies deformed epidermal autoregulatory factor-1 as a new glycogen synthase kinase-3 interactor.

The phosphatidylinositol 3-kinase-mammalian target of rapamycin (PI3K-mTOR) pathway plays pivotal roles in cell survival, growth, and proliferation downstream of growth factors. Its perturbations are associated with cancer progression, type 2 diabetes, and neurological disorders. To better understand the mechanisms of action and regulation of this pathway, we initiated a large scale yeast two-hybrid screen for 33 components of the PI3K-mTOR pathway. Identification of 67 new interactions was followed by validation by co-affinity purification and exhaustive literature curation of existing information. We provide a nearly complete, functionally annotated interactome of 802 interactions for the PI3K-mTOR pathway. Our screen revealed a predominant place for glycogen synthase kinase-3 (GSK3) A and B and the AMP-activated protein kinase. In particular, we identified the deformed epidermal autoregulatory factor-1 (DEAF1) transcription factor as an interactor and in vitro substrate of GSK3A and GSK3B. Moreover, GSK3 inhibitors increased DEAF1 transcriptional activity on the 5-HT1A serotonin receptor promoter. We propose that DEAF1 may represent a therapeutic target of lithium and other GSK3 inhibitors used in bipolar disease and depression.

Deformed-jellium model for the fission of multiply charged metal clusters

A deformed-jellium model is used to calculate the fission barrier height of positive doubly charged sodium clusters within an extended Thomas-Fermi approximation. The fissioning cluster is continuously deformed from the parent configuration until it splits into two fragments. Although the shape of the fission barrier obviously depends on the parametrization of the fission path, we have found that remarkably, the maximum of the barrier corresponds to a configuration in which the emerging fragments are already formed and rather well apart. The implication of this finding in the calculation of critical numbers for fission is illustrated in the case of multiply charged Na clusters.

A note on the degree sequences of graphs with restrictions

Degree sequences of some types of graphs will be studied and characterizedin this paper.

Generating hard SAT/CSP instances using expander graphs

In this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and high expansion implies high resolution width. We have extended this approach to generate hard n-ary CSP instances and we have also adapted this idea to increase the expansion of the system of linear equations used to generate XORSAT instances, being able to produce harder satisfiable instances than former generators.