Name
Abstract | ||
|---|---|---|
Let A=(aij)i,j=1n be a Hermitian matrix of size n⩾2, and set ρ(A)=1n2∑i,j=1naij,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)⩽C1disc(A)lognfor 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))⩾C2disc(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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.disc.2004.05.006 | Discrete Mathematics |
Keywords | Field | DocType |
Discrepancy,Graph eigenvalues,Second singular value,Pseudo-random graphs,Quasi-random graphs | Adjacency matrix,Graph theory,Binary logarithm,Graph,Discrete mathematics,Combinatorics,Singular value,Multiplicative function,Regular graph,Hermitian matrix,Mathematics | Journal |
Volume | Issue | ISSN |
285 | 1 | 0012-365X |
Citations | PageRank | References |
13 | 1.06 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Béla Bollobás | 1 | 2696 | 474.16 |
| Vladimir Nikiforov | 2 | 124 | 20.26 |