Portland State University Discrete Mathematics Seminar

A spanning tree graph is similar to the idea of a line graph: a new graph you can build from an old one. I will reintroduce the idea of spanning tree graphs as well as describe exciting new related findings. Expect lots of pretty pictures.

Trees are an extremely important and useful topic in graph theory and network design. I'll talk about some of the motivation and history of the subject, including Cayley's famous formula that counts the number of spanning trees of a complete graph. Then we'll use that formula to figure out the probability that a randomly chosen subtree of a complete graph is a spanning tree. This is joint work with Alex Chin, Kelly MacPhee, and Charles Vincent, three undergraduates in Lafayette College's REU program last summer.

In this talk I'll review the definition of vertex stability, summarize some of the known results and present and explain my current research on the topic.

The game of SET^® is deeply mathematical. We will first explore some combinatorics in the game. The deck is an excellent model of the finite affine geometry AG(4,3), so we will use the game to aid in the visualization of the structure of the geometry. We will focus on maximal caps, which correspond to largest possible collections of cards with no sets. There is an interesting structure to these caps and to partitions of the geometry into caps. Recent results give more information about these partitions.

In the past decade the volume of biological information available to researchers has exploded. Genetic sequencing experiments routinely produce expression data for thousands of genes in hundreds of cells and conditions. This talk will show how graph theory has become an essential tool to model the interactions between genes, cells, conditions and drugs and highlight some of the many challenges these mathematical tools can help us address. In particular we’ll discuss methods to visualize these large graphs, infer gene interaction networks based on data, and compare networks to background models in order to ascertain functional motifs.

In 1933, three Harvard junior-fellows tied together some recurring themes in mathematics into what Gian Carlo Rota called one of the most important ideas of our day. They were finding independence everywhere they looked. Do you? We find that matroids are everywhere: vector spaces are matroids; we can define matroids on a graph. Matroids are useful in situations that are modeled by both graphs and matrices. We consider how we can ask research questions about matroids, and look into results from a student's investigation.

Two matroids are commonly defined on a graph: the familiar cycle matroid and the more rarely-encountered bicircular matroid. The bases of the cycle matroid are the spanning trees of the associated graph; the bases of the bicircular matroid are all subgraphs of the graph where each connected component contains exactly one cycle and (possibly) other edges. We enumerate the bases of the bicircular matroid for several classes of graphs. For a given graph, usually there are more bases of the bicircular matroid than the cycle matroid. We ask when the reverse is true, and what this translates to in terms of the structure of the graph.

No prior knowledge of matroids or graphs is needed.

There are many natural questions regarding patterns in the prime numbers for which we can say little more than, "Well, it'd be weird if this didn't happen." In this talk, we survey some of these questions — some answered, some open — and we loosely present one of the main tools with which we may battle such conspiracies: the sieve. Of particular note, we will touch upon the remarkable recent work of Zhang, Maynard, Tao, and the Polymath project on "bounded gaps between primes", an approximation to the twin prime conjecture.