Interest in discrete distributions has increased markedly over the past two decades or so. However, although a very large number of univariate discrete distributions have been extensively investigated, relatively few bivariate versions of these have been studied in any detail. In this thesis we introduce bivariate Hermite, Poisson binomial, and Poisson Pascal distributions and go on to investigate certain structural and estimation properties of bivariate generalized Poisson distributions. We introduce the notation and terminology which provides the basis for this thesis in Chapter 1. In Chapter 2, following an approach due to Subrahmaniam [1966] we examine conditionality in bivariate generalized Poisson distributions with special reference to the bivariate Neyman type A models. We consider in Chapter 3 bivariate versions of two univariate estimation procedures known as 'the method of zero frequency' and '.the method of even points'. We continue by applying these to the bivariate Poisson, Negative binomial, and Neyman A type I, type II, and type III distributions. Holgate [1966] describes three ways of constructing bivariate distributions with Neyman type A marginals. Proceeding on similar lines in Chapter 4, we introduce bivariate Poisson binomial and Poisson Pascal distributions and we study various properties including conditional distributions and regression functions. We examine in Chapter 5 parameter estimation for bivariate Poisson binomial distributions using zero frequencies, even points, and moments. In Chapter 6, following Kemp [1972], we define two bivariate Hermite distributions, one with five and one with eight parameters via various straightforward extensions of the models leading to the univariate Hermite distribution. We continue by deriving recurrence relations for the probabilities and the central moments, bound for the correlation coefficient, conditional distributions, regression functions, and limiting forms.

No description available.

In this thesis, we research the computational complexity of the graph colouring problem and its variants including precolouring extension and list colouring for graph classes that can be characterised by forbidding one or more induced subgraphs. We investigate the structural properties of such graph classes and prove a number of new properties. We then consider to what extent these properties can be used for efficiently solving the three types of colouring problems on these graph classes. In some cases we obtain polynomial-time algorithms, whereas other cases turn out to be NP-complete. We determine the computational complexity of k-COLOURING, k-PRECOLOURING EXTENSION and LIST k-COLOURING on $P_k$-free graphs. In particular, we prove that k-COLOURING on $P_8$-free graphs is NP-complete, 4-PRECOLOURING EXTENSION $P_7$-free graphs is NP-complete, and LIST 4-COLOURING on $P_6$-free graphs is NP-complete. In addition, we show the existence of an integer r such that k-COLOURING is NP-complete for $P_r$-free graphs with girth 4. In contrast, we determine for any fixed girth $g\geq 4$ a lower bound $r(g)$ such that every $P_{r(g)}$-free graph with girth at least $g$ is 3-colourable. We also prove that 3-LIST COLOURING is NP-complete for complete graphs minus a matching. We present a polynomial-time algorithm for solving 4-PRECOLOURING EXTENSION on $(P_2+P_3)$-free graphs, a polynomial-time algorithm for solving LIST 3-Colouring on $(P_2+P_4)$-free graphs, and a polynomial-time algorithm for solving LIST 3-COLOURING on $sP_3$-free graphs. We prove that LIST k-COLOURING for $(K_{s,t},P_r)$-free graphs is also polynomial-time solvable. We obtain several new dichotomies by combining the above results with some known results.

Every relation between posets gives rise to an adjunction, known as a Galois connection, between the corresponding power sets. Formal concept analysis (FCA) studies the fixed points of these adjunctions, which can be interpreted as latent “concepts” [20], [19]. In [47] Pavlovic defines a generalisation of posets he calls proximity sets (or proxets), which are equivalent to the generalised metric spaces of Lawvere [37], and introduces a form of quantitative concept analysis (QCA) which provides a different viewpoint from other approaches to fuzzy concept analysis (for a survey see [4]). The nucleus of a fuzzy relation between proxets is defined in terms of the fixed points of a naturally arising adjunction based on the given relation, generalising the Galois connections of formal concept analysis. By giving the unit interval [0, 1] an appropriate category structure it can be shown that proxets are simply [0, 1]-enriched categories and the nuclues of a proximity relation between proxets is a generalisation of the notion of the Isbell completion of an enriched category. We prove that the sets of fixed points of an adjunction arising from a fuzzy relation can be given the structure of complete idempotent semimodules and show that they are isomorphic to tropical convex hulls of point configurations in tropical projective space, in which addition and scalar multiplication are replaced with pointwise minima and addition, respectively. We show that some the results of Develin and Sturmfels on tropical convex sets [13] can be applied to give the nucleus of a proximity relation the structure of a cell complex, which we term the fuzzy concept complex. We provide a formula for counting cells of a given dimension in generic situations. We conclude with some thoughts on computing the fuzzy concept complex using ideas from Ardila and Develin’s work on tropical oriented matroids [1].

