You are here

Invited Paper Session Abstracts - Eigenvalues and Graphs

Friday, July 31, 1:30 p.m. - 4:20 p.m., Philadelphia Marriott Downtown, Grand Ballroom C

Graphs can be used to represent the relations (edges) between objects (vertices), and so play an important role both in theoretical as well as applied settings. One important tool in understanding graphs is through the use of the eigenvalues and eigenvectors of matrices associated with graphs; this is sometimes known as spectral graph theory. There are many possible matrices that can be explored and each one brings its own strengths and weaknesses into understanding graphs. This session will bring together a variety of viewpoints of how eigenvalues and graphs are connected.

Steve Butler, Iowa State University

Spectral and Combinatorial Properties of the Associahedron Graph

1:30 p.m. - 1:50 p.m.
Sebi Cioaba, University of Delaware


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.


The Exponential Distance Matrix

2:00 p.m. - 2:20 p.m.
Kate Lorenzen, Iowa State University


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.


Fiedler Vectors with Unbalanced Sign Patterns

2:30 p.m. - 2:50 p.m.
Sooyeong Kim, University of Manitoba


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.


Quantum Walks on Graphs

3:00 p.m. - 3:20 p.m.
Sabrina Lato, University of Waterloo


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.


A Meta-Conjecture in Spectral Extremal Graph Theory

3:30 p.m. - 3:50 p.m.
Michael Tait, Villanova University


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.