Invited Paper Session Abstracts - Eigenvalues and Graphs

In this talk, I will discuss some combinatorial and spectral properties of the associahedron graph. Its vertices the triangulations of a convex \(n-gon\) by \(n − 3\) non-crossing diagonals and two triangulations are adjacent if they differ by one diagonal flip or they share \(n − 4\) diagonals.

Given a graph \(G\), the exponential distance matrix is defined entry-wise by letting the \((u, v)−entry\) be \(q dist(u,v)\), where \(dist(u, v)\) is the distance between the vertices \(u\) and \(v\) with the convention that if vertices are in different components, then \(q dist(u,v) = 0\). We establish several properties of the characteristic polynomial (spectrum) for this matrix, give some families of graphs which are uniquely determined by their spectrum, and produce cospectral constructions.

In this talk, we introduce a Fielder vector, which is used for the graph partitioning problem, to partition a graph (according to its sign pattern) into two connected subgraphs that are similar in size. Our work is motivated by graphs having Fiedler vectors with unbalanced sign patterns such that a partition can result in two connected subgraphs that are distinctly different in size. A characterization of graphs having a Fiedler vector with exactly one negative component is presented, and some classes of such graphs are shown. In particular, we describe graphs such that any Fiedler vector has only either one negative or one positive sign.

In the same way that Brownian motion can be modelled by random walks, the movement of quantum particles can be modelled by quantum walks. Consequently, there is a close relationship between algorithms that run on quantum computers and quantum walks on graphs. Given a graph and an associated Hermitian matrix (such as the adjacency matrix or Laplacian matrix), a quantum walk is defined by an exponential function of the matrix, and thus an exponential function on the eigenvalues of the matrix. In this talk, we will give an overview of quantum walks on graphs, focusing on the behaviors that set them apart from their classical counterparts and spectral characterization of such behaviors.

Let \(ex(n, F)\) be the maximum number of edges in an \(F\)-free graph on n vertices and \(spex(n, F)\) be the maximum spectral radius (of the adjacency matrix) of an \(F\)-free graph on \(n\) vertices. In this talk we discuss a conjecture regarding for which graphs \(F\) the extremal graphs for these two problems are the same. This is motivated by a recent theorem of ours which determines \(spex(n, F)\) when \(F\) is a friendship graph. This is joint work with Sebi Cioaba, Lihua Feng, and Xiao-Dong Zhang.