Algebraic Graph Theory Seminar - Paul Horn

Title: Graphs, curvature, and local discrepancy

Abstract: Spectral graph theory, the use of eigenvalues to study graphs, gives an important window into many properties of graphs.  One of the reasons for this is that the eigenvalues can be used to certify the `pseudo-randomness' of the edge set of a graph.  In recent years, several notions of discrete curvature have been introduced that gives a 'local' way (depending on the neighborhood structure of vertices) to study some of the same properties that eigenvalues can capture.   In this talk, we'll introduce some of the notions of curvature of graphs and, in particular, introduce some newly developed 'discrepancy inequalities.'   These (like eigenvalues) certify pseudo-randomness of an edge set but, in the case of curvature establish a `local pseudo-randomness' of edges within the first few neighborhoods of a vertex.