Engineering: Reportshttp://hdl.handle.net/10092/6112016-05-26T22:59:15Z2016-05-26T22:59:15ZWild triangles in 3-connected matroidsOxley, J.Semple, C.Whittle, G.http://hdl.handle.net/10092/122062016-05-26T15:00:59Z2006-01-01T00:00:00ZWild triangles in 3-connected matroids
Oxley, J.; Semple, C.; Whittle, G.
Tutte's Triangle Lemma proves that if {a, b, c} is a triangle in a 3-connected matroid and neither M\a nor M\b is 3-connected, then M has a triad that contains a and exactly one of b and c. Hence {a, b, c} is contained in a fan of M with at least four elements. In this paper we ask for a somewhat stronger conclusion. When is it that, for each t in { a, b, c}, either M\t is not 3-connected, or M\t has a 3-separation that is not equivalent to a 3-separation induced by M? The main result describes the structure of M relative to { a, b, c} when this occurs. This theorem generalizes a result of Geelen and Whittle for sequentially 4-connected matroids. The motivation for proving this result was for use as an inductive tool for connectivity results aimed at representability questions. In particular, Geelen, Gerards, and Whittle use it in their proof of Kahn's Conjecture for 4-connected matroids.
2006-01-01T00:00:00ZComputing the minimum number of hybridisation events for a consistent evolutionary historyBordewich, M.Semple, C.http://hdl.handle.net/10092/122052016-05-26T15:00:57Z2004-01-01T00:00:00ZComputing the minimum number of hybridisation events for a consistent evolutionary history
Bordewich, M.; Semple, C.
It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events such as hybridisations mean that species are a mixture of genes from different ancestors. Since such events are relatively rare, a fundamental problem for biologists is to determine the smallest number of hybridisation events required to explain a given (input) set of data in a single (hybrid) phylogeny. The main results of this paper show that computing this smallest number is both NP-hard and APX-hard in the case the input is a collection of phylogenetic trees on sets of present-day species. This answers a problem which was raised at a recent conference. As a consequence of these results, we also correct a previously published NP-hardness proof in the case the input is a collection of binary sequences, where each sequence represents the attributes of a particular present-day species. The NP and APX-hardness of these problems mean that it is unlikely that there is an efficient algorithm for either computing the result exactly, or approximating it to any arbitrary degree of accuracy.
2004-01-01T00:00:00ZThe structure of equivalent 3-separations in a 3-connected matroidHall, R.Oxley, J.Semple, C.http://hdl.handle.net/10092/122042016-05-26T15:01:03Z2004-01-01T00:00:00ZThe structure of equivalent 3-separations in a 3-connected matroid
Hall, R.; Oxley, J.; Semple, C.
Let M be a matroid. When M is 2-connected, Cunningham and Edmonds gave a tree decomposition of M that displays all of its 2-separations. This result was extended by Oxley, Semple, and Whittle, who showed that, when M is 3-connected, there is a corresponding tree decomposition that displays all non-trivial 3-separations of M up to a certain natural equivalence. This equivalence is based on the notion of the full closure fcl(Y) of a set Y in M, which is obtained by beginning with Y and alternately applying the closure operators of M and M* until no new elements can be added. Two 3-separations (Y₁, Y₂) and (Z₁, Z₂) are equivalent if {fcl(Y₁),fcl(Y₂)} = {fcl(Z₁), fcl(Z₂)}. The purpose of this paper is to identify all the structures in M that lead to two 3-separations being equivalent and to describe the precise role these structures have in determining this equivalence.
2004-01-01T00:00:00ZUsing graphical modelling in official statisticsPenny, R. N.Reale, M.http://hdl.handle.net/10092/122012016-05-26T15:01:00Z2004-01-01T00:00:00ZUsing graphical modelling in official statistics
Penny, R. N.; Reale, M.
People using economic time series would like them to be available as soon as possible after the end of the reference period. However there can be difficulties in getting all the responses required to produce a series of acceptable quality in a timely manner. The earlier the time series is released the more likely there will be tardy respondents, thus the series will have to be estimated without their responses. As QGDP is the aggregation of a large number of economic time series the difficulties are compounded.
An adequate preliminary estimate of QGDP may be made by using models parsimonious in the number of time series involved. Graphical models assist us in obtaining such parsimonious models by identifying the relevant components in a saturated structural VAR enabling us to eliminate unnecessary delays. Even if an earlier release is not possible we could target work to improve the timeliness of series identified in the parsimonious models.
2004-01-01T00:00:00Z