Location: MF 12

Speaker: Alexander van Werde (TU/e)

Title: Cokernel statistics of walk matrices: towards generalized spectral determinacy of random graphs

Abstract:
Spectral graph theory studies how the spectrum of a graph can reveal its structure.  To probe the fundamental limits of this discipline, one may wonder whether the isomorphism class of a graph can be recovered based on spectral information. For instance, we would like to know the probability that a random graph is determined by its generalized spectrum, which consists of the adjacency spectra of the graph and its complement.

Deterministic criteria for generalized spectral determinacy are known due to Wang and Xu (2006, 2017) and can be stated in terms of the walk matrix of the graph, but it is not known how frequently those criteria are satisfied. This talk concerns a new line of attack which could be used to determine the frequency of satisfaction. More specifically, I develop a connection to category-theoretic proof techniques which originate in combinatorial random matrix theory.  The results concern the limiting law of the cokernel of the walk matrix, both as an Abelian group and as a Z[x]-module.

Based on arXiv:2401.12655.