ILAS 2022


ILAS 2022 Meeting: Invited Mini-Symposium on
Distance matrices of graphs

June 20–24, 2022, National University of Ireland, Galway

Last modified on May 13, 2022

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

21 Jun (Tue),   10:30 Aida Abiad
21 Jun (Tue),   11:00 Projesh Nath Choudhury
21 Jun (Tue),   11:30 Carlos Alejandro Alfaro Montufar
21 Jun (Tue),   12:00 Lorenzo Ciardo
23 Jun (Thu),   10:30 Leslie Hogben
23 Jun (Thu),   11:00 Carolyn L. Reinhart
23 Jun (Thu),   11:30 Krishnan Sivasubramanian



Titles and Abstracts


Aida Abiad, Eindhoven University of Technology (Netherlands) and Ghent University (Belgium) 21 Jun (Tue),   10:30
Extending a conjecture of Graham and Lovász on the distance characteristic polynomial Venue: TBA

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.


Projesh Nath Choudhury, Indian Institute of Science (India) 21 Jun (Tue),   11:00
Blowup-polynomials of graphs Venue: TBA

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.)


Carlos Alejandro Alfaro Montufar, Banco de México (Mexico) 21 Jun (Tue),   11:30
Distance ideals of graphs Venue: TBA

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).


Lorenzo Ciardo, University of Oxford (UK) 21 Jun (Tue),   12:00
Two moments for trees Venue: TBA

Abstract. The moment of a force $\textbf{F}$ applied to a point particle having distance $\textbf{d}$ from a fixed fulcrum is the cross product $\textbf{d}\times \textbf{F}$. We consider two graph-theoretic versions of this notion, of different nature: Given a rooted tree $T$, its combinatorial moment $\mu$ is given by the sum over each vertex $v$ of the distance of $v$ from the root times the degree of $v;$ its spectral moment $\rho$ is the largest eigenvalue of a square matrix encoding the "common distance" from the root of pairs of vertices in $T$. The features of both these parameters resemble those of their physical counterpart. Therefore, they share a similar behaviour with respect to elementary constructions on trees. This allows us to show that $\mu$ is essentially an upper bound for $\rho$, and the ratio $\mu /\rho$ is at most linear in the order of $T$; specific classes of trees having a fractal structure allow to conclude that $\mu /\rho$ is in fact unbounded in general.

Interestingly, both $\mu$ and $\rho$ are closely linked to connectivity notions for graphs – Kemeny's constant $\kappa$ and algebraic connectivity $\alpha$, respectively. As a consequence, the quantitative comparison between the two moments promises to shed some light on the still shadowy relation between $\kappa$ and $\alpha$.


Leslie Hogben, American Institute of Mathematics and Iowa State University (USA) 23 Jun (Thu),   10:30
Spectra of Variants of Distance Matrices of Graphs Venue: TBA

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).


Carolyn L. Reinhart, Swarthmore College (USA) 23 Jun (Thu),   11:00
The distance matrix and its variants for digraphs Venue: TBA

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).


Krishnan Sivasubramanian, Indian Institute of Technology at Bombay (India) 23 Jun (Thu),   11:30
The 2-Steiner distance matrix of a tree Venue: TBA

Abstract. Let $T$ be a tree with vertex set $V(T) = \{ 1, 2, \dots, n\}$. The Steiner distance of $S \subseteq V(T)$ of vertices of $T$ is defined to be the number of edges in a smallest connected subtree of $T$ that contains all the vertices of $S$. The $k$-Steiner distance matrix $\mathfrak{D}_k(T)$ of $T$ is an $\binom{n}{k} \times \binom{n}{k}$ matrix whose rows and columns are indexed by subsets of vertices of size $k$. The entry in the row indexed by $P$ and column indexed by $Q$ is equal to Steiner distance of $P \cup Q$. When $k=1$, it is easy to see that we have $\mathfrak{D}_1(T)=D(T)$, the distance matrix of $T$ which is a well studied matrix. In this work, we consider the next case, that is when $k=2$. We show that rank$(\mathfrak{D}_2(T))=2n-p-1$, where $p$ is the number of pendant vertices (or leaves) in $T$. We construct a basis $\mathfrak{B}$ for the row space of $\mathfrak{D}_2(T)$ and obtain a formula for the inverse of the nonsingular square submatrix $\mathfrak{D} = \mathfrak{D}_2(T)[\mathfrak{B}, \mathfrak{B}].$ We also compute the determinant of $\mathfrak{D}$ and show that its absolute value is independent of the structure of $T$ and apply it to obtain the inertia of $\mathfrak{D}_2(T)$.

This is joint work with Ali Azimi (Iran).