Hermitian matrices and graphs: singular values and discrepancy Original Research Article

Let A=(aij)i,j=1n be a Hermitian matrix of size n⩾2, and set ρ(A)=1n2 ∑i,j=1n aij,disc(A)=maxX,Y⊂[n],X≠∅,Y≠∅ 1|X||Y|∑i∈X ∑j∈Y (aij−ρ(A)).We show that the second singular value σ2(A) of A satisfiesσ2(A)⩽C1 disc(A) log nfor some absolute constant C1, and this is best possible up to a multiplicative constant. Moreover, we construct infinitely many dense regular graphs G such thatσ2(A(G))⩾C2 disc(A(G)) log |G|,where C2>0 is an absolute constant and A(G) is the adjacency matrix of G. In particular, these graphs disprove two conjectures of Fan Chung.