|
|
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: | 200 |
|
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{|X||Y|}},
$$
where the maximum is taken over all pairs of (non-empty, not necessarily disjoint) subsets of the vertex set of the graph, and $e(X,Y)$ denotes the number of edges between $X$ and $Y$.
|
|