{'fraction_non_alphanumeric': 0.04482799245994345, 'fraction_numerical': 0.007657869934024506, 'mean_word_length': 4.199693721286371, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Can One Hear the Shape of a Graph?

We show that the spectrum of the Schrodinger operator on a finite, metric graph determines uniquely the connectivity matrix and the bond lengths, provided that the lengths are non-commensurate and the connectivity is simple (no parallel bonds between vertices and no loops connecting a vertex to itself). That is, one can hear the shape of the graph! We also consider a related inversion problem: A compact graph can be converted into a scattering system by attaching to its vertices leads to infinity. We show that the scattering phase determines uniquely the compact part of the graph, under similar conditions as above.


Background and notations
The question "Can one hear the shape of a drum?", was posed by Marc Kac [1] as a paradigm example for a class of problems which is of fundamental importance in many physical applications: Given the quantum spectrum, can one deduce uniquely the basic interactions or the geometric constraints which specify the system? In Kac's original paper, this inversion problem is formulated for Laplacians on compact domains with boundary conditions (billiards), and in spite of approximately fifty years of active research, the complete answer is still an enigma. If the billiard boundary is allowed to have corners, one can draw different yet isospectral billiards [2,3]. Isospectral microwave cavities were also constructed [4] using the same models. Recently, it was shown that Kac's question is answered in the affirmative for simply connected doamins with analytic boundaries with some symmetry restrictions [5] . For boundaries in intermediate classes of smoothness the answer is not known. The existence of isospectral systems was investigated for Laplacians on closed Riemannian manifolds [6] and for discrete Laplacians which are formed by the connectivity matrices of graphs [7]. In both cases, elaborate techniques were devised to identify large sets of different, but isospectral systems. However, if the domains are analytic surfaces of revolution, the spectrum determines the manifold uniquely [8].
In the present note we address yet another class of problems which go under the name "quantum graphs". The Schrödinger operator consists of the one-dimensional Laplacian on the bonds, endowed with boundary conditions on the vertices, which ensure that the spectra are real and discrete. (see [9] for a detailed discussion and list of references). These systems recently attracted the attention of the quantum chaos community, since, in spite of their structural simplicity, their spectra display the complexity and statistics which characterize generic quantum chaotic systems such as billiards. Moreover, an exact trace formula [11,12] can be written down in terms of the periodic orbits (PO) on the graph, which is analogous to the semiclassical trace formula for chaotic systems. So far, this exact trace formula paved the way to the study of spectral statistics by applying combinatorial methods to periodic orbit expansions [13,14]. Here we shall show that it also provides the key to the affirmative answer to Kac's question, when applied to graphs.
A graph G consist of V vertices connected by B bonds. The V × V connectivity matrix is defined by: C i,j = number of bonds connecting the vertices i and j . (1) A graph is simple when for all i, j : C i,j ∈ [0, 1] (no parallel connections) and C i,i = 0 (no loops). The valence of a vertex is v i = V j=1 C i,j and the number of bonds is B = 1 2 V i,j=1 C i,j . We denote the bonds connecting the vertices i and j by b = [i, j]. The notation [i, j] and the letter b will be used whenever we refer to a bond without specifying a direction.
To any vertex i we can assign in a unique way the set s (i) of bonds which emanate from it: We shall refer to s (i) as a topological star, since its definition does not require any metric information. For simple graphs, Directed bonds will be denoted by d = (i, j), and we use the convention that the bond is directed from the first to the second index. The round brackets, and the letter d are reserved to denote the directed bonds. The reverse bond to d = (i, j) is denoted byd = (j, i). In analogy to (2), we define the sets of directed bonds outgoing from or incoming to i: respectively. Note: card[s (i, belongs to the two sets, s (i,+) and s (j,−) , and We shall now define the Schrödinger operator on G, and collect a few facts which will be used in the sequel. For a detailed exposition see e.g., [9]. We assign the natural metric to the bonds, and each bond is endowed with a length L b . The Schrödinger operator consists of on all the bonds, and A b are constants which are introduced to break the symmetry between the counter propagating waves on the bond. The differential operator is supplemented by boundary conditions which are imposed in the following way. The most general solution of the Schrödinger equation on where d, andd denote the two directions on the bond b, and a d , ad are yet unspecified complex numbers. The boundary conditions impose the relations where the vertex scattering matrix σ (i) is a unitary, v i × v i matrix. σ (i) can be either an arbitrary k independent unitary matrix, or of the general class of (possibly k dependent) matrices derived from matching conditions at the vertices [9,10]. The matrix σ (i) will be called properly connecting if none of its matrix elements vanishes. The transition probabilities W As an example, consider the most commonly used and discussed quantum graphs, where the vertex scattering matrices are derived by imposing Neumann boundary conditions at the vertices. In this case σ v i , and but for the trivial vertices with v i = 2, these scattering matrices are properly connecting.
Combining the boundary conditions for all the vertices, results in a secular equation for the wavenumbers k n which consists of the spectrum of the Schrödinger operator. The secular equation reads, where S(k) is a 2B × 2B unitary matrix, whose rows and columns are labeled by the directed bond labels. It is defined as The index i denotes the vertex at which d follows d ′ , and L d = Ld, is the bond length which is independent of the direction of propagation. However A d = −Ad, which distinguishes between the directions of propagation. S(k) can be interpreted as a quantum evolution operator describing the scattering of waves with wave number k between connected bonds. The wave which scatters at the vertex With the next application of S(k) the wave scatters again on the vertex to which d is directed. If all σ (i) matrices are properly connecting, the waves on G propagate between all the topologically connected bonds. The unitarity of the matrices σ (i) guarantees that S(k) is unitary for real k. This is also why the Schrödinger operator is self-adjoint and its spectrum is pure-point and unbounded on the real line.
The secular equation (8), with the form (9) for S(k) leads naturally to the exact trace formula [11,12] where L = B b=1 L b is the total length of G. The sum extends over all the PO's on the graph, and goes over primitive PO's as well as their repetitions. The length of a PO is denoted by l p . The coefficient A p is a product over all the scattering amplitudes σ (i) d,d ′ , encountered along the PO, times the length of the primitive PO of which p is a repetition. It is also endowed with a phase factor exp(i A d L d ). The length of a PO is The length spectrum is the Fourier transform of (10),

Hearing the shape of the graph
After reviewing the necessary background, we are in position to formulate the answer to Kac's question for graphs. Theorem 1: The spectrum of a Schrödinger operator on a metric graph determines uniquely the graph connectivity and the length of the bonds, provided that -the graph is finite and simple, -the bond lengths are rationally independent, -the vertex scattering matrices are properly connecting. Before presenting the formal proof, we shall sketch its main idea: The length spectrum (12) is constructed from the Schrödinger spectrum. Its singularity at l = 0 provides the total length of the graph L, which, in turn, gives an upper bound to the individual bond lengths. The conditions that the lengths are rationally independent, and that whenever d follows d ′ at vertex i, σ (i) d,d ′ = 0, ensure that the lengths of all the PO's which are consistent with the graph connectivity, appear as δ singularities in the length spectrum, and their corresponding coefficients A p do not vanish. Moreover, PO's p, p ′ which traverse the bonds different numbers of times ( q for some b in (11)) have distinct lengths. We use these facts to isolate two classes of periodic orbits. . Once all the topological stars s (i) are found, we apply (3) to get the connectivity. Thus, the shortest, and structurally simplest PO's are used to extract the parameters which determine the "shape" of G.
The proof of the theorem proceeds as follows: i). Use the spectrum to construct the sum (12). Its singular support R consists of l = 0 and the infinitely many points l p of the form (11) on the real axis. The weight of the singularity at l = 0 is 2L. ii) Generate a finite set P which consists of all the strictly positive lengths l p ∈ R, which are less than 2L. Exclude any length which can be expressed as an integer multiples of any other length, with a multiplier larger than 1. P is the (finite) set of lengths of primitive PO's on G, with lengths in (0, 2L]. iii) Define the basis Q ⊂ P , which consists of the minimum number of lengths λ q ∈ P such that ∀l p ∈ P , l p = 1 2 P is a finite set, and therefore Q can be constructed in a finite number of steps. Because of the rational independence of the bond lengths, the basis is composed of the lengths of 2-PO's [d,d], with λ q = 2L q where L q are the lengths of the bonds. card[Q] = B is the number of bonds, and λ q = 2L. iv) In what follows we shall construct metric stars which will be shown to be in one-toone correspondence with the topological stars (2): Define two lengths λ q and λ q ′ ∈ Q to be connected if λ q + λ q ′ ∈ P . A length in Q cannot be connected to itself since repetitions where excluded from P . The lengths in Q which are not connected to any other length, correspond to disconnected bonds, which are identified this way, and excluded from the susequent analysis. Given a length λ r ∈ Q, consider all the clusters C m (λ r ) ⊂ Q satisfying the following requirements: (a) λ r ∈ C m (λ r ). (b) All the lengths in C m (λ r ) are pairwise connected. (c) C m (λ r ) is maximal -adding another λ s ∈ Q, will violate (b). Denote the number of C m (λ r ) by N(λ r ). Metric stars are special clusters defined as follows. If for some λ s , N(λ s ) = 1 we shall define {λ s }, as a metric star consisting of a single element. If card[C m (λ s )] = 2 then it is a metric star with two elements. All other C m (λ r ) are metric stars if for any three elements λ l , λ m , λ n ∈ C m (λ r ), λ l +λ m +λ n ∈ P . P is pruned of repetitions. Hence, this condition excludes repeated triangular PO's from being considered as stars. Using all the λ r ∈ Q as reference lengths, we construct all the different metric stars in Q. The bond lengths are rationally independent, thus, the metric stars S (i) are in 1 ↔ 1 correspondence with the topological stars (2). The proof is completed by writing the connectivity matrix in analogy with (3): The length spectrum can be used to get more information about the graph [15]. The coefficients of the δ singularities provide constraints on the values of the elements of the vertex scattering matrices. Assuming that the σ (i) are symmetric, one can determine the transition probabilities W Dividing (16) and (17) by (15) we get ratios of the matrix elements of a single σ (i) of the form Ratios of products of three matrix elements can also be formed. Using this information one can construct the matrices σ (i) uniquely, up to a phase factor since the ratios of the type (18) are invariant under a right and left multiplication by arbitrary diagonal matrices. Hence one obtains only absolute values, in other words, the transition probabilities W When σ (i) are real, L b A b mod2π can also be computed from the weights of simple PO's.

