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.
Authors
Ball, NevilleCollections
- Theses [4364]