Georgia Institute of Technology College of Sciences

In the realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. 

Given a Riemannian manifold M, let f be an eigenfunctions f of the Laplacian with respect to some boundary conditions.  A nodal domain associated with f is the maximal connected subset of the domain M  for which the f does not change sign.

Here we examine the discrete cases, namely we consider nodal domains for graphs. Dekel-Lee-Linial shows that for a Erdős–Rényi graph G(n, p), with high probability there are exactly two nodal domains for each eigenvector corresponding to a non-leading eigenvalue.  We prove that with high probability, the sizes of these nodal domains are approximately equal to each other.