Application to non-compact (scattering) graphs
A related inversion problem, is encountered when the compact graph is turned into a scattering system by coupling to its vertices leads (bonds) to infinity [16]. It is assumed throughout that each vertex can be attached to at most one lead. The definition of the Schrödinger operator can be extended naturally to the non-compact case, and the coupling to the leads is achieved by modifying the vertex scattering matrices to include coupling to the leads. Let N be the number of vertices to which leads are attached, and the leads are denoted by the index of the vertices to which they are connected. Then, for every wavenumber k one can find a solution to the Schrödinger equation which on the leads takes the form and the outgoing amplitudes O l (k) are related to the incoming amplitudes I l (k) by where T (k) is the N ×N scattering matrix. The conservation of flux ensures the unitarity of T (k). An explicit expression for the scattering matrix is given in [16]. Here, we shall be concerned with the scattering phase defined by The scattering phase is the counterpart of the spectral counting function for compact systems. This can be best seen by considering the function d R (k) = dΘ(k) dk . It assigns a normalized Lorentzian to each scattering resonances, and it is the counterpart of the spectral density (10). An exact trace formula for d R (k) was derived in [16]. It reads, where k n − iγ n are the poles (resonances) of T (k) in the complex k plane. As in the compact case, L = B b=1 L b is the total length of the bonds in the compact part of the graph. The sum extends over all the PO's (periodic orbits) on the compact part of the graph, and goes over primitive PO's as well as their repetitions. The length of a PO is denoted by l p . The amplitudeÃ p is a product over all the scattering amplitudesσ (i) d,d ′ , encountered along the PO, times the length of the primitive PO of which p is a repetition. It is also endowed with a phase factor A d L d . The vertex scattering matricesσ (i) in the space of the directed compact bonds are sub-unitary (| detσ (i) | ≤ 1). To completẽ σ (i) to a unitary matrix a row and a colomn should be added, to take into account the coupling of the compact bonds to the lead. For this reason, the rows of the classical transition matrixW do not sum up to unity, which take into account the flux which escapes through the leads. The same mechanism is responssible also to the reduction of |Â p | relative to the corresponding |A p |. This accelerates the convergence of (22) and pushes its poles away from the real axis. A length spectrum similar to (12) is obtained from the Fourier transform of (22), and its singular support consists of 0 and the length spectrum of the compact part of the graph. The following result can be proved using the same argument as above: Theorem 2: The scattering phase Θ(k) of a non-compact metric graph, determines uniquely the connectivity and the bond lengths in the compact part of the graph, provided that -the graph is composed of a finite and simple compact part, with leads to infinity. A vertex can be coupled to at most one lead.
-the bond lengths in the compact part are rationally independent, -the vertex scattering matrices are properly connecting.
The proof follows verbatim the proof of theorem 1.

