Uniform multicommodity flows in random networks

Thesis

Given a network 𝒩, and a collection 𝒱 of unordered pairs of vertices in 𝒩, a corresponding uniform multicommodity flow F of volume φ consists of simultaneous flows of volume φ of unique commodities between each pair of vertices in 𝒱. The maximum uniform flow volume is the maximum value of φ such that there is a uniform multicommodity flow of volume φ in 𝒩, within the capacity constraints.

This thesis considers networks with random edge-capacities. Multicommodity flows are of interest in operational research and combinatorial optimisation and sampling. They have been studied extensively from a "worst-case" perspective, but the "typical" behaviour of multicommodity flow problems is much less well understood. In order to address this, a model is considered in which the underlying graph is fixed and the edge capacities are random. Aldous, McDiarmid and Scott studied the case in which the underlying graph is complete, the edge capacities are independent, each distributed like a given random variable C, and 𝒱 is the collection of all unordered pairs of vertices.

Another very natural example is the d-dimensional (hyper)cube Q^d, with independent random edge capacities, where the probability of an edge having zero capacity is less than 1/2. Two models are studied. In the first, flows are routed between all antipodal (opposite) pairs of vertices, and in the second, flows are routed between all vertex pairs. In both cases, as d tends to infinity, asymptotic values for the maximum uniform flow volumes are determined.

A detailed characterisation is given next for the size and distribution of components in a random subgraph of the hypercube where the probability of an edge being present is a constant less than 1/2. It is shown that, whp, other than the main component, the number of vertices in any component is bounded by a constant and that the number of components of a given size or configuration is asymptotically normal. Multicommodity flows in the largest component of such a network are then analysed.

Two further random structures are considered. Firstly, a network formed by giving each edge of a random cubic graph a capacity of 1 is considered. In this case the capacities are not random but the structure of the underlying graph is. This case is of interest as it is a tractable example of a graph with the 'small world' property that the diameter increases like log n. Secondly the argument of Aldous, McDiarmid and Scott is generalised to give results for directed and undirected complete multipartite graphs. Lastly multicommodity flows in a directed hypercube are considered.

Authors: Withers, P

• DOI: 10.5287/ora-z6bpg9kae
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: Percolation; Component structure; Hypercube; Random Graph; Multicommodity flow; Network