Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The structure of the cycles of a graph is a well-studied topic with deceivingly simple open questions. For example, the Double Cover Conjecture claims that there is a family of cycles such that every edge of a bridgeless graph is contained in exactly two cycles. A linear-algebraic view of the problem is a natural point of view. Considering every cycle as an indicator vector, we explore the lattice $L_G$ generated by the cycles of an undirected graph, defined as the integer linear combinations of the 0/1-incidence vectors of cycles. This linear algebraic perspective has been applied historically to model combinatorial problems on directed graphs with great success (in some textbooks), whereas the undirected edge case less so. In this talk, we present structural results for the lattice $L_G$, including explicit formulas for its dimension and determinant, and we present a quadratic time algorithm to construct lattice bases, using only cycles as generators.

This is joint work with Gennadiy Averkov, Jesus De Loera, and Bryan Gillespie. Our paper is available on the ArXiv.

Slides for Anastasia's talk can be found at Chavez-Mar4-LatVecSpaceAndGraphs.pdf

Please contact mjvazirani@ucdavis.edu if you need the Zoom link/password (or see hint above). Zoom: 994 0826 8795