Stability of vertices in random boolean cellular automata

Based on computer simulations, Kauffman (Physica D, 10, 145-156, 1984) made several generalizations about a random Boolean cellular automaton which he invented as a model of cellular metabolism. Here we give the first rigorous proofs of two of Kauffman's generalizations: a large fraction of vertices stabilize quickly, consequently the length of cycles in the automaton's behavior is small compared to that of a random mapping with the same number of states; and reversal of the states of a large fraction of the vertices does not affect the cycle to which the automaton moves.     

Cycles in a random graph near the critical point

Let G(n, M) be a graph chosen at random from the family of all labelled graphs with n vertices and M(n) = 0.5n + s(n) edges, where s³(n)n^?2→∞ but s(n) = o(n). We find the limit distribution of the length of shortest cycle contained in the largest component of G(n, M), as well as of the longest cycle outside it. We also describe the block structure of G(n, M) and derive from this result the limit probability that G(n, M) contains a cycle with a diagonal. Finally, we show that the probability tending to 1 as n-→∞ the length of the longest cycle in G(n, M) is of the order s²(n)/n.     

Properties of Ergodic Projection for Quantum Dynamical Semigroups

We study properties of ergodic projection forquantum dynamical semigroups on W *-algebras. Inparticular, we describe the normal and singular parts ofthis projection, characterize normal invariantfunctionals, and derive some conclusions for ergodicsemigroups.     

A hybrid evolutionary algorithm for the two-dimensional packing problem

This paper presents a hybrid evolutionary algorithm for the two-dimensional non-guillotine packing problem. The problem consists of packing many rectangular pieces into a single rectangular sheet in order to maximize the total area of the pieces packed. Moreover, there is a constraint on the maximum number of times that a piece may be used in a packing pattern. The set of packing patterns is processed by an evolutionary algorithm. Three mutation operators and two types of quality functions are used in the algorithm. The best solution obtained by the evolutionary algorithm is used as the initial solution in a tree search improvement procedure. This approach is tested on a set of benchmark problems taken from the literature and compared with the results published by other authors.     

Random subgraphs of the 2D Hamming graph: the supercritical phase

We study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on n vertices. Let p be the edge probability, and write ${p={(1+\varepsilon)}/{(2(n-1))}}$ for some ${\varepsilon \in \mathbb{R}}$ . In Borgs et al. (Random Struct Alg 27:137–184, 2005; Ann Probab 33:1886–1944, 2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for ${\varepsilon \leq \Lambda V^{-1/3}}$ , where Λ >  0 is a constant and V = n ² denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained. In this paper we prove that, when ${\varepsilon \gg (\log{V})^{1/3} V^{-1/3}}$ , then the largest connected component has size close to ${2 \varepsilon V}$ with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of p are supercritical. Barring the factor ${(\log{V})^{1/3}}$ , this identifies the size of the largest connected component all the way down to the critical p window.     

A new approach to the giant component problem

We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence. We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np = 1 + ω(n)n^?1/3, where ω(n) → ∞ arbitrarily slowly. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Entanglement in a three spin system controlled by electric and magnetic fields

We study the effect of electric field and magnetic flux on spin entanglement in an artificial triangular molecule built of coherently coupled quantum dots. In a subspace of doublet states an explicit relation of concurrence with spin correlation functions and chirality is presented. The electric field modifies superexchange correlations and shifts many-electron levels (the Stark effect), as well as changing spin correlations. For some specific orientation of the electric field one can observe monogamy, for which one of the spins is separated from two others. Moreover, the Stark effect manifests itself in a different spin entanglement for small and strong electric fields. The role of magnetic flux is opposite: it leads to circulation of spin supercurrents and spin delocalization.     

On k-leaf connectivity of a random graph

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > 1/4. A threshold function for k-leaf connectivity is also found.