Another proof of Wright's inequalities

We present a short way of proving the inequalities obtained by Wright in [E.M. Wright, The number of connected sparsely edged graphs III: Asymptotic results, Journal of Graph Theory 4 (1980) 393-407] concerning the number of connected graphs with ? edges more than vertices.     

Extremal properties of three-dimensional sensor networks with applications

We analyze various critical transmitting/sensing ranges for connectivity and coverage in three-dimensional sensor networks. As in other large-scale complex systems, many global parameters of sensor networks undergo phase transitions. For a given property of the network, there is a critical threshold, corresponding to the minimum amount of the communication effort or power expenditure by individual nodes, above (respectively, below) which the property exists with high (respectively, a low) probability. For sensor networks, properties of interest include simple and multiple degrees of connectivity/coverage. First, we investigate the network topology according to the region of deployment, the number of deployed sensors, and their transmitting/sensing ranges. More specifically, we consider the following problems: assume that n nodes, each capable of sensing events within a radius of r, are randomly and uniformly distributed in a 3-dimensional region R of volume V, how large must the sensing range R/sub SENSE/ be to ensure a given degree of coverage of the region to monitor? For a given transmission range R/sub TRANS/, what is the minimum (respectively, maximum) degree of the network? What is then the typical hop diameter of the underlying network? Next, we show how these results affect algorithmic aspects of the network by designing specific distributed protocols for sensor networks.     

Random 2 XORSAT Phase Transition

We consider the 2-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form x ⊕ y=0 or x ⊕ y=1. Formula of size m on n Boolean variables are chosen uniformly at random from among all ((n(n-1)) || (m)){n(n-1)\choose m} possible choices. When c<1/2 and as n tends to infinity, the probability p(n,m=cn) that a random 2-XOR formula is satisfiable, tends to the threshold function exp (c/2)⋅(1−2c)^1/4. This gives the asymptotic behavior of random 2-XOR formula in the SAT/UNSAT subcritical phase transition. In this paper, we first prove that the error term in this subcritical region is O(n ⁻¹). Then, in the critical region c=1/2, we prove that p(n,n/2)=Θ(n ^−1/12). Our study relies on the symbolic method and analytical tools coming from generating function theory which also enable us to describe the evolution of n^1/12 p(n,\fracn2(1+mn^-1/3))n^{1/12}\ p(n,\frac{n}{2}(1+\mu n^{-1/3})) as a function of μ. Thus, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of 2-XORSAT transition.     

The Average Size of Giant Components between the Double-Jump

We study the sizes of connected components according to their excesses during a random graph process built with n vertices. The considered model is the continuous one defined in [17]. An ℓ-component is a connected component with ℓ edges more than vertices. ℓ is also called the excess of such a component. As our main result, we show that when ℓ and n/ℓ are both large, the expected number of vertices that ever belong to an ℓ-component is about 12^1/3 ℓ^1/3 n^2/3. We also obtain limit theorems for the number of creations of ℓ-components.     

Radio-restoration by yeast s-RNA and its nucleotides of plant tissues cultured in vitro. Restorative activity of yeast s-RNA and a mixture of its nucleotides on the growth of Sorconera crown-gall tissue cultures

Gamma RNA extracts from yeast restore the growth of Scorsonere Crown gall tissues which were subjected to gamma radiation from sigma cobalt 60. A mixture of nucleotides obtained from enzymatic hydrolysis of s-RNA by a ribonuclease T1 has the same stimulatory effect.     

Birth and growth of multicyclic components in random hypergraphs

Define an ?-component to be a connected b-uniform hypergraph with k edges and k(b−1)−? vertices. In this paper, we investigate the growth of size and complexity of connected components of a random hypergraph process. We prove that the expected number of creations of ?-components during a random hypergraph process tends to 1 as b is fixed and ? tends to infinity with the total number of vertices n while remaining ?=o(n^1/3). We also show that the expected number of vertices that ever belong to an ?-component is ∼12^1/3?^1/3n^2/3(b−1)^−1/3. We prove that the expected number of times hypertrees are swallowed by ?-components is ∼2^1/33^−1/3n^1/3?^−1/3(b−1)^−5/3. It follows that with high probability the largest ?-component during the process is of size of order O(?^1/3n^2/3(b−1)^−1/3). Our results give insight into the size of giant components inside the phase transition of random hypergraphs and generalize previous results about graphs.     

Optimal Initialization and Gossiping Algorithms for Random Radio Networks

The initialization problem, also known as naming, consists to give a unique identifier ranging from 1 to n to a set of n indistinguishable nodes in a given network. We consider a network where n nodes (processors) are randomly deployed in a square (respectively, cube) X. We assume that the time is slotted and the network is synchronous, two nodes are able to communicate if they are within distance at most of r of each other (r is the transmitting/receiving range). Moreover, if two or more neighbors of a processor u transmit concurrently at the same time slot, then u would not receive either messages. We suppose also that the anonymous nodes know neither the topology of the network nor the number of nodes in the network. Under this extremal scenario, we first show how the transmitting range of the deployed processors affects the typical characteristics of the network. Then, by allowing the nodes to transmit at various ranges we design sublinear randomized initialization protocols: In the two, respectively, three, dimensional case, our randomized initialization algorithms run in O(n^1/2 log n^1/2), respectively, O(n^1/3 log n^2/3), time slots. These latter protocols are based upon an optimal gossiping algorithm which is of independent interest