Mathematics, Computer Science, and Statistics
The seminar typically meets Fridays from 3:00 until 4:00 in LA 241.
* Special time and place: Wednesday at 4:00 in LA 130
# Special place: LA 126
+ Special time and place: 1:50 in LA 126
Abstracts
Finding Small Identifying Codes is Hard
We describe dominating, locating-dominating, and identifying codes in graphs, with particular attention paid to fault detection and location in sensor networks. We give upper and lower bounds on the number of vertices in an identifying code and show that the bounds can be achieved. We give an efficient algorithm for finding a minimal identifying code and finally show that the problem of finding a minimum identifying code in an arbitrary graph is NP-complete.
Endless Fishbowls and Driving in California
Since an argument can be made that we live in a 3-dimensional manifold, they are of some interest to us. We'll get a brief introduction to 3-manifolds (including the endless fishbowl) and then switch gears and look at a family of graphs, called "freeway diagrams". It turns out, that there is a nice way to tell when two freeway diagrams are not the same that just involves drawing pictures. We'll take a look at this process. What do these two topics have to do with each other? You'll have to come back next week to find out!
Analysis of Discrete Population Models
We will investigate linear and nonlinear discrete population models; and consider stability, bifurcations, and chaos in nonlinear models. We will also analyze linear models for structured populations and nonlinear multi-population models.
Separation Numbers on Chessboard Graphs
It's well-known that at most n queens can be placed on a nxn chessboard so that no two queens attack each other. It's also well-known that it takes at least five queens on an 8x8 board to attack or occupy every square. If we place enough pawns on the board, we can increase or decrease the maximum number of nonattacking queens (the "independence number of the queens graph") or the minimum number of queens needed to dominate the rest of the board (the "domination number of the queens graph"). A separation number is the minimum number of pawns needed to have a given effect on a particular graph-theoretic parameter of a chessboard graph. We consider separation numbers for various chessboard graphs. For example, in order to allow n+k mutually nonattacking queens on an nxn board, we need only put k pawns on that board, if n is sufficiently large.
Your friendly local topological graph theorist
Come one; come all! Investigate the glamorous world of embedding graphs in various topological spaces and question why you might want to do so! Try your hand at embedding graphs in projective planes, on donuts and coffee cups—do I hear a potential audience member suggest that these two surfaces are the same? Just wait until you see my coffee cup!—and in topological spaces that are not surfaces. What? I hear you wonder. Embed a graph in a space that is not a surface? Well, the spine of my book is not locally homeomorphic to the plane, you see.
I will reference to my dissertation work as needed to inspire my audience to see complexity in a newer, simpler light. Newcomers to Graph Theory rejoice! Pictorial representations abound! Notation-dense definitions will not be emphasized. Develop an intuitive understanding of taking minors of a graph, apex vertices, clique-sums, r-rounds, tree decompositions, and a planar-nonplanar decomposition algorithm. See how I put these elements together to prove that any member of a minor-closed class of graphs, other than the class of all graphs, can be embedded in a book with a bounded number of pages, where the bound depends only on the class.
Facility Location: An application of graph theory
Imagine you have to choose the optimal location for a hospital or a shopping mall. How will you make your choice? We will discuss how to use the idea of distance in a simple graph to guide our decision.
A Geometric Appreciation of the Singular Value Decomposition (SVD)
Solving problems involving more than one variable using a computer invariably leads to solving some linear system Ax = b. Computer scientists often focus on the algebraic steps to solve the problem and miss the geometry behind it. In this talk, we will define and discuss the geometric meaning of basic Linear Algebra values including eigenvalues and discriminants, and culminate with a geometric look at the SVD.
