Random Structures

Abstract

For many combinatorial objects we can associate a natural probability distribution on the members of the class, and we can then call the resulting class a class of random structures. Random structures form good models of many real world problems, in particular real networks and disordered media. For many such problems, the systems under consideration can be very large, and we often care about whether a property holds most of the time. In particular, for a given class of random structures, we say that a property holds with high probability if the probability that that property holds tends to one as the size of the structures increase. We examine several classes of random structures with real world applications, and look at some properties of each that hold with high probability. First we look at percolation in 3 dimensional lattices, giving a method for producing rigorous confidence intervals on the percolation threshold. Next we look at random geometric graphs, first examining the connectivity thresholds of nearest neighbour models, giving good bounds on the threshold for a new variation on these models useful for modelling wireless networks, and then look at the cop number of the Gilbert model. Finally we look at the structure of random sum-free sets, in particular examining what the possible densities of such sets are, what substructures they can contain, and what superstructures they belong to.