Discrete Math Seminar

List of Seminar Presentations

09/22: Andrew Ray

Festoon Trees

Among trees on n vertices and some bounded degree, there is a unique tree maximizing the number of independent sets, minimizing the number of matchings, and minimizing the energy. All three of these extremal trees happen to be the same. We will discuss the interesting structure of this class of trees, and an interesting system of numeration that arises from these trees.

(no notes available)

09/15: Katie Johnson

Counting Lower Hessenberg Matrices

Oftentimes it is interesting to study sets of matrices that have a certain zero pattern. In linear algebra, knowing that a matrix is triangular or diagonal is extremely helpful in computing the determinant or determining eigenvalues, as well as determining whether certain other properties, such as singularity, hold. In combinatorics, we may take a very different approach by counting the number of matrices that follow a specific zero pattern under various restrictions. In my talk, I will present some work I did as an undergraduate studying matrices with the Hessenberg zero pattern and unraveling the beautiful structure these matrices exhibit.

(no notes available)

09/08: Stephen G. Hartke

Packings of degree sequences

I will continue the theme of packing realizations of degree sequences discussed by Tyler last week. Specifically, I will discuss a "potential" version of the Sauer-Spencer theorem and extensions to Kundu's theorem.

(notes)

09/01: Tyler Seacrest

A packing problem and a potential packing problem

Packing problems are very common in math, in computer science, and on vacations! In graph theory, we say that two n vertex graphs G and H pack if they can be placed on the same n vertices without any edges overlapping. I will cover a proof of one of the first major results in this area due to Sauer and Spencer in 1978, which states that if twice the product of the maximum degrees of each graph is less than n, then the two graphs pack. I will then move on to a Kundu's k-factor theorem, which can be seen as a "potential" version of the packing problem.

(notes)

08/25: Christine Kelley

Organizational meeting/ a graph-theoretic approach to designing hash functions

This will primarily be an organizational meeting of the discrete math seminar for the year, and also give us the opportunity to meet the new graduate students interested in discrete math. Following this, we will introduce cyptographic hash functions and a graph-theoretic design strategy for these functions.

(notes)