This chapter is devoted to various interactions between the graph theory and mathematical physics of disordered media, studying spectral properties of random quantum Hamiltonians. We show how the notions, methods, and constructions of graph theory can help one to solve difficult problems, and also highlight recent developments in spectral theory of multiparticle random Hamiltonians which both benefit from graph‐theoretical methods and suggest original structures where new insights are required from various areas of mathematical physics in a broad sense.
- isoperimetric estimates
- Cheeger bound
- Lifshitz tails
- Anderson localization
- multiparticle localization
- quantum graphs
The proposed chapter focuses on the methods and applications of the graph theory in the area of quantum transport on combinatorial and metric (often referenced to as “quantum”) graphs. It is well known that perfectly periodic potentials in Euclidean spaces or on periodic lattices create favorable conditions for nonlocalized solutions of Schrödinger and/or wave equations. In quantum physics, this results in transport of quantum particles, for example, electrons or phonons. However, after the seminal, Nobel prize winning work  published by Philip W. Anderson in 1958, it has been realized by physicists that the propagation of quantum particles in an imperfect environment, modeled by a random or almost periodic electrostatic or magnetic potential, can be significantly inhibited, to the point where mobile quantum particles, e.g., electrons, are localized: their wave functions decay exponentially away from some loci— their respective localization centers. In many applications, the media where quantum particles propagate are not periodic crystals, but have instead a structure of more or less complex graphs formed by atoms, and therefore are treated as disordered media. The structural disorder can be complemented by a parametric one, e.g., in the context of weighted graphs where the canonical graph Laplacian on is modulated by variable weights assigned to the edges. In general terms of the spectral theory of unordered structures, this is an instance of the “off‐diagonal” disorder. Furthermore, it is important to analyze the spectral properties of the discrete analogs of the Schrödinger operators on a graph , where is a fixed or random real‐valued function on .
The recent wake of interest to the nanosystems and molecular devices attracted many researchers to such models, and numerous intriguing problems in this area still remain challenging and wide open. It has been understood that the classical aspects of the graph theory, such as isoperimetric estimates (particularly, the Cheeger bounds) and deep results of the spectral theory of graphs, are of great importance to the localization/delocalization processes on graphs other than periodic lattices embedded in a Euclidean space.
Furthermore, the most recent developments in the spectral theory of disordered quantum systems, initiated independently and simultaneously by physicists (cf., e.g., ) and mathematicians (cf. [3, 4, 5, 6], emphasized the role of interparticle interaction which had been consciously and explicitly neglected in the pioneering works due to the complexity of the analysis involved, although P. W. Anderson himself was concerned about possible effects of interaction on the fundamental properties of the quantum transport. Following the first mathematical works in this direction, the notion of a multiparticle quantum graph has been recently introduced by Sabri .
Summarizing, the proposed chapter provides to the reader an overview of synthetic techniques and results where the traditional problem of the combinatorial and spectral graph theory is intertwined with complementary structures, ideas, and methods of functional analysis and quantum mechanics, in response to the new challenges in modern technology.
2. Isoperimetric bounds, spectral gaps, and quantum localization
The integer lattices , , endowed with the usual graph structure constitute a very particular class of connected graphs. The spectra and (generalized) eigenfunctions of their canonical graph Laplacians are easy to find, due to the commutative group structure of these lattices. The lattice Laplacian is the canonical Laplacian on endowed with the graph structure where the edges are formed by the pairs with Euclidean distance . It follows from the Fourier analysis on the additive group that the spectral measure of is absolutely continuous (with respect to the Lebesgue measure). The graph Laplacians are defined as nonpositive operators, but in mathematical physics one considers instead. The spectrum of is easily computed, knowing that its Fourier image is the operator of multiplication by the function
The generalized eigenfunctions are given by the respective Fourier harmonics (plane waves) , where . In physics, one often works with finite cubes, where the eigenfunctions of the respective Laplacian are combinations of plane waves. Particular questions concerning the Laplacians relative to such finite graphs depend upon specific intended applications. A number of situations give rise to the quantitative analysis of a few of the lowest eigenvalues of , numbered in increasing order. In particular, the spectral gap and the analytic form of the eigenfunctions with eigenvalues and , known explicitly for the rectangles, are more difficult to analyze for general graphs. One possible question is about the size of the gap : it features a power‐law decay as the size of the cube grows, but what can one say about the spectral gap for less regular graphs? Furthermore, it is readily seen that the eigenvalue is degenerate on the cube, and has multiplicity equal to the dimension : the respective eigenfunctions are the lowest‐frequency harmonics, related to the global geometry of the cube, but the situation for general graphs is more complex.
Before going to the answers, provided by the graph theory for a large class of nonperiodic graphs, we give some motivations coming from the spectral theory of random operators.
One remarkable phenomenon relative to disordered media was discovered in the 1960s by physicist I.M. Lifshitz  and colorfully called in the physics and mathematics communities “Lifshitz tails”: the eigenvalue distribution of the random operators decays extremely as the energy approaches the lower edge of spectrum.
In this chapter, we always assume the random potential to take i.i.d. (independent and identically distributed) values. In addition, we assume the common probability distribution of these random values to admit a bounded probability density.
We shall use the following notions and notations. Given a potential , we consider the discrete Schrödinger operator , where is the graph Laplacian on the integer lattice . Further, for each integer and a lattice point denoted by the cube centered at of side length , and let be the Schrödinger operator in the cube ; here, is the canonical graph Laplacian in with the graph structure inherited from the integer lattice, where the edges are given by the pairs of nearest neighbours in the Euclidean distance. Next, denote by the eigenvalues of numbered in increasing order, and introduce the finite‐volume eigenvalue counting function
Definition 1. The limiting eigenvalue distribution function of the operator is the limit
whenever it exists. Otherwise, we say that the limiting distribution function does not exist.
In the case where a fixed potential is replaced by a sample of a random field on the lattice, the operator also becomes random.
In physical terminology, widely used also in mathematical physics of disordered media, is usually called the integrated density of states (IDS). The existence of the above limit is not obvious and, generally speaking, the limit may not exist. However, the existence of for any energy can be established by the methods of ergodic theory in a particular, but very rich and useful for physical applications class of ergodic operators (including all i.i.d. potentials), as well as for the periodic and almost‐periodic potentials. In fact, the latter classes can be incorporated into the general scheme of ergodic operators; cf., e.g., the monographs [9, 10]. Moreover, the IDS for ergodic potentials is nonrandom; in physical terminology, IDS is a “self‐averaging” quantity. Simply put, spatial average coincides with the ensemble average for ergodic operators.
Whenever the potential of the Schrödinger operator is lower bounded, e.g., nonnegative, and its spectrum have the same property, sinceis nonnegative. Therefore, . In physics, is called the ground state energy. A number of important quantities and phenomena are related to the ground state energy and also to the behavior of the IDS as the energy approaches . Lifshitz  discovered that for a large class of Hamiltonians with random potential energy, including random Schrödinger operators on a lattice, the IDS decays very fast as : for some
Lifshitz tails have numerous important ramifications in theoretical and experimental physics. They also result in a nonperturbative onset of the Anderson localization on lattices for any, arbitrarily small amplitude of the random potential . Away from the spectral edge, the proofs of localization require a sufficiently large amplitude of ; moreover, it is widely believed that in dimension , in the models where the random potential has a sufficiently small amplitude , there are intervals of energy where the corresponding generalized eigenfunctions (“extended quantum states”) are not square‐summable, and the spectral measure has in a nontrivial absolutely continuous component. In simpler terms, there is a nontrivial quantum transport in some energy zones.
A substantial progress has been achieved in the direction of proofs of localization near the spectral edge (or edges). For a long time, most of the efforts have been made in the analysis of lattice Hamiltonians . Recently, it has been shown in Ref.  that a number of results obtained on the integer lattices can be extended to much more general graphs of polynomial (or, more generally, subexponential) growth. The key point is the availability of lower bounds on the spectral gap in terms of the Cheeger’s constant of the graph.
Consider a lattice cube with the graph structure inherited from the lattice, and the random lattice Schrödinger operator on it. The starting point of the localization analysis of this finite‐volume Hamiltonian is the estimate of the probability to have some eigenvalues of in a small interval near the spectral edge . This is closely related to the Lifshitz tails. One needs a finite‐volume analog of the limiting Lifshitz asymptotics, but for the localization analysis, one can settle for a sufficiently strong, albeit not necessarily sharp, upper bound on the probability
Now recall Temple’s inequality .
Proposition 1. Let be a self‐adjoint operator in a finite‐dimensional Hilbert space , and be a simple eigenvalue. If a vector with unit norm satisfies then
Now one can see the importance of the size of the lowest spectral gap, . As was mentioned above, is easily calculated explicitly for the Laplacians in lattice rectangles, but of course there is no universal formula for general finite graphs. The following result was obtained in Ref. .
Proposition 2. Let be given a finite connected subgraph of a locally finite countable connected graph satisfying the following condition: there exists some real constants and such that any ball of radius has cardinality
Apart from the canonical negative Laplacian , it is often more convenient to work with its modified variant defined by
where and are the coordination numbers of the vertices and , respectively: . The coordination numbers are nonzero, whenever the graph is connected and has more than one vertex. Below we quote the bounds obtained for the modified Laplacian, but, up to some constants, they remain valid for the original Laplacian.
Definition 2. The Cheeger’s constant of a finite connected graph is the following quantity:
where the minimum is taken over all nontrivial partitions of the graph into disjoint subgraphs and its complement .
Denote by , , the eigenvalues of numbered, as their counterparts , in increasing order. Then one has the following results (cf. ).
Proposition 3. Let be given a finite connected graph of diameter . Let be the first nonz ero eigenvalue of the modified graph Laplacian , and the Cheeger’s constant of . Then
The upper bound by is not quite explicit in general (this depends of course on the specific problems at hand), but for finite connected subgraphs one can prove that (cf. ). Now we are ready to prove the following result.
Lemma 1. Let be a finite connected subgraph of a graph satisfying the growth condition in Eq. (6), and . Let be a nonnegative real function on , and set Then
Proof. Consider the normalized eigenfunctions of with the eigenvalue , viz. . Next, introduce an auxiliary operator . By nonnegativity of the functions , we have the inequalities (in the sense of the associated quadratic forms)
so that by the min‐max principle, we have and . Since , it follows that , and therefore,
Thus, we have Temple’s inequality to and . Note first that by , one has
Now apply Temple’s inequality, taking account of the above identity:
Lemma 2. Consider a nonnegative i.i.d. random field on a locally finite graph satisfying the growth condition in Eq. (7), with the common marginal probability distribution function , and assume the following:
There exist arbitrarily large such that any ball can be partitioned into connected graphs with , for some .
for some , and all ;
Then for any positive integer , there exists a finite connected subgraph with and satisfying the following spectral bound:
Proof. Using the Cheeger bound for the first nonzero eigenvalue, we have
Let , then , hence we can use and get
The value can be made arbitrarily small by taking the cardinality of the graph large enough, and by assumption on continuity of the probability distribution function , for sufficiently small we have . Recall that the values of the random potential are i.i.d., and so are since they are functions of i.i.d. r.v., so the probability for the sample mean of a large number of i.i.d. random variables to take a value away from the expectation can be assessed with the help of the large deviations theory. Specifically, for any and i.i.d. r.v. , for any such that , one has
Theorem 1. Assume (W). There exist some and arbitrarily large balls such that
Proof. Fix a vertex . By assumption (i), there are arbitrarily large such that the ball can be partitioned into connected graphs with . The operator admits the following lower bound in the sense of quadratic forms:
Since is a multiplication operator, we also have
Observe that by (i), . Owing to Lemma 1, we conclude that
provided that is sufficiently large.
Now we give an application of the above result, which was the main motivation in Ref. , and explain how the bounds for the eigenvalues of the graph Laplacians give rise to the decay of eigenfunctions. Due to the size limitations of the present chapter, we treat the Green’s functions in finite cubes, but the decay of the latter is important in itself, for physical applications, and it is known to imply the decay of eigenfunctions (cf. ). The decay of the Green’s functions is established by the so‐called multiscale analysis (MSA), an inductive scaling algorithm which we will sketch now (details can be found in [9, 10]). First, fix some notations and give some definitions. Given a ball and the operator , we denote by its resolvent operator , and by , , the matrix elements of the resolvent (usually called Green functions) in the standard orthonormal delta‐basis formed by the single‐site indicator functions . Further, given a ball inside a larger connected subgraph , the Green functions satisfy an inequality, often called Simon‐Lieb inequality (sli), easily following from the second resolvent identity: for any and , one has
Since , and the coordination numbers are uniformly bounded by , we have , so the above GRI implies
Here, is an arbitrary point of , but we will be mostly interested in the case where , so the first maximum in the above RHS becomes a characteristic of the ball .
A simple but important observation is that when , we have for the function a subharmonic‐type inequality:
As long as all points at distance from are centers of ‐balls with the same “subharmonic” property, the GRI can be iterated. If steps of iteration can be performed, and for some , then the value admits a small upper bound by .
Definition 3. Given real numbers and , a ball is called ‐nonsingular (‐, NS, in short), if for all
with . Otherwise, it is called ‐singular (‐S).
The main result of Ref.  is the following
Theorem 2. There exist , an interval with , and an integer such that for all and one has
We shall need a positive number ; t suffices to set , which will be assumed below, but for clarity, sometimes the parameter will be used in its symbolic form.
We denote by the spectrum of the operator .
Definition 4. Given an operator in a ball , this ball is called ‐nonresonant (‐NR, in short), if , and ‐resonant (‐R), otherwise.
Clearly, if a ball is ‐NR, the resolvent is well‐defined at the energy , and the modulus of all the respective Green functions are upper bounded by , since the finite‐dimensional operator is self‐adjoint. Probabilistic bounds on for random operators are traditionally called Wegner bounds, due to the original work by Wegner  who established the first general bound of that kind.
Lemma 3 (Wegner estimate). Assume that the random potential of the operator is i.i.d. and the common marginal probability distribution of admits a probability density bounded by some . Then for any
Definition 5. Given an operator in a ball , this ball is called ‐bad if it contains at least two nonoverlapping ‐S balls of radius , and ‐good, otherwise.
Lemma 4. If a ball is ‐NR and ‐good, then it is ‐NS.
Sketch of the proof. The claim is easily obtained by iterating the Simon‐Lieb inequality (SLI) and using the hypothesis of ‐goodness; the latter guarantees that in the course of iterated applications of the GRI, one can stumble on an ‐S ball of size at most once. There may be no singular ball inside , then the subharmonic‐type inequalities easily provide an exponential decay from the center to the boundary of the ball. Furthermore, if there is one singular ball, one can approach it from the center and from the boundary, using the SLI on the first or on the second spatial argument of the Green function. The “wasted” distance is of order or , so an elementary calculation provides the desired decay bound of the Green’s functions. Technical details can be found in Ref. , but it is worth emphasizing the crucial role of the “nonresonance” hypothesis: as was explained, an iterated use of the subharmonic‐type inequality in Eq. (21) only gives the upper bound , which is absolutely useless without an explicit control of the sup‐norm of the function , and in our case, one has the functions .
Theorem 2 can be derived from the following inductive statement.
Theorem 3. Introduce the following notations: for each , let
Assume that with , and
Then for all one has .
Sketch of the proof. We proceed by induction, starting with the hypothesis . Assume the required bound holds for some , then we have to prove it for the balls of size . By Lemma 4, if a ball is ‐S, then either it is ‐R, or it is not ‐good, i.e., contains at least two disjoint balls , which are ‐S. The number of possible pairs inside is bounded by , and the probability for each pair to be ‐S is bounded inductively by . Thus, the probability of existence of at least one such pair is upper‐bounded by
Further, the probability for the ball to be ‐R is upper‐bounded with the help of the Wegner estimate from Lemma 111, without induction:
Theorem 3 shows that if on some scale the Green functions in the balls of radius decay—with a sufficiently high probability—exponentially fast from the center to the boundary of the ball, then the same phenomenon is reproduced, with ever higher probability, on any scale . Such a decay is akin to that of a wave function of a quantum particle in a classically prohibited space where the energy of the particle is below the potential “barrier,” so there is a powerful mechanism, originally discovered by P. W. Anderson in 1958, which reproduces the local tendency of a quantum particle to localization in the disordered environment on any scale. The main problem concerns the mechanisms creating such a tendency for localization. This is where we turn to the spectral analysis in the balls and seek estimates for the first nonzero eigenvalue of the graph Laplacian in .
Indeed, if we restrict our analysis to the interval of small positive energies (assuming the potential is nonnegative; otherwise we can make a spectral shift), then it is clear that for all energies below the spectrum of the operator must decay exponentially with respect to the distance , due to the above‐mentioned “under‐the‐barrier” decay well‐known from the elementary exercises in quantum mechanics. Mathematically, there is actually a more general result, the Combes‐Thomas estimate  which applies not only to the values strictly below the spectrum of , but all in the resolvent set, i.e., simply away from the spectrum. Specifically, fix an operator relative to a ball , and let satisfy . There exist universal constants such that for all it holds that
Now all the pieces of the puzzle find their place:
Using the isoperimetric spectral estimates combined with the Temple inequality, we can find a sufficiently small energy interval , with , such that in large balls a random potential takes a very low average value with a very small probability, so that it is highly unlikely for to have its lowest eigenvalue below .
Restrict the energy interval to ; then for all we have , so the Combes‐Thomas estimate in Eq. (31) applies and guarantees a fast decay of the Green functions from the center to the boundary of the ball . Notice that we can have lower bounded by a fractional power of . Indeed, Eq. (19) allows us to take , and the probability for such a bound to hold is at least , in notations of Eq. (19).
We thus have, in a tiny interval of energies close to the bottom of the spectrum, the starting hypothesis of the scale induction fulfilled. Now the roll the induction and prove exponential decay with high probability at any scale , .
Once again, it is to be stressed that it is a graph‐theoretic spectral estimate that makes this story possible, and the presented phenomena take place for a rich class of graphs, much larger than just periodic lattices. This general estimate is a far‐going replacement for the elementary consequences of the Fourier analysis on .
Summarizing, the problem of computing exact asymptotics, or at least sharp upper/lower bounds on the limiting distribution function of the eigenvalues for the operators on various classes of graphs is of course much more general and important than one particular application to the Anderson localization presented above. This if often a difficult problem, and the wealth of knowledge and intuition accumulated in the spectral graph theory would be very welcome to this area of mathematical physics.
3. Symmetric powers of graphs and spectra of fermionic systems
3.1. Motivation and preliminaries
Now we turn to another problem of spectral analysis of quantum Hamiltonians of disordered systems. The presentation will be less technical, and the main message is that the graph theory provides here both an adequate language and technical tools allowing one to treat efficiently difficult problems arising in the recently developed multiparticle localization theory; some of these problems are still open and challenging.
In quantum mechanics, stationary states of a system of several quantum particles are described by the eigenfunctions of their respective Hamiltonians acting in subspaces of either symmetric or antisymmetric functions , , where is the number of particles, and each argument runs through the single‐particle configuration space. The particles described by antisymmetric functions are called fermions, and those described by symmetric functions are called bosons. Physically speaking, the particles evolve in the three‐dimensional space, but in the framework of the so‐called tight‐binding approximation, they can be restricted to a periodic lattice or, more generally, a locally finite graph embedded in the Euclidean space. In this section, we assume the latter and work with N‐particle systems on a graph . In fact, even the case where is of interest for us, since we are going now to show how a typical construction of the graph theory, the symmetric power of a graph, can be instrumental for solving a formal yet thorny technical problem encountered in the multiparticle Anderson localization theory.
The quantum particles are physically indistinguishable, so any accurate mathematical model has to reflect this fact. In some situations including the localization analysis of randomly disordered media, it is more convenient to represent the Hilbert space of symmetric or antisymmetric functions on as the space of functions on the set of configurations of indistinguishable particles, instead of a subspace of (+/−)‐symmetric functions defined directly on . While the two approaches are mathematically equivalent, the latter one has an important technical advantage that can be explained as follows.
Consider for simplicity of a two‐particle fermionic system in a finite subgraph with the graph structure inherited from . The wave functions of the two‐particle systems are thus antisymmetric functions of two variables . We assume the Hamitlonian of this system to ba a discrete Schrödinger operator of the form
Definition 6. Let be given a random potential on a subgraph of the lattice , and a nonrandom function of an integer argument. A two‐particle discrete Schrödinger operator on is the operator of the form
(the kinetic energy operator) is the sum of two replicas of the graph Laplacian on , acting on a function as a function of the variable , ;
is the operator of multiplication by the random function ; and
is the operator of the interaction energy of the two particles at hand, acting as the operator of multiplication by the nonrandom function .
The factor measures the amplitude of the kinetic energy operators and reflects the mobility of the particles. In this section, it is instructive to think of as a small number, so that the potential energy is in a certain sense dominant. is the operator of random potential energy induced by the disordered media (modeled here by a finite linear chain) acting as operator of multiplication by the real‐valued function
and are i.i.d. random variables on (local potentials produced, e.g., by heavy ions).
The function is called the two‐body interaction potential.
For the sake of notational clarity, here and below we use boldface notations for various objects related to multiparticle objects.
The onset of Anderson localization manifests itself by a fast (usually exponential) decay of the eigenstates of the Hamiltonian away from some vertex, depending upon the quantum number $j$ (usually referred to as the localization center of the respective eigenstate . The quantum transport, on the other hand, may take place due to the tunneling between distant vertices with very close local energies. The latter notion can be ambiguous when the kinetic energy is nonnegligent, but pictorially, under the assumption we made above that is small, the local energy at a vertex is essentially given by , thus depends directly upon .
Now recall that the modulus of an asymmetric function is symmetric, thus necessarily takes identical values at vertices and in the space of ordered configurations of distinguishable particles. The symmetric vertices and can be located at arbitrarily large distances from each other in the original two‐particle configuration space given by the Cartesian product . As a result, one has, formally, consider the possibility of “tunneling” between and , although there is no physical particle transfer process between these two configurations: from the consistent quantum mechanical point of view, the latter are simply identical! We come therefore to realize that the mathematical model based on the Cartesian square of the “physical,” single‐particle configuration space generates some formal problems which actually have no physical raison d'être, yet they have to be addressed explicitly to rule out some unwanted phenomena. In particular, this renders substantially more complicated the rigorous localization analysis.
However, the above‐mentioned difficulty disappears as soon as one replaces the Hilbert space of antisymmetric functions on by an isomorphic Hilbert space of functions Φ on the set of configurations of indistinguishable pairs of vertices from the basic graph . The required construction is well‐known in the graph theory: we need a symmetric power of the graph . Due to the mathematical complexity of the rigorous multiparticle Anderson localization theory, we can only sketch its general strategy in this chapter, but the main tool, which proves very valuable here, deserves a more detailed discussion. As was said in the introductory part, the main goal of this section is to attract the readers’ attention to some interesting and useful relations between the mathematical physics of disordered media and the notions, tools, and deep results of the graph theory.
3.2. Construction of a symmetric power of a graph
3.2.1. An example in one dimension
Before we turn to general constructions of symmetric powers of locally finite graphs, it seems instructive to consider first a particular case where the underlying, basic graph is linear, i.e., isomorphic to a subgraph of the one‐dimensional lattice . The existence of a complete linear order makes possible a particularly simple variant of the symmetric square (indeed, of any symmetric power , ).
Consider the triangular subset of lattice square (here stands for the integer interval ):
(here (2) reflects the number of “particles”). An example is presented in Figure 1. Any antisymmetric function on vanishes at any point of the form , and its modulus takes identical values on and on the symmetric point . It follows that
This provides a natural isomorphism between the Hilbert spaces of complex functions on and on Clearly, the same idea works in the N‐particle case, where we can define
except that in the latter case, the factor of in Eq. (23) is to be replaced by .
Such a simple, transparent geometrical construction is no longer available for general graphs, but an isomorphism similar to that from Eq. (23) can be established for the symmetric powers of graphs. Below we give a variant with a distinctive flavor of quantum mechanics.
3.2.2. General construction
The vertex set. Let be given a connected, locally finite countable graph with the vertex set and an edge set , and an integer . Consider the integer‐valued functions on such that . The physical meaning of the value is the number of particles at the vertex , so it is usually called the occupation number of the site . Due to the indistinguishable nature of the particles, only the numbers of particles at each site are physically observable (measurable in experiments). Furthermore, since we are modeling now fermions, the respective wave functions, by their antisymmetry, must vanish on any configuration of particles among which at least two occupy the same position. This was precisely the reason we excluded the “diagonal” from above. Now we achieve the same effect by the requirement . The bottom line is that a configuration of particles admissible for modeling fermions is completely determined by a function ; for all intents and purposes, each is a (fermionic) configuration.
Hence, we constructed an appropriate vertex set of the graph that would generalise for an general underlying graph . Specifically, there is a projection
The points of the support of a function will be called the particles of the configuration . Restricted on the set of ‐tuples of pairwise distinct vertices , the projection is exactly ‐fold: the pre‐image has cardinality .
The edge set. Using again a terminology inspired by physics, we say that two configurations form an (unordered) edge if and only if is obtained by moving exactly one particle of to a position unoccupied by other particles from .
Mathematically, we require that
It is not difficult to see that the two definitions are equivalent. Indeed, each term in the above sum equals or , since , and such a term vanishes when either , i.e., is unoccupied by either configuration, or , i.e., both configurations have a particle at . Removing particles from the support of to produce new configuration , we have to place them outside the support. Therefore,
each point with and (i.e., occupied by but unoccupied by ) contributes by a two unit term to the sum: first, , and second, for the position to which we move the particle from we have . If we move more than one particle from , the sum in Eq. (25) will be at least . We conclude that the second definition in Eq. (25) is equivalent to the first one.
This completes the construction of the ‐th symmetric power of the graph .
3.2.3. Hilbert space isomorphism: antisymmetric functions versus symmetric power
Now the isomorphism between of the Hilbert space of square‐summable complex antisymmetric functions on the Cartesian power and the Hilbert space of all square‐summable complex functions on is defined in a natural fashion. Recall that we introduced the projection , such that consists of all permutations of the vertices from the support of . Any function Φgenerates a symmetric function , and each symmetric function can be obtained in this way, as . The modulus of any antisymmetric function on the Cartesian power takes identical values on all elements of . Thus, with ,
Now the required isomorphism is defined by .
It might appear that the described isomorphism is just an interesting formal trick, but there is much more to it than a mere mathematical curiosity. As one illustration, we consider now a problem of spectral analysis for multiparticle random Hamiltonians above.
3.2.4. An application: KAM‐type analysis of two‐particle fermionic random Hamiltonians
The goal of this subsection is merely to illustrate the key role of the isomorphism between the subspace of antisymmetric square‐summable functions of variables in a graph and the space of all square‐summable functions on the symmetric power . The mathematical problem where it is used is quite complex, so we will only sketch the main setting and focus on the role of the symmetric powers.
It is to be emphasized that the spectral analysis of ‐particle quantum Hamiltonians in presence of a random potential field, generated by a disordered media, accurately taking into account a nontrivial interaction between the particles, is a relatively new direction both in theoretical physics and in rigorous mathematical physics. This is an actively developing and challenging area of research. While physicists have finally obtained convincing theoretical results on the stability of localization under the Coulomb interaction, the progress in rigorous mathematical physics is still relatively modest, compared to theoretical physics. The best insight achieved in the last 10 years concerns the systems of a fixed number of particles in a large sample of a disordered media. For the purposes of this chapter, we always restrict the analysis to discrete systems on graphs.
As was said in the introductory section, we can only sketch rather complex mathematical constructions involved and illustrate the main mechanisms of stability of localization under interaction. For simplicity, suppose that we have a system of particles in a large but finite connected graph on which an i.i.d. random (potential) field is defined. One can consider various marginal probability distributions, i.e., identical probability distributions of the random variables . Two models popular in theoretical physics of disordered media suit perfectly our needs here: a standard Gaussian distribution with zero mean and unit variance, and the uniform distribution on the interval .
Consider first the simplest (yet mathematically nontrivial) case of zero amplitude of interaction. Then the variables in the Hamiltonian can be separated, since in this case one has an algebraic representation where is the identity operator, and therefore, the eigenvectors of the operator can be chosen in the tensor product form, , where are eigenvectors of the single‐particle Hamiltonians and , respectively. The latter are identical replicas acting on their respective variables and . The eigenvalues are the sums , with .
The main reason why the electron‐electron interaction was consciously neglected even in theoretical physics, is that it is relatively weak as compared to the potential energy of interaction with the ions surrounding the mobile electrons, so we also assume the amplitude of the interaction potential to be small.
Another important assumption can simplify the spectral analysis, at least in an informal treatment of the problem: small amplitude of the factor in front of the kinetic energy operator ; in physical terms, this corresponds to a low mobility of the particles at hand which, naturally, should favor “localization” of a given particle. Mathematically, already for (isolated particles), with we get a multiplication operator which has the orthonormal eigenbasis composed of the “discrete delta‐functions” , . Similarly, for and we have a perator of multiplication by the total potential energy which also has a complete eigenbasis composed of “localized” eigenfunctions.
If we had constructed an eigenbasis of the multiplication operator in the representation on the Cartesian square , then we would have obtained the two‐site supported eigenfunctions:
while the representation on the symmetric square gives rise to single‐site eigenfunctions , where . Naïvely, starting with the “ultralocalized” eigenfunctions , one may attempt to use the first‐order perturbation theory. The well‐known formulae of the rigorous perturbation theory for the eigenvectors reveal two problems:
“small denominators,” i.e., pairs of very close or equal eigenvalues; and
large dimension of the spectral problem, which may also give rise to degenerate eigenvalues or at least to some pairs of close eigenvalues.
Indeed, the eigenvalue associated to the unperturbed eigenfunctions of the potential energy operator is given by
Fix now the random field model with uniform marginal distribution, and let the interaction be uniformly bounded, then the above eigenvalues all belong to some fixed, bounded interval, regardless of the dimension of the Hilbert space, growing with the cardinality of . The larger is , the closer the eigenvalues must get, counted with multiplicity and restricted to a fixed interval of . In the Gaussian model, a similar phenomenon is encountered, with high probability, since large values of the Gaussian random potential are taken with small probability.
A conclusion we can draw from this elementary analysis is that one cannot expect the perturbation theory for nondegenerate spectra, or for the finite‐dimensional operators with bounded multiplicity, to work efficiently in the model with a large graph .
Several approaches have been developed in spectral theory of single‐particle random Hamiltonians in the last three decades. Technically, they are based on different mechanisms, and even a brief presentation of these approaches would require an entire book. Interested readers may familiarize themselves with the basic techniques in the monographs [9, 10]. Recently, there has been a wake of growing interest to the technique going back to the celebrated KAM (Kolmogorov‐Arnold‐Moser) theory originally developed for the analysis of stability of invariant tori in some nonlinear dynamical systems
Recently, Imbrie  adapted the KAM techniques to the spectral analysis of random lattice Hamiltonians, in any dimension, and to one‐dimensional random spin chains.
In essence, the “linear” version of the KAM method is an inductive, iterated use of the first‐order perturbation theory with an accurate account of the higher‐order terms represented by an infinite number of diagrams. At each step of the induction, one obtains an orthogonal basis for the considered (random) operator that is an approximate eigenbasis for the latter, but with better and better accuracy. The error terms on the ‐th step of induction feature a typical Newtonian decay rate like , where , which is not surprising since KAM technique is based on one or another form of Newton’s method. Once a new, more accurate eigenbasis of order is constructed by perturbing its predecessor of order , the matric elements of are computed in this (orthonormal) basis, and the process is repeated. KAM type constructions are usually quite complex and cumbersome. One has first to describe in detail the entire set of properties to be assumed on the step and then reproduced on the next induction step .
A synthetic method, employing some ideas of the KAM method and other, simpler techniques elaborated in the spectral theory of single‐particle random Hamiltonians, have been proposed first to the noninteracting random systems , and later on to their ‐particle counterparts. The pivot of this method, like in the KAM approach, is an accurate quantitative control of the “small denominators”—minimal distances between distinct random eigenvalues of random Hamiltonians associated with finite but growing subgraphs of a countable graph. It would be difficult to carry out such a program in the representation of distinguishable particles, i.e., on the Cartesian power .
Now return to the semiquantitative analysis of a two‐particle Hamiltonian. Restrict ourselves to a case where the size of the underlying graph , modeling the “physical” space where the two quantum particles evolve, has a fixed size, and allow us to vary the parameter in (the mobility amplitude), and to take it as small as needed for an attempt to make one step of application of the perturbation theory for nondegenerate spectra.
With both and small enough, the main contribution comes from the random potential, so we have the eigenfunctions of the unperturbed operator with eigenvalues , and we have to assess the difference between two such eigenvalues, labeled by two pairs of sites of the graph :
Since the potential is random, there can be no uniform, deterministic lower bound on the absolute value of the above difference: with positive probability, it can be smaller than any . The randomness, however, is a double‐edged sword: while small values of the difference are certainly possible, they may, or might, be unlikely, so we have to determine, how unlikely is to have .
To begin with, notice that we have to deal with different eigenfunctions, hence with two nonidentical pairs . Thus, . Consider two cases.
In this case, the random variables and have no common terms, and therefore they are independent. Moreover, inside each pair we have independence, so the probability distribution of each sum can be easily obtained by convolution. For simplicity, consider the case of standard Gaussian variables, then each eigenvalue is also Gaussian with zero mean and variance . The difference is again a sum of two i.i.d. Gaussian variables and , hence it is Gaussian with zero mean and variance . Recalling the explicit form of the Gaussian probability density with variance , which is uniformly bounded by , we conclude that
Now the unordered pairs and have exactly one common point; let it be , so we have a pair of eigenvalues and with and the difference given by
so it is again a sum of two independent random variables. Assuming as before the distribution to be Gaussian with zero mean and unit variance, we see that is centered Gaussian with variance , so the analog of Eq. (32) is now
The final conclusion is that for small , the small differences between any two eigenvalues corresponding to two distinct eigenfunctions on the symmetric square of the underlying graph is small, viz., of order of . Therefore, for a finite graph of size , the probability to have at least one pair of eigenvalues at distance smaller than is bounded by (we used the weakest of the two estimates in Eqs. (32) and (33)).
This simple probabilistic analysis provides the logical basis for the KAM approach, where we can rule out “small denominators” which cannot be tolerated in the analytic application of the first‐order perturbation formulae, at some initial scale. The rest of the procedure requires a number of analytic efforts, but the crucial point, viz., the possibility to avoid degenerate eigenvalues at the initial scale, is the direct consequence of the graph‐theoretical construction of a symmetric power of a graph . Using a Cartesian power of would at best significantly complicate the entire procedure, and perhaps render it impractical. In any case, no replacement for resorting to symmetric powers has been found so far in multiparticle localization theory of fermionic systems on graphs.
4. Combinatorial and metric (quantum) graph
Our final topic also concerns the constructive relations and interactions between the graph theory, in a broad sense, and the mathematical physics of the quantum world. However, the general direction of these interactions will be reversed, for we are going to discuss a very recently developed class of mathematical objects naturally emerged in the analysis of interacting quantum systems. We would like to attract the attention of experts in graph theory and related fields to the new area, where a number of questions are not even properly formulated, and many interesting phenomena are yet to be discovered.
First, recall the notion of a metric graph; due to a wake of interest to the so‐called nanotubes, one often refers to these mathematical objects as “quantum graphs.”
Metric graphs represent an important link between the discrete spaces and manifolds endowed with a rich local structure of a Euclidean space. By definition, a metric graph over a finite or countable unoriented combinatorial graph with the vertex set and the edge set , is a singular one‐dimensional manifold constructed as follows. Associate with each edge an open interval , considered as a Riemannian manifold with the Riemannian metric inherited from . In some models, all the intervals have the same lengths, so by a change of parameters one usually can assume they are replicas of . In other models, on the contrary, one allows variable length of these basic intervals. We will assume the former and work with unit intervals. There is a canonical oriented graph associated with the unoriented graph , with the same vertex set and two opposite edges for each edge in . In some auxiliary constructions, this morphism from the category of unoriented graphs to that of oriented ones can be used, to avoid some ambiguities, but it will be not crucial to our purposes, since we will work with a second‐order differential operator (essentially the second derivative operator), so the orientation will not be really important.
Each open interval is canonically compactified by its natural embedding into . Taking an edge and fixing its orientation in one of the two possible ways, so that , we thus can identify its starting point with and the terminal point with . Next, we define the differential operator in the space of twice differentiable functions on ; boundary conditions are discussed below. In other words, , where is the Laplacian on the Riemannian manifold . While requires a local coordinate, hence a fixed orientation, is not sensible to this choice.
Further, consider the disjoint union of the basic (open) intervals , finite or countable, with the natural structure of the measure space induced by the Lebesgue measure on each interval with the respective sigma‐algebra of measurable subsets. In turn, this allows us to introduce the Hilbert space of square‐integrable functions on ; this is not yet an object we had needed, for there is no connections between the restrictions of a given function on to different, pairwise disjoint connected components thereof.
Now it is time to choose boundary conditions, having in mind the canonical embedding of into the union of the compactified intervals . In application to the “quantum” graphs, traditionally one imposes the Kirchhoff conditions. Now, for formal reasons, fix some orientation on each edge, hence, a local coordinate on each . Then we can define the one‐sided first derivatives on each vertex, in the directions of all attached intervals . Let be such a derivative along the local coordinate on , and set for outgoing edges and for the ingoing ones. The Kirchhoff conditions are as follows: a function must be continuous at each vertex and obey a conservation law
Below we call the intervals continuous edges.
Now, using the standard methods of functional analysis, one can construct a self‐adjoint extension of the “Laplacian” with Kirchhoff boundary conditions, and for any, say, bounded measurable function (a potential), define the Schrödinger operator as unbounded self‐adjoint operator in , with the suitable domain.
One can perturb the above, rather idyllic picture in several ways. First, one can consider a random potential , taking i.i.d. random values on each edge. Further, on can vary the lengths of the continuous edges, assuming that are i.i.d. random variables with a common probability distribution. From the functional analytic point of view, treating unbounded self‐adjoint operators on metric graphs, in the framework of random operators, is substantially more delicate a matter that the analysis of finite‐difference operators on the underlying discrete, combinatorial graphs. One may wonder, whether some properties of the Hamiltonians on the underlying graph can be useful for the analysis of their continuous siblings . The theory of boundary triples (cf. ) provides a powerful and valuable tool of spectral analysis on continuous metric graphs, where an essential part of technical work is carried out in a simpler framework of countable graphs with discrete Schrödinger operators.
Now we turn to a further development in this direction made recently by Sabri  who introduced the notion of multiparticle quantum graph. We consider the simplest nontrivial case of quantum particles on a quantum graph . To be able to refer to existing results and publications, we assume the particles distinguishable.
In the discussion of two‐particle systems on a graph in Section 3, the pair was ranging in the Cartesian (and then symmetric) square of , and the latter is, topologically, a discrete space, thus essentially of the same nature as the factors in the product . But now that the configuration space for each particle is a continuous object, viz. a (singular) one‐dimensional Riemannian manifold, the situation changes radically: the configuration space for the pair is locally a two‐dimensional manifold; in the case of an ‐tuple it becomes ‐dimensional. Many specifically 1D methods of spectral analysis are inapplicable in dimension .
Shortly after the publication of the first results on ‐particle Anderson localization in periodic lattices and in Euclidean spaces, Sabri  proposed an interesting extension of the new techniques and results to the multiparticle systems on quantum graphs. His construction was essentially motivated by a specific goal, but there are various contexts where the construction itself may prove valuable.
For , one has to start again with the building blocks of a 1D quantum graph over a combinatorial graph : the open finite intervals associated with each edge of . Restricting the positions of the two particles to their respective continuous edges identified with , we have the pair ranging in the unit square . For brevity, call such basic squares cells. Each cell is delimited by four continuous edges inherited from the first and from the second particle, and these four (continuous) edges are the loci of contact between the cells. Clearly, this complicates the structure of what was the edge set in the underlying graph , but this is the natural replacement for the notion of the edge set; this is what defines the topology and metric geometry of the new object, called by Sabri a ‐particle (more generally, ‐particle) quantum graph .
Just like the Laplacian defined on the quantum graph, we can define its two‐particle counterpart : first, on the unit squares, and then proceed to self‐adjoint extensions with one or another kind of boundary conditions to be imposed on the 1D continuous edges of the conventional, ‐particle quantum graphs supporting each of the two particles. This inevitable functional analytic work has been done by Sabri. And of course, once the natural Laplacian is defined as an unbounded self‐adjoint operator with a suitable domain in the Hilbert space of square‐integrable functions on , one can also define the Schrödinger operators , e.g., for bounded measurable functions . In Figure 2, we give an example of three models based on the same graph structure: a combinatorial graph, a quantum graph, and a two‐dimensional domain surrounding the quantum graph in question.
The new construction raises a number of questions, of different nature. One of them concerns the constructive relations between the spectral properties of a Schrödinger operator on the continuous, locally two‐dimensional (2D) manifold , and its analog on the Cartesian square of the combinatorial graph .
Another question, of functional analytic nature, raised by Sabri, concerns an explicit description of the self‐adjoint extensions of the 2D Laplacian initially defined, say, on infinitely differentiable functions with support inside an open cell . It appears that the corner points make the explicit analysis difficult, although the existence of the desired extensions poses no serious problem.
Mathematical modeling of physical phenomena had provided important motivations for developing various fields of mathematical physics since several centuries; as to the quantum physics, its development was from the beginning of the twentieth century parallel to the development of the functional analysis in general and spectral theory of operators in particular. The remarkable discovery made by P. W. Anderson in 1958 brought to life a synthetic approach to modeling disordered systems based on a fusion of analysis in a broad sense with probability theory. The physical community came to realize that the models based on the idealized picture of perfectly periodic crystals miss some crucial mechanisms responsible for transport (e.g., electrical conductivity) or absence thereof under the Anderson localization. The classical formulae for conductivity and many related phenomena, crucial for the development of modern microelectronics and nanotechnologies, cannot ignore the localization/delocalization problematics. While the most simple models may refer to the integer (and some other periodic) lattices in a Euclidean space where classical Fourier analysis can use the method of separation of variables, the situation can be significantly more complex in the case of quasicrystals, featuring both a local order and long‐range disorder. Mathematically, such structures are described as nonperiodic graphs where the Fourier analysis breaks down, and one needs some efficient, constructive replacements. Furthermore, large and complex molecules studied in organic chemistry and molecular biology also require a versatile toolbox not limited to a commutative Fourier analysis. Also, the crystalline media in presence of structural (e.g., mechanical) defects are not stricto sensu periodic, so again one needs robust eigenvalue distribution bounds not relying on the exactly periodic geometry of the media. In Section 2, we have seen that the isoperimetric inequalities, appeared in the graph theory under the influence of its diverse applications, provide indeed adequate tools for an asymptotic analysis of the limiting eigenvalue distribution for discrete quantum Hamiltonians used in physics in the framework of the so‐called tight‐binding approximation effective for the “low” energies. The term “low” actually refers to the energies lost important to the quantum processes exploited in modern microdevices (e.g., CPU having diameter of a few millimeters and width of order of a few dozens of atomic layers), in biological tissues and technologically created organic substances.
In 2008, The Isaac Newton Institute for Mathematical Sciences in Cambridge, Great Britain, has organized a semiannual program “Mathematics and Physics of Anderson Localization: 50 Years Later” aiming to summarize the impact of Anderson’s theory on physical theories and applications as well as on the mathematical physics. The general conclusion many participants and younger researchers could draw from numerous and diverse presentations was that the paradigm of quantum localization/delocalization provides today both a language and a general theoretic background for many specific directions of research; it is not an isolated pragmatic physical model or abstract mathematical problem. The program in question also revealed to the physics and mathematics communities the importance of the interparticle interaction which was briefly discussed in Section 3; the need for such theory was emphasized already by Anderson in his early papers, but one had to wait almost half a century to see its emergence in independent physical and rigorous mathematical works. Shortly after the program, the Anderson localization theory for interactive disordered systems has been applied (in mathematical works) to the nanotubes modeled by quantum graphs. While the size limitations of the present work do not allows us to present mathematical details of the new theory, there is no doubt that many of its mathematical aspects are closely related to the methods of the graph theory. Further reading, along with an extensive bibliography, can be found in the first monograph  dedicated to localization phenomena in interactive systems. This new direction of mathematical physics still is at its early stage of development. The language and toolbox of the graph theory proved to be very useful here, as we have seen in Section 3. On the other hand, new structures discussed in Section 4, emerging from the analysis of multiparticle quantum graphs open new problems and propose new types of models to the graph theory. This chapter was written in the hope to bring closer the communities of researchers, particularly the younger ones, working in functional analysis, graph theory in a broad sense, and in probability theory.