CMD_11

Welcome to the Department of Mathematics

What's Happening This Week In Mathematics....

 

file

Upcoming Events

  • Daryl Funk, Ph.D. Thesis Defence, Mathematics Room K9509 Burnaby Campus
    10:00 AM - 12:30 PM
    January 8, 2015
    (Sr. Supervisor: Matt DeVos) (Co-Supervisor: Luis Goddyn) Title: On Excluded Minors and Biased Graph Representations of Frame Matroids Abstract: A biased graph is a graph in which every cycle has been given a bias, either balanced or unbalanced. Biased graphs provide representations for an important class of matroids, the frame matroids. As with graphs, we may take minors of biased graphs and of matroids, and a family of biased graphs or matroids is minor-closed if it contains every minor of every member of the family. For any such class, we may ask for the set of those objects that are minimal with respect to minors subject to not belonging to the class — i.e., we may ask for the set of excluded minors for the class. A frame matroid need not be uniquely represented by a biased graph. This creates complications for the study of excluded minors. Hence this thesis has two main intertwining lines of investigation: (1) excluded minors for classes of frame matroids, and (2) biased graph representations of frame matroids. Trying to determine the biased graphs representing a given frame matroid leads to the necessity of determining the biased graphs representing a given graphic matroid. We do this in Chapter 3. Determining all possible biased graph representations of non-graphic frame matroids is more di cult. In Chapter 5 we determine all biased graphs representations of frame matroids having a biased graph representation of a certain form, subject to an additional connectivity condition. Perhaps the canonical examples of biased graphs are group-labelled graphs. Not all biased graphs are group-labellable. In Chapter 2 we give two characterisations of those biased graphs that are group labellable, one topological in nature and the other in terms of the existence of a sequence of closed walks in the graph. In contrast to graphs, which are well-quasi-ordered by the minor relation, this characterisation enables us to construct infinite antichains of biased graphs, even with each member on a fixed number of vertices. These constructions are then used to exhibit infinite antichains of frame matroids, each of whose members are of a fixed rank. In Chapter 4, we begin an investigation of excluded minors for the class of frame matroids by seeking to determine those excluded minors that are not 3-connected. We come close, determining a set E of 18 particular excluded minors and drastically narrowing the search for any remaining such excluded minors. Keywords: Frame matroid; biased graph; excluded minors; representations; group-labelling; gain graph; well-quasi-ordering; lift matroid; graphic matroid
  • Operations Research Seminar: Michael Armstrong
    2:30 PM - 3:30 PM
    January 8, 2015
    Title: Salvo Models for Missile Combat Abstract: Modern surface warships attack and defend using guided missiles such as the Harpoon and Standard. Because few battles have been fought this way, missile combat is not as well understood as that involving gunfire. Salvo models provide a simple way to represent such battles, much as Lanchester models represent gunfire battles. This talk will introduce salvo combat models, describe some of their properties, and demonstrate their application to the carrier airstrikes of the 1942 Battle of the Coral Sea.
  • Ashok Rajaraman, Ph.D. Thesis Defence, Mathematics Room: SCK9509
    10:30 AM - 12:30 PM
    January 15, 2015
    (Sr. Supervisor: Cedric Chauve) Title: Variants of the Consecutive Ones Property: Algorithms, Computational Complexity and Applications to Genomics Abstract: Genome mapping problems in bioinformatics can be modelled as problems of finding sequences of vertices in hypergraphs, subject to consecutivity constraints. These problems are related to the consecutive ones property, a well-studied structural property on binary matrices. Many variants of this property have been introduced to include subtleties in the model, such as upper bounds on the number of times a vertex may appear in a sequence, the distance of the input from having the property, and confidence values for the consecutivity constraints. Most problems involving these variants are intractable, and efficient solutions call for restrictions on the structure of the input, exponential time algorithms, or approximations. The following document discusses these problems, from both a theoretical perspective, and from the genomics point of view. We encounter two main classes of problems, divided into models which account for repeated elements in genomes, and those which do not. Orthogonally, we divide the problems into decision and optimization questions. For models with repeats, we discuss when the given input can be used to reconstruct the genome map of interest, and if we can discard a minimal set of encoded consecutivity information from the model to obtain an input which can be used to reconstruct this genome map. We also discuss the problem of ambiguity introduced by repeats, and introduce the concept of repeat spanning intervals in order to address them. We show that the problem of optimizing over the set of repeat spanning intervals is NP-hard in general, and give an algorithm when the intervals are small. In models without repeated elements, we discuss the problem of optimization by finding a solution that minimizes the distortion in the consecutivity information, by generalizing the concepts of bandwidth and minimum linear arrangement to hypergraphs. We design approximation algorithms for two versions of the latter problem, with an approximation ratioof O (√log n log log n). Finally, we provide details of implementations of some of the methods developed for genome mapping and scaffolding on ancestral genomes. We include results on real data for the genome of the Black Death agent, and for ancestral Anopheles mosquitoes. Keywords: consecutive ones property; genome reconstruction; repeat ambiguity; vertex ordering; approximation algorithms
  • Krystal Guo, Ph.D. Thesis Defence, Mathematics Room: K9509
    10:00 AM - 12:00 PM
    January 26, 2015
    (Sr. Supervisor: Bojan Mohar) Title: Simple eigenvalues of graphs and digraphs Abstract: The spectra of graphs and their relation to graph properties have been well-studied. There has been extensive study about the interplay of eigenvalues of a graph and various graph properties, such as the diameter or the chromatic number. For digraphs, in contrast, there are relatively few results. There is a directed analogue of Wilf's bound on chromatic number, however the spectra of digraphs is generally an unexplored area. The adjacency matrix of a digraph is usually difficult to work with; it is not always diagonalizable and the interlacing theorem does not hold (in general) for adjacency matrices of digraphs. All acyclic digraphs have the same spectrum as the empty graph. This motivates the need to work with a different matrix which captures the adjacency of the digraph. To this end, we introduce the Hermitian adjacency matrix. Another way to extract more information out of the spectrum is by restricting to specific classes of digraphs. In this thesis, we look at vertex-transitive digraphs with simple eigenvalues. Intuitively, the property of having many simple eigenvalues tends to coincide with having few automorphisms. For example, the only vertex-transitive graph with all eigenvalues simple is $K_2$. In the case of graphs, we restrict to the cubic vertex-transitive case, where we find combinatorial properties of graphs with multiple simple eigenvalues. We also explore the eigenvectors of vertex-transitive digraphs with all eigenvalues distinct.
  • Download .ics