A word- graph Gw is a simple digraph associated with a finite word w such that the vertex set of Gw is the alphabet of wand the edge-set of Gw is determined by ~on-identical adjacent letter pairs in w. A family of word-graphs can be thought of as a formal language. The novel theory of word- graphs proposed in this thesis is of interest for two reasons: . first, word-graphs have close links with a range of word-based stochastic processes such as language, music, DNA and protein sequences; second, the cross-applicability of proof techniques in graph theory and combinatorics on words has lead to a recent explosion of interest in the literature in the relationship between words and graphs. The focus of this thesis is on developing a theory of word-graphs by formalising how structural word-theoretic properties manifest in digraphs and how structural graphtheoretic properties manifest in words. The analysis starts by looking at the relationship between word and digraph forms and continues by investigating whether or not a given digraph can be represented by a word or a set of words. The main findings include: representational word and digraph structure is intrinsically linked; every finite digraph can be represented by a finite set of words; and the number of words required to represent a digraph is determined by that digraph's edge-contracted subgraphs. Besides the theory's applications in stochastic process analysis, word- graph theory has the potential to be used as a general methodology for digraph and word theoretic analysis.

The Cartesian Cut Cell method has been applied to different flow configurations by researchers at the Centre of Mathematical Modelling and Flow Analysis. This method has been implementer to define flow domains around obstacles using a Godunov-type high order upwind scheme to solve Shallow Water Equations and Navier-Stokes (Euler) equations in two phase flows. A new idea to study Navier-Stoke (Euler) equations in just one phase flows where the domain is accurate described using the Cartesian Cut Cell Method around the moving free surface is presented. The solution technique involves three stages for every time step: the definition of the domain, the solution of the flow equations and the movement of the free surface. The Cartesian Cut Cell Method only requires to recompute cells affected by the movement of the free surface obtaining providing quickly the new domain. The flow equations are solved using the Artificial Compressibility Method and a Godunov-type high order upwind scheme involving the solution of Riemann problems. The Heigh Function method is applied to study the evolution on time of the free surface. This method involves the solution of the kinematic equations, where a fourth order Runge-Kutta method is employed. Boundary conditions at the free surface are discussed. The technique proposed is very quick and allows the use of big time steps. In comparison with the two phase version, the proposed techniques used one thousand times bigger time steps and require around 25 times less computational effort. On the other hand, the results shows dependency on the artificial compressibility parameter introduced as part of the solution of the flow equations. Extensions to the presented study are proposed including the use of different flow solvers.

