Portal de Periódicos da CAPES

Knots in Graphs in Subsets of Z 3

1998; Institute of Electrical and Electronics Engineers; Linguagem: Inglês

10.1007/978-1-4612-1712-1_10

2198-3224

C E Soteros,

Point processes and geometric inequalities

The probability that an embedding of a graph in Z 3 is knotted is investigated. For any given graph (embeddable in Z 3) without cut edges, it is shown that this probability approaches 1 at an exponential rate as the number of edges in the embedding goes to infinity. Furthermore, at least for a subset of these graphs, the rate at which the probability approaches 1 does not depend on the particular graph being embedded. Results analogous to these are proved to be true for embeddings of graphs in a subset of Z 3 bounded by two parallel planes (a slab). In order to investigate the knotting probability of embeddings of graphs in a rectangular prism (an infinitely long rectangular tube in Z 3), a pattern theorem for self-avoiding polygons in a prism is proved. From this it is possible to prove that for any given eulerian graph, the probability that an embedding of the graph in a prism is knotted goes to 1 as the number of edges in the embedding goes to infinity. Then, just as for Z 3, there is at least a subset of these graphs for which the rate that this probability approaches 1 does not depend on the particular graph. Similar results are shown to hold in cases where restrictions are placed on the number of edges per branch in a graph embedding.