Logo: to the web site of Uppsala University

We propose a modification to the random destruction of graphs: given a finite network with a distinguished set of sources and targets, remove (cut) vertices at random, discarding components that do not contain a source node. We investigate the number of cuts required until all targets are removed, and the size of the remaining graph. This model interpolates between the random cutting model going back to Meir and Moon (J. Austral. Math. Soc. 11, 1970) and site percolation. We prove several general results, including that the size of the remaining graph is a tight family of random variables for compatible sequences of expander-type graphs, and determine limiting distributions for binary caterpillar trees and complete binary trees.

In this thesis, consisting of an introduction and four papers, different models in the mathematical area of combinatorial probability are investigated.

In Paper I, two operations for combining generalised Pólya urns, called disjoint union and product, are defined. This is then shown to turn the set of isomorphism classes of Pólya urns into a semiring, and we find that assigning to an urn its intensity matrix is a semiring homomorphism.

In paper II, a modification and generalisation of the random cutting model is introduced. For a finite graph with given source and target vertices, we remove vertices at random and discard all resulting components without a source node. The results concern the number of cuts needed to remove all target vertices and the size of the remaining graph, and suggest that this model interpolates between the traditional cutting model and site percolation.

In paper III, we define several polynomial invariants for rooted trees based on the modified cutting model in Paper II.We find recursive identities for these invariants and, using an approach via irreducibility of polynomials, prove that two specific invariants are complete, that is, they distinguish rooted trees up to isomorphism.

In paper IV, joint with Paul Thévenin, we consider an operation of concatenating t random perfect matchings on 2n vertices. Our analysis of the resulting random graph as t tends to infinity shows that there is a giant component if and only if n is odd, and that the size of this giant component as well as the number of components is asymptotically normally distributed.