NETWORKS
Day 2 (Wednesday 20 April) @ 11:30–13:00
Noela Müller (TU Eindhoven)
The full rank condition for sparse random matrices
The presentation is on a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. The result covers both matrices over finite fields with independent non-zero entries and {0,1}-matrices over the rationals. The sufficient condition is generally necessary as well. This is joint work with Amin Coja-Oghlan, Pu Gao, Max Hahn-Klimroth, Joon Lee and Maurice Rolvien.
Viresh Patel (University of Amsterdam)
Computational counting and zeros of graph polynomials
In recent decades there has been a lot of interest in efficient algorithms to (approximately) count fundamental objects in graphs such as independent sets or proper k-colourings. More generally, these counting problems have associated generating polynomials (the independence polynomial for independent sets and the chromatic polynomial for proper k-colourings), and one is also interested in efficient approximation algorithms to evaluate these polynomials at different points. I will give an overview of a relatively recent technique called Taylor polynomial interpolation for designing these counting algorithms. We will see an intimate (but not fully understood) connection between computational complexity of counting problems and the locations of zeros of the associated counting polynomials.
Rajat Hazra (Leiden University)
Spectrum of inhomogeneous Erdős-Rényi random graphs
The talk is on inhomogeneous Erdős-Rényi random graphs. The eigenvalues of the adjacency and Laplacian matrix of the graph are studied. The empirical spectral distribution of the matrix after suitable scaling and centering is shown to have a deterministic limit in probability. Depending on the rank of the inhomogeneity kernel generating the random graph, the largest few eigenvalues have a much higher magnitude than that of the bulk. Assuming the rank to be finite, the second order behaviour of those few eigenvalues, after suitable centring and scaling, is shown to be multivariate Gaussian. We also describe the behaviour of the eigenvectors corresponding to the largest eigenvalue.
