Sandbox:DavidKohler/Alon try 1/Rayleigh quotient

Rayleigh quotients offer an efficient tool to estimate the first and second largest eigenvalues of a graph by choosing suitable functions on the vertices of the graph.

Definition

Let G be a graph and denote by A_G its adjacency matrix. Let f be a real function on the vertices of the graph G, we define its Rayleigh quotient to be the real number R_A(f) defined by:

$R_{A}(f)={\frac {<Af,f>}{<f,f>}}$

with respect to the usual scalar product <f,g > of two functions f and g over the vertices V_G of a graph G is defined by:

$<f,g>=\sum _{v\in V_{G}}f(v)g(v)$

Properties

Denote by 1_X the characteristic function of the set X of vertices of a graph G. Then the Rayleigh quotient of this characteristic function is twice the ratio of edges in the subgraph induced by the vertices in the set X to its number of vertices.

More generally, if X and Y are two subsets of vertices, then <A1_X, 1_Y is the sum of the number of edges in the subgraph induced by X∪Y and the number of edges in the subgraph induced by X∩Y.