Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

A pattern recognition approach to complex networks

Complex networks exist in many areas of science such as biology, neuroscience, engineering, and sociology. The growing development of this area has led to the introduction of several topological and dynamical measurements, which describe and quantify the structure of networks. Such characterization is essential not only for the modeling of real systems but also for the study of dynamic processes that may take place in them. However, it is not easy to use several measurements for the analysis of complex networks, due to the correlation between them and the difficulty of their visualization. To overcome these limitations, we propose an effective and comprehensive approach for the analysis of complex networks, which allows the visualization of several measurements in a few projections that contain the largest data variance and the classification of networks into three levels of detail, vertices, communities, and the global topology. We also demonstrate the efficiency and the universality of the proposed methods in a series of real-world networks in the three levels.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Random primordial magnetic fields and the gas content of dark matter haloes

We recently predicted the existence of random primordial magnetic fields (RPMFs) in the form of randomly oriented cells with dipole-like structure with a cell size L(0) and an average magnetic field B(0). Here, we investigate models for primordial magnetic field with a similar web-like structure, and other geometries, differing perhaps in L(0) and B(0). The effect of RPMF on the formation of the first galaxies is investigated. The filtering mass, M(F), is the halo mass below which baryon accretion is severely depressed. We show that these RPMF could influence the formation of galaxies by altering the filtering mass and the baryon gas fraction of a halo, f(g). The effect is particularly strong in small galaxies. We find, for example, for a comoving B(0) = 0.1 mu G, and a reionization epoch that starts at z(s) = 11 and ends at z(e) = 8, for L(0) = 100 pc at z = 12, the f(g) becomes severely depressed for M < 10(7) M(circle dot), whereas for B(0) = 0 the f(g) becomes severely depressed only for much smaller masses, M < 10(5) M(circle dot). We suggest that the observation of M(F) and f(g) at high redshifts can give information on the intensity and structure of primordial magnetic fields.

Non-random reef use by fishes at two dominant zones in a tropical, algal-dominated coastal reef

Habitat use and the processes which determine fish distribution were evaluated at the reef flat and reef crest zones of a tropical, algal-dominated reef. Our comparisons indicated significant differences in the majority of the evaluated environmental characteristics between zones. Also, significant differences in the abundances of twelve, from thirteen analyzed species, were observed within and between-sites. According to null models, non-random patterns of species co-occurrences were significant, suggesting that fish guilds in both zones were non-randomly structured. Unexpectedly, structural complexity negatively affected overall species richness, but had a major positive influence on highly site-attached species such as a damselfish. Depth and substrate composition, particularly macroalgae cover, were positive determinants for the fish assemblage structure in the studied reef, prevailing over factors such as structural complexity and live coral cover. Our results are conflicting with other studies carried out in coral-dominated reefs of the Caribbean and Pacific, therefore supporting the idea that the factors which may potentially influence reef fish composition are highly site-dependent and variable.

The Prospective and Retrospective Memory Questionnaire: A population-based random sampling study

The Prospective and Retrospective Memory Questionnaire (PRMQ) has been shown to have acceptable reliability and factorial, predictive, and concurrent validity. However, the PRMQ has never been administered to a probability sample survey representative of all ages in adulthood, nor have previous studies controlled for factors that are known to influence metamemory, such as affective status. Here, the PRMQ was applied in a survey adopting a probabilistic three-stage cluster sample representative of the population of Sao Paulo, Brazil, according to gender, age (20-80 years), and economic status (n=1042). After excluding participants who had conditions that impair memory (depression, anxiety, used psychotropics, and/or had neurological/psychiatric disorders), in the remaining 664 individuals we (a) used confirmatory factor analyses to test competing models of the latent structure of the PRMQ, and (b) studied effects of gender, age, schooling, and economic status on prospective and retrospective memory complaints. The model with the best fit confirmed the same tripartite structure (general memory factor and two orthogonal prospective and retrospective memory factors) previously reported. Women complained more of general memory slips, especially those in the first 5 years after menopause, and there were more complaints of prospective than retrospective memory, except in participants with lower family income.

Conformal deformation of equilibrium measures in normal random ensembles

We investigate the eigenvalue statistics of ensembles of normal random matrices when their order N tends to infinite. In the model, the eigenvalues have uniform density within a region determined by a simple analytic polynomial curve. We study the conformal deformations of equilibrium measures of normal random ensembles to the real line and give sufficient conditions for it to weakly converge to a Wigner measure.

Nonlinear Schrodinger equation with chaotic, random, and nonperiodic nonlinearity

