|
This is a local page for the invited Minisymposium on "Distance matrices
of graphs", at the 2022 meeting of the
International Linear
Algebra Society (ILAS). The Minisymposium takes place on
June 21 (Tue) and 23 (Thu).
The organizers are: Projesh Nath Choudhury and Apoorva Khare.
For information on hotels, and registration,
click on the ILAS 2022 logo at the top of this page.
Distance matrices associated to graphs have been explored intensively
in the literature for several decades now, both from an algebraic and a
spectral viewpoint. They have connections to graph embeddings,
communications networks, and quantum chemistry among other areas. This
minisymposium will bring together researchers working on distance
matrices from a variety of perspectives, and discuss modern approaches
and recent results.
Speakers
|
|
| Abstract.
Graham and Lovász conjectured in 1978 that the sequence of
normalized coefficients of the distance characteristic polynomial of a
tree is unimodal with the maximum value occurring at $\lfloor \frac{n}{2}
\rfloor$ for a tree $T$ of order $n$. We extend this old conjecture to
block graphs. In particular, we prove the unimodality part and we
establish the peak for several extremal cases of block graphs.
This is joint work with B. Brimkov, S. Hayat, A. Khramova and J. Koolen.
|
|
| Abstract.
Given a finite simple connected graph $G=(V,E)$ (or even a finite metric
space), we introduce a novel invariant which we call its
blowup-polynomial $p_G(n_v : v \in V)$. To do so, we compute the
determinant of the distance matrix of the graph blowup, obtained by
taking $n_v$ copies of the vertex $v$, and remove an exponential factor.
First: we show that as a function of the sizes $n_v$, $p_G$ is a
polynomial, is multi-affine, and is real-stable. Second: we show that the
multivariate polynomial $p_G$ fully recovers $G$. Third: we obtain a
novel characterization of the complete multi-partite graphs, as precisely
those whose "homogenized" blowup-polynomials are Lorentzian/strongly
Rayleigh. (Joint with Apoorva Khare.) |
|
| Abstract.
Distance ideals of graphs generalize, among other graph parameters, the
spectrum and the Smith normal form (SNF) of distance and distance
Laplacian matrices. In particular, they allow us to introduce the notion
of codeterminantal graphs, which generalize the concepts of cospectral
and coinvariant graphs. We show computational results on codeterminantal
graphs up to 9 vertices. Although the spectrum of several graph matrices
has been widely used to determine graphs, the computational results
suggest that the SNF of the distance Laplacian matrix seems to perform
better for determining graphs. Finally, we show that complete graphs and
star graphs are determined by the SNF of its distance Laplacian
matrix.
This is joint work with Aida Abiad (Eindhoven University of Technology
and Ghent University), Kristin Heysse (Macalester College), Libby Taylor
(Stanford University) and Marcos C. Vargas (Banco de México).
|
|
|
Abstract.
In the last ten years, variants of the distance matrix of a graph, such
as the distance Laplacian, the distance signless Laplacian, and the
normalized distance Laplacian matrix of a graph, have been studied. This
talk compares and contrasts techniques and results for these four
variants of distance matrices. New results are obtained by cross-applying
techniques from one variant of the distance matrix to another are
presented.
This is joint work with Carolyn Reinhart (Swarthmore).
|
|
|
Abstract.
A directed graph, or digraph, is a graph in which edges are replaced by
directional arcs. While the distance matrix and its variants are
symmetric matrices when defined on graphs, these matrices are not
necessarily symmetric on digraphs. Thus, some of the techniques used in
the graph case no longer apply. This talk will discuss techniques used to
study distance matrices for digraphs and some results they have yielded.
New results regarding cospectrality for the distance matrix of digraphs
will also be presented.
This is joint work with Leslie Hogben (Iowa State University and AIM).
|
|
