pipette
ENEnglish

Almost all graphs are determined by their generalized spectrum

Ziqing Xiang

Preprint

En palabras de los autores

Haemers' conjecture for the generalized spectrum asserts that almost all graphs are determined by their generalized spectrum, that is, for almost all graphs , every graph with the same spectrum as whose complement has the same spectrum as the complement of is isomorphic to . We prove this conjecture by showing that the random graph is determined by its generalized spectrum with probability tending to one. The proof combines a local theory of the denominators of the rational orthogonal matrices that relate generalized cospectral graphs, Fourier analysis of random symmetric matrices over finite rings, Seidel switching, inverse Littlewood--Offord theory over finite fields, rank estimates for random symmetric matrices modulo primes, and a study of the rational factors of the characteristic polynomial of a random symmetric matrix with zero diagonal.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.