Annals of Combinatorics 4 (2000) 375-382

Random Structures

Christian M. Reidys

Los Alamos National Laboratory, TSA 2, NM 87545, USA

Received September 14, 1998

AMS Subject Classification: 05C38, 05C40, 05C80, 05C90

Abstract. A random structure, sn, consists of (i) a random contact graph X with vertex set {1,..., 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, X1 and X2. X1 is a random partial one factor graph over the vertices$ \{\ell_{i_1},\dots,\ell_{i_{2m}}\}$ and has edge set {y1, ...,ym}. X2 has vertex set {1, ...,n} and is obtained by selecting the edges of Kn \ {y1,...,ym} with independent probability p={c2 / n},c2>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.

Keywords: random structure, random graph, connectivity, branching process


1.  N. Alon, J.H. Spensor, and P. Erdös, The Probabilistic Method, Wiley-Interscience Series, in: Discrete Mathematics and Optimization, John Wiley and Sons, Inc., New York, 1991.

2.  H. Bauer, Wahrscheinlichkeitstheorie, de Gruyter Verlag, 1991.

3.  B. Bollobás, Random Graphs, Academic Press, 1985.

4.  H. Chennoff, A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Stat. 23 (1952) 493509.

5.  R.M. Karp, The transitive closure of a random digraph, Random Structures and Algorithms 1 (1990) 7394.

6.  C.M. Reidys, Random induced subgraphs of generalized n-cubes, Adv. Apply. Math. 19 (1997) 360377.

7.  C.M. Reidys, P.F. Stadler, and P. Schuster, Generic properties of combinatory maps and neutral networks of RNA secondary structures, Bull. Math. Biol. 59 (1997)339397.

8.  P. Schuster, W. Fontana, P.F. Stadler, and I.L. Hofacker, From sequences to shapes and back: a case study in RNA secondary structures, Proc. Roy. Soc. B 255 (1994) 279284.

9.  M.S. Walterman, Combinatorics of RNA hairpins and cloverleaves, Studies Appl. Math. 60 (1978) 9196.

Get the DVI | PS | PDF file of this abstract.