The graph p-Laplacian eigenvalue problem

In this thesis we discuss the graph p-Laplacian eigenvalue problem. In particular, after reviewing the state of the art, we present new results on the nodal domain count of the p-Laplacian eigenpairs, on the graph infinity-Laplacian eigenproblem, and on the computation of the p-Laplacian eigenpairs. Concerning the nodal domain count, we prove that the number of nodal domains induced by a p-Laplacian eigenfunction can be bounded, both from above and below, in terms of the position of the corresponding eigenvalue in the variational spectrum. Moreover, we prove that on trees the variational spectrum exhausts the entire spectrum, and the number of nodal domains induced by an everywhere nonzero eigenfunction is equal to the variational index of the corresponding eigenvalue. These results allow us to derive, from the p-Laplacian spectrum, topological information about the graph. Indeed, when p is equal to 1 and infinity, the p-Laplacian eigenvalues approximate the Cheeger constants and the packing radii of the graph, respectively. The study of the infinity-Laplacian eigenproblem is another major contribution of this thesis. In particular, we compare different formulations of this degenerate eigenproblem. In the first case we study the infinity-eigenpairs as solutions of the limiting eigenvalue equation, in the second case we define the infinity-eigenpairs as generalized critical points of the infinity-Rayleigh quotient. Then, we relate the infinity variational eigenvalues to the packing radii of the graph. Here, among other things, we prove that the first and the second infinity variational eigenvalues are exactly equal to the first and the second packing radii of the graph. Finally, we present a novel approach to compute the p-Laplacian eigenpairs both in the smooth case 2<p<infinity and in the degenerate case p=infinity. To this end, we observe that the p-Laplacian eigenvalue problem, both for 2<p<infinity and p=infinity, can be reformulated as a constrained linear weighted-Laplacian eigenvalue problem. Based on this remark, we introduce a family of energy functions whose domain is the space of positive measures on the edges and on the nodes of the graph. Then, we first prove that the unique saddle point of the first energy function corresponds to the unique first eigenpair of the p-Laplacian. Second, we prove that smooth saddle points of the k-th energy function correpond to p-Laplacian eigenpairs (f,lambda), such that the Morse index of the p-Rayleigh quotient in f is equal to k. Based on such results, we introduce gradient flows suited to compute saddle points of the proposed energy functions and we discuss the results of their numerical integration. Practically, the integration of the gradient flows, at each step, requires only the computation of a linear eigenpair. Hence we are able to use all the theoretical and numerical advantages of the linear setting to overcome the difficulties of solving a nonlinear equation. However, the theoretical study of the gradient flows remains an open problem, which deserves a future in-depth study.