01587407

j

01587407 Reidys, Christian M. Random structures. Ann. Comb. 4, No.3-4, 375-382 (2000). 2000 Birkh\"auser Verlag (Springer), Basel EN connectivity branching process random structure random graphs

doi:10.1007/PL00001286

Summary: A random structure, $s_n$, consists of (i) a random contact graph $X$ with vertex set $\{1,\dots, n\}$ and (ii) a multi-set of binary relations over the finite set ${\cal A}$, associated with the edges of $X$. The $X$-edges are the union of the edge sets of two random graphs, $X_1$ and $X_2$. $X_1$ is a random partial one factor graph over the vertices $\{\ell_{i_1},\dots, \ell_{i_{2m}}\}$ and has edge set $\{y_1,\dots, y_m\}$. $X_2$ has vertex set $\{1,\dots, n\}$ and is obtained by selecting the edges of $K_n\setminus\{y_1,\dots, y_m\}$ with independent probability $p= c_2/n$, $c_2>0$. This paper provides a probabilistic analysis of the contact graphs of random structures and puts the results into context with the evolutionary optimization of biopolymers.