An example of isospectral graphs
We have shown that the spectral density (for compact graphs) and the resonnance density (for scattering graphs) determine uniquely the bond lengths and the the connectivity, provided that the bond lengths are rationally independent, and the vertex scattering matrices are properly connecting. We shall now construct a non trivial example of two different, yet isospectral graphs, obtained when the requirement of rational independence is relaxed.
Extending the geometric construction of [3] we produced the pair of graphs shown in Figure 1. Their bond lengths are rational combinations of two arbitrary lengths a and b, as shown in the figure. Neumann boundary conditions are imposed at the vertices. The spectra of the two graphs are the zeros of the corresponding secular functions (8), which for the present cases read: Z (I) (k) = tg(2 (a + b) k) + (23) 2 tg(a k) + 2 tg(b k) + tg((2 a + b) k) + tg((a + 2 b) k) 1 − (2 tg(a k) + tg(b k)) (tg(b k) + tg((2 a + b) k) + tg((a + 2 b) k)) Z (II) (k) = tg(2 a k) (24) 2 tg(a k) + 2 tg(b k) + tg((a + 2 b) k) + tg((2 a + 3 b) k) 1 − (tg(a k) + tg(b k) + tg((a + 2 b) k)) (tg(a k) + tg(b k) + tg((2 a + 3 b) k)) It is not an easy matter to show directly that these two different functions vanish at exactly the same values of k. However, the theorem which underlies their construction [3] guarantees this fact.