

Contemporary Problems in Number Theory
September 1, 2011 12:45, Moscow, Steklov Mathematical Institute, Room 530 (8 Gubkina)






Telling graph properties from its largest eigenvalue
V. F. Lev^{} 
Number of views: 
This page:  81 

Abstract:
The spectrum is an important characteristic of a graph, encoding many of its intrinsic properties. In this talk we give an interpretation to the maximal eigenvalue of a graph (also known as its “spectral radius”), showing that it is equal, up to a logarithmic factor, to the quantity
$$
\max_{X,Y}\frac{e(X,Y)}{\sqrt{XY}},
$$
where the maximum is taken over all pairs of (nonempty, not necessarily disjoint) subsets of the vertex set of the graph, and $e(X,Y)$ denotes the number of edges between $X$ and $Y$.

