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.

Gibbs random graphs on point processes

Consider a discrete locally finite subset Gamma of R(d) and the cornplete graph (Gamma, E), with vertices Gamma and edges E. We consider Gibbs measures on the set of sub-graphs with vertices Gamma and edges E` subset of E. The Gibbs interaction acts between open edges having a vertex in common. We study percolation properties of the Gibbs distribution of the graph ensemble. The main results concern percolation properties of the open edges in two cases: (a) when Gamma is sampled from a homogeneous Poisson process; and (b) for a fixed Gamma with sufficiently sparse points. (c) 2010 American Institute of Physics. [doi:10.1063/1.3514605]

An oracle approach for interaction neighborhood estimation in random fields

We consider the problem of interaction neighborhood estimation from the partial observation of a finite number of realizations of a random field. We introduce a model selection rule to choose estimators of conditional probabilities among natural candidates. Our main result is an oracle inequality satisfied by the resulting estimator. We use then this selection rule in a two-step procedure to evaluate the interacting neighborhoods. The selection rule selects a small prior set of possible interacting points and a cutting step remove from this prior set the irrelevant points. We also prove that the Ising models satisfy the assumptions of the main theorems, without restrictions on the temperature, on the structure of the interacting graph or on the range of the interactions. It provides therefore a large class of applications for our results. We give a computationally efficient procedure in these models. We finally show the practical efficiency of our approach in a simulation study.

The Lobel-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars

Loebl, Komlos, and Sos conjectured that if at least half the vertices of a graph G have degree at least some k is an element of N, then every tree with at most k edges is a subgraph of G. We prove the conjecture for all trees of diameter at most 5 and for a class of caterpillars. Our result implies a bound on the Ramsey number r( T, T') of trees T, T' from the above classes.

Morpholin-4-ium morpholine-4-carbodithioate

The title compound, C(4)H(10)NO(+)center dot C(5)H(8)NOS(2)(-), is built up of a morpholinium cation and a dithiocarbamate anion. In the crystal, two structurally independent formula units are linked via N-H center dot center dot center dot S hydrogen bonds, forming an inversion dimer, with graph-set motif R(4)(4)(12).

Skewness, splitting number and vertex deletion of some toroidal meshes

The skewness sk(G) of a graph G = (V, E) is the smallest integer sk(G) >= 0 such that a planar graph can be obtained from G by the removal of sk(C) edges. The splitting number sp(G) of C is the smallest integer sp(G) >= 0 such that a planar graph can be obtained from G by sp(G) vertex splitting operations. The vertex deletion vd(G) of G is the smallest integer vd(G) >= 0 such that a planar graph can be obtained from G by the removal of vd(G) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh C(m) x C(n) for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation Tc(m) x c(n) of C(m) x C(n) in the torus, and an hexagonal mesh Hc(m) x c(n), the dual of Tc(m) x c(n) in the torus. It is established that sp(Tc(m) x c(n)) = vd(Tc(m) x c(n) = sk(Hc(m) x c(n)) = sp(Hc(m) x c(n)) = vd(Hc(m) x c(n)) = min{m, n} and that sk(Tc(m) x c(n)) = 2 min {m, n}.

Annealing effects on microstructure and coercive field of ferritic-martensitic ODS Eurofer steel

Oxide dispersion strengthened reduced-activation ferritic-martensitic steels are promising candidates for applications in future fusion power plants. Samples of a reduced activation ferritic-martensitic 9 wt.%Cr-oxide dispersion strengthened Eurofer steel were cold rolled to 80% reduction in thickness and annealed in vacuum for 1 h from 200 to 1350 degrees C to evaluate its thermal stability. Vickers microhardness testing and electron backscatter diffraction (EBSD) were used to characterize the microstructure. The microstructural changes were also followed by magnetic measurements, in particular the corresponding variation of the coercive field (H(c)), as a function of the annealing treatment. Results show that magnetic measurements were sensitive to detect the changes, in particular the martensitic transformation, in samples annealed above 850 degrees C (austenitic regime). (C) 2010 Elsevier B.V. All rights reserved.

Node-Depth Encoding and Multiobjective Evolutionary Algorithm Applied to Large-Scale Distribution System Reconfiguration

The power loss reduction in distribution systems (DSs) is a nonlinear and multiobjective problem. Service restoration in DSs is even computationally hard since it additionally requires a solution in real-time. Both DS problems are computationally complex. For large-scale networks, the usual problem formulation has thousands of constraint equations. The node-depth encoding (NDE) enables a modeling of DSs problems that eliminates several constraint equations from the usual formulation, making the problem solution simpler. On the other hand, a multiobjective evolutionary algorithm (EA) based on subpopulation tables adequately models several objectives and constraints, enabling a better exploration of the search space. The combination of the multiobjective EA with NDE (MEAN) results in the proposed approach for solving DSs problems for large-scale networks. Simulation results have shown the MEAN is able to find adequate restoration plans for a real DS with 3860 buses and 632 switches in a running time of 0.68 s. Moreover, the MEAN has shown a sublinear running time in function of the system size. Tests with networks ranging from 632 to 5166 switches indicate that the MEAN can find network configurations corresponding to a power loss reduction of 27.64% for very large networks requiring relatively low running time.

Assembling a consistent set of sentences in relational probabilistic logic with stochastic independence

We examine the representation of judgements of stochastic independence in probabilistic logics. We focus on a relational logic where (i) judgements of stochastic independence are encoded by directed acyclic graphs, and (ii) probabilistic assessments are flexible in the sense that they are not required to specify a single probability measure. We discuss issues of knowledge representation and inference that arise from our particular combination of graphs, stochastic independence, logical formulas and probabilistic assessments. (C) 2007 Elsevier B.V. All rights reserved.

Probabilistic logic with independence

This paper investigates probabilistic logics endowed with independence relations. We review propositional probabilistic languages without and with independence. We then consider graph-theoretic representations for propositional probabilistic logic with independence; complexity is analyzed, algorithms are derived, and examples are discussed. Finally, we examine a restricted first-order probabilistic logic that generalizes relational Bayesian networks. (c) 2007 Elsevier Inc. All rights reserved.

Impact of plastic deformation on magnetoacoustic properties of Fe-2%Si alloy

The paper presents the results of a complementary study including magnetic hysteresis loops B(H), magnetic Barkhausen noise (MBN) and magnetoacoustic emission (MAE) signals measurements for plastically deformed Fe-2%Si samples. The investigated samples had been plastically deformed with plastic strain level (epsilon(p)) up to 8%. The properties of B(H) loops are quantified using the coercivity H(C) and maximum differential permeability mu(rmax) as parameters. The MBN and MAE voltage signals were analysed by means of rms-like voltage (Ub and Ua, respectively) envelopes, plotted as a function of applied field strength. Integrals of the Ub and Ua voltages over half of a period of magnetization were then calculated. It has been found that He and integrals of Ub increase, while mu(rmax) decreases monotonically with increasing epsilon(p). The MAE (Ua) peak voltage at first decreases, then peaks at epsilon(p) approximate to 1.5% and finally decreases again. The integral of the Ua voltage at first increases for low epsilon(p) and then decreases for epsilon(p) > 1.5%. All those various dependence types suggest the possibility of detection of various stages of microstructure change. The above-mentioned results are discussed qualitatively in the paper. Some modelling of the discussed dependency is also presented. (C) 2008 Elsevier Ltd. All rights reserved.

An In-Depth Study of the Barkhausen Emission Signal Properties of the Plastically Deformed Fe-2%Si Alloy

This paper presents the results of the in-depth study of the Barkhausen effect signal properties for the plastically deformed Fe-2%Si samples. The investigated samples have been deformed by cold rolling up to plastic strain epsilon(p) = 8%. The first approach consisted of time-domain-resolved pulse and frequency analysis of the Barkhausen noise signals whereas the complementary study consisted of the time-resolved pulse count analysis as well as a total pulse count. The latter included determination of time distribution of pulses for different threshold voltage levels as well as the total pulse count as a function of both the amplitude and the duration time of the pulses. The obtained results suggest that the observed increase in the Barkhausen noise signal intensity as a function of deformation level is mainly due to the increase in the number of bigger pulses.

Hysteresis loss subdivision

Assuming that different energy dissipation mechanisms are at work along hysteresis, a hysteresis loss subdivision procedure has been proposed, using the induction at maximum permeability ( around 0.8 T, in electrical steels) as the boundary between the ""low-induction`` and the ""high-induction`` regions. This paper reviews the most important results obtained in 10 years of investigation of the effect of microstructure on these components of the hysteresis loss. As maximum induction increases, the ""low-induction loss`` increases linearly up to 1.2 T, while the ""high-induction loss`` is zero up to 0.7 T and then increases as a power law with n = 5. Low-induction loss behavior is linearly related to H(c) between 0.4 and 1.2 T. Grain size has a larger influence on low-induction losses than on high-induction losses. Texture has a much stronger influence on high loss than on low-induction loss, and it is related to the average magnetocrystalline energy. 6.5%Si steel shows smaler hysteresis loss at 1.5 T than 3.5%Si steel only because of its smaler high-induction component. The abrupt increase in hysteresis loss due to very small plastic deformation is strongly related to the high-induction loss component. These results are discussed in terms of energy dissipation mechanisms such as domain wall movement, irreversible rotation and domain wall energy dissipation at domain nucleation and annihilation. (C) 2008 Elsevier B.V. All rights reserved.

Exploring the random genesis of co-occurrence networks

Using the network random generation models from Gustedt (2009)[23], we simulate and analyze several characteristics (such as the number of components, the degree distribution and the clustering coefficient) of the generated networks. This is done for a variety of distributions (fixed value, Bernoulli, Poisson, binomial) that are used to control the parameters of the generation process. These parameters are in particular the size of newly appearing sets of objects, the number of contexts in which new elements appear initially, the number of objects that are shared with `parent` contexts, and, the time period inside which a context may serve as a parent context (aging). The results show that these models allow to fine-tune the generation process such that the graphs adopt properties as can be found in real world graphs. (C) 2011 Elsevier B.V. All rights reserved.