Discrete Mathematics Seminar

The Discrete Mathematics Seminar at York University, organized by Harmony Zhan and me (Justin Troyka), meets on Wednesdays at 11:00–12:00 in Ross N638, every 1 or 2 weeks. Our next meeting is on Wednesday December 4. Here are talks from previous years. Contact Harmony (h3zhan@yorku.ca) or me (jmtroyka@yorku.ca) if you would like to give a talk!

Date Speaker Title Abstract
Nov 6 Krystal Guo, Université de Montréal Inverses of Trees A tree is invertible if and only if it has a perfect matching. Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix has entries in {0, ±1} and is the signed adjacency matrix of a graph which contains T. In this talk, we give a new proof of this theorem, which gives rise to a partial ordering relation on the class of all invertible trees on 2n vertices. In particular, we show that given an invertible tree T whose inverse graph has strictly more edges, we can remove an edge from T and add another edge to obtain a non- isomorphic invertible tree T whose median eigenvalue is strictly greater. This extends naturally to a partial ordering. We characterize the maximal and minimal elements of this poset and explore the implications about the median eigenvalues of invertible trees.
Nov 13 (No meeting)
Nov 20 Harmony Zhan, York University Equiangular lines and covering graphs A set of lines in a Hilbert space is called equiangular if any two lines make the same angle. Despite decades of study, in general, we do not know how many equiangular lines we can pack in a given dimension. However, there is a well known connection between real equiangular lines and double covers of graphs, as established in the 70s. I will discuss this correspondence and its generalization to the complex case. The latter is joint work with Coutinho, Godsil and Shirazi.
Nov 27 (No meeting)
Dec 4 Justin Troyka, York University The cycle lemma In this talk, which is mostly expository, I will present a cluster of related ideas that have arisen in combinatorics in the last few decades, concerning the arrangement of combinatorial objects into a cycle structure. The enumeration of these cycles is linked to that of the constituent objects via logarithmic differentiation. Applications include enumeration of lattice paths (such as those that give rise to the Catalan numbers), enumeration of various kinds of trees, and combinatorial proof of the Lagrange Inversion Formula. I will also describe how this combinatorial relation has arisen in my current work with Neal Madras on pattern-avoiding affine permutations.