In this Letter we deal with a nonlinear Schrodinger equation with chaotic, random, and nonperiodic cubic nonlinearity. Our goal is to study the soliton evolution, with the strength of the nonlinearity perturbed in the space and time coordinates and to check its robustness under these conditions. Here we show that the chaotic perturbation is more effective in destroying the soliton behavior, when compared with random or nonperiodic perturbation. For a real system, the perturbation can be related to, e.g., impurities in crystalline structures, or coupling to a thermal reservoir which, on the average, enhances the nonlinearity. We also discuss the relevance of such random perturbations to the dynamics of Bose-Einstein condensates and their collective excitations and transport. (C) 2010 Elsevier B.V. All rights reserved.

Approach to Equilibrium for a Class of Random Quantum Models of Infinite Range

We consider random generalizations of a quantum model of infinite range introduced by Emch and Radin. The generalizations allow a neat extension from the class l (1) of absolutely summable lattice potentials to the optimal class l (2) of square summable potentials first considered by Khanin and Sinai and generalised by van Enter and van Hemmen. The approach to equilibrium in the case of a Gaussian distribution is proved to be faster than for a Bernoulli distribution for both short-range and long-range lattice potentials. While exponential decay to equilibrium is excluded in the nonrandom l (1) case, it is proved to occur for both short and long range potentials for Gaussian distributions, and for potentials of class l (2) in the Bernoulli case. Open problems are discussed.

Perturbation treatment of symmetry breaking within random matrix theory

We discuss the applicability, within the random matrix theory, of perturbative treatment of symmetry breaking to the experimental data on the flip symmetry breaking in quartz crystal. We found that the values of the parameter that measures this breaking are different for the spacing distribution as compared to those for the spectral rigidity. We consider both two-fold and three-fold symmetries. The latter was found to account better for the spectral rigidity than the former. Both cases, however, underestimate the experimental spectral rigidity at large L. This discrepancy can be resolved if an appropriate number of eigenfrequencies is considered to be missing in the sample. Our findings are relevant for symmetry violation studies in general. (C) 2008 Elsevier B.V. All rights reserved.

Texture analysis using graphs generated by deterministic partially self-avoiding walks

Texture is one of the most important visual attributes for image analysis. It has been widely used in image analysis and pattern recognition. A partially self-avoiding deterministic walk has recently been proposed as an approach for texture analysis with promising results. This approach uses walkers (called tourists) to exploit the gray scale image contexts in several levels. Here, we present an approach to generate graphs out of the trajectories produced by the tourist walks. The generated graphs embody important characteristics related to tourist transitivity in the image. Computed from these graphs, the statistical position (degree mean) and dispersion (entropy of two vertices with the same degree) measures are used as texture descriptors. A comparison with traditional texture analysis methods is performed to illustrate the high performance of this novel approach. (C) 2011 Elsevier Ltd. All rights reserved.

Bose systems in spatially random or time-varying potentials

Bose systems, subject to the action of external random potentials, are considered. For describing the system properties, under the action of spatially random potentials of arbitrary strength, the stochastic mean-field approximation is employed. When the strength of disorder increases, the extended Bose-Einstein condensate fragments into spatially disconnected regions, forming a granular condensate. Increasing the strength of disorder even more transforms the granular condensate into the normal glass. The influence of time-dependent external potentials is also discussed. Fastly varying temporal potentials, to some extent, imitate the action of spatially random potentials. In particular, strong time-alternating potential can induce the appearance of a nonequilibrium granular condensate.

Modularity and robustness of bone networks

Cortical bones, essential for mechanical support and structure in many animals, involve a large number of canals organized in intricate fashion. By using state-of-the art image analysis and computer graphics, the 3D reconstruction of a whole bone (phalange) of a young chicken was obtained and represented in terms of a complex network where each canal was associated to an edge and every confluence of three or more canals yielded a respective node. The representation of the bone canal structure as a complex network has allowed several methods to be applied in order to characterize and analyze the canal system organization and the robustness. First, the distribution of the node degrees (i.e. the number of canals connected to each node) confirmed previous indications that bone canal networks follow a power law, and therefore present some highly connected nodes (hubs). The bone network was also found to be partitioned into communities or modules, i.e. groups of nodes which are more intensely connected to one another than with the rest of the network. We verified that each community exhibited distinct topological properties that are possibly linked with their specific function. In order to better understand the organization of the bone network, its resilience to two types of failures (random attack and cascaded failures) was also quantified comparatively to randomized and regular counterparts. The results indicate that the modular structure improves the robustness of the bone network when compared to a regular network with the same average degree and number of nodes. The effects of disease processes (e. g., osteoporosis) and mutations in genes (e.g., BMP4) that occur at the molecular level can now be investigated at the mesoscopic level by using network based approaches.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 Elsevier B.V. All rights reserved.