Frequentist methods for learning Gaussian graphical model structure are unsuccessful at identifying hubs when n < p. An alternative is Bayesian structure-learning, in which it is common to restrict attention to certain classes of graphs and to explore and approximate the posterior distribution by repeatedly moving from one graph to another, using MCMC or other methods such as stochastic shotgun search (SSS). ( give two corrected versions of an algorithm for non-decomposable graphs and discuss random graph distributions in depth, in particular as priors in Bayesian structure-learning. The main topic of the thesis is Bayesian structure-learning with forests or trees. Forest and tree graphical models are widely used, and I explain how restricting attention to these graphs can be justified using theorems on random graphs. I describe how to use methods based on the Chow-Liu algorithm and the Matrix Tree Theorem to find the MAP forest and certain quantities in the full posterior distribution on trees. I give adapted versions of MCMC and SSS for approximating the posterior distribution for forests and trees, and systems for storing these graphs so that it is easy and efficient to choose legal moves to neighbouring forests or trees and update the stored information. Experiments with the adapted algorithms and simulated datasets show that the system for storing trees so that moves are chosen uniformly at random does not bring much advantage over simpler systems. SSS with trees does well when the true graph is a tree or a sparse graph. Graph priors improve detection of hubs but need large ranges of probabilities to have much effect. SSS with trees and SSS with forests do better than SSS with decomposable graphs in certain cases. MCMC on forests often fails to mix well and MCMC on trees is much slower than SSS.

A homogeneous structure is a countable (finite or countably infinite) first order structure such that every isomorphism between finitely generated substructures extends to an automorphism of the whole structure. Examples of homogeneous structures include any countable set, the pentagon graph, the random graph, and the linear ordering of the rationals. Countably infinite homogeneous structures are precisely the Fraisse limits of amalgamation classes of finitely generated structures. Homogeneous structures and their automorphism groups constitute the main theme of the thesis. The automorphism group of a countably infinite structure becomes a Polish group when endowed with the pointwise convergence topology. Thus, using Baire Category one can formulate the following notions. A Polish group has generic automorphisms if it contains a comeagre conjugacy class. A Polish group has ample generics if it has a comeagre diagonal conjugacy class in every dimension. To study automorphism groups of homogeneous structures as topological groups, we examine combinatorial properties of the corresponding amalgamation classes such as the extension property for partial automorphisms (EPPA), the amalgamation property with automorphisms (APA), and the weak amalgamation property. We also explain how these combinatorial properties yield the aforementioned topological properties in the context of homogeneous structures. The main results of this thesis are the following. In Chapter 3 we show that any free amalgamation class over a finite relational language has Gaifman clique faithful coherent EPPA. Consequently, the automorphism group of the corresponding free homogeneous structure contains a dense locally finite subgroup, and admits ample generics and the small index property. In Chapter 4 we show that the universal bowtie-free countably infinite graph admits generic automorphisms. In Chapter 5 we prove that Philip Hall's universal locally finite group admits ample generics. In Chapter 6 we show that the universal homogeneous ordered graph does not have locally generic automorphisms. Moreover we prove that the universal homogeneous tournament has ample generics if and only if the class of finite tournaments has EPPA.

Given a network N, and a collection V of unordered pairs of vertices in N, a corresponding uniform multicommodity flow F of volume φ consists of simultaneous flows of volume φ of unique commodities between each pair of vertices in V. The maximum uniform flow volume is the maximum value of φ such that there is a uniform multicommodity flow of volume φ in N, 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 V is the collection of all unordered pairs of vertices. Another very natural example is the d-dimensional (hyper)cube Qd, 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.

This thesis examines graph-theoretic approaches to problems arising in emitter- to-platform association, for example in associating emitters and ships. The first part of this thesis focuses on emitters that are observed by two different sensors, which can only determine the bearing the observed signal was emitted from. The aim is to pair observations from the two sensors, that originate from the same emitter. In this thesis it is shown that different types of observations can be represented as one of c colours and each observed bearing as a row or a column in an n by n grid. Given the horizontal and vertical projections of a coloured grid, the aim is to reconstruct the original layout of the coloured squares on the grid. Deciding whether two sets of positive natural numbers are the horizontal and vertical projections of a coloured grid is NP-complete for two or more colours [24, 35, 47] and has close connections to colour degree matrix problems. Necessary and sufficient conditions are known for a demand matrix to be a colour degree matrix of an edge-coloured forest [9, 22]. In this thesis the first step beyond forests is taken: necessary and sufficient conditions for a demand matrix to be realisable by a graph with at most one cycle are proved. As part of the proof some directly forced structures are discovered, that is, structures that must exist in every realisation. Moreover, corresponding results for multi-graphs and pseudoforests with at most k cyclic components are presented. This part concludes with O (n2 ) time algorithms to check these conditions and return a witness if one of the conditions is violated. Finally O(n3) time algorithms to find a realisation, if one exists, are described. The second part of this thesis introduces the coloured L-model. This is an original idealised graph model, developed to explore the combinatorial properties of the emitter-to-platform association problem, referred to as the reverse radar problem in this thesis. The aim is to decide which groups of observed radars originate from the same ship, taking into account which combinations of radar models are known to be carried by different types of ships. It is shown what exactly makes finding a solution to this idealised version of the reverse radar problem NP-hard, and that there are tractable cases equivalent to finding (weighted) matchings in related graphs, which have bounded pathwidth. Restricting to graphs with bounded pathwidth is a reasonable simplification, as signals come in along bearings (i.e. along a cycle) and a cycle has pathwidth two. New algorithms to find (weighted) matchings in graphs with bounded pathwidth and treewidth are presented, which can be used to solve the reverse radar problem in this model. Finally, the likelihood and two-time models are introduced, which complement the coloured L-model by generalising measurement errors and by introducing time. It is shown that the problem remains NP-hard, even for very simple cases and some tractable cases are described.