Lonesum Matrices and Acyclic Orientations: Enumeration and Asymptotics by Professor Jessica Khera
This is a past event.
Thursday, March 10 at 3:45pm to 5:00pm
DM - Deuxieme Maison, 409A
11200 SW 8th ST 33199, Deuxieme Maison, Miami, Florida 33199
An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes.
Join Zoom Meeting
Meeting ID: 925 0916 1937