On the minimum number of eigenvalues of trees of diameter seven

L. Emilio Allem, Carlos Hoppen, Lucas Siviero Sibemberg · 2025

Read On the minimum number of eigenvalues of trees of diameter seven by L. Emilio Allem, Carlos Hoppen, Lucas Siviero Sibemberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-17603.txt.

Introduction

Allem, Hoppen, and Sibemberg count the fewest distinct eigenvalues a matrix can have when its pattern is a tree of diameter seven. Their 2025 paper builds on the seed method of Johnson and Saiago, which grows big tree realizations from small ones of the same diameter. Realizations are sorted by which seed defines them. Along the way the authors correct a result in that earlier paper. The work sharpens the map of how few tones a tree-shaped matrix can sound.

Catalog record

CREATORL. Emilio Allem, Carlos Hoppen, Lucas Siviero Sibemberg
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-17603

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the minimum number of eigenvalues of trees of diameter seven L. Emilio Allem, Carlos Hoppen, Lucas Siviero Sibemberg Abstract . The underlying graph G G of a symmetric matrix M = ( m i ​ j ) ∈ ℝ n × n M=(m_{ij})\in\mathbb{R}^{n\times n} is the graph with vertex set { v 1 , … , v n } \{v_{1},\ldots,v_{n}\} such that a pair { v i , v j } \{v_{i},v_{j}\} with i ≠ j i\neq j is an edge if and only if m i ​ j ≠ 0 m_{ij}\neq 0 . Given a graph G G , let q ⁡ ( G ) q(G) be the minimum number of distinct eigenvalues in a symmetric matrix whose underlying graph is G G . A symmetric matrix M M is said to be a realization of q ⁡ ( G ) q(G) if it has underlying graph G G and q ⁡ ( G ) q(G) distinct eigenvalues. In the case of trees, a paper by Johnson and Saiago [Johnson, C.R, and Saiago, C.M, Diameter Minimal Trees, Linear and Multilinear Algebra 64(3) (2015), 557–571.] proposed an approach by which realizations of large trees are constructed from realizations of smaller trees with the same diameter, known as seeds, which has proved to be very successful. In this paper, we discuss realizations of q ⁡ ( T ) q(T) for trees of diameter seven based on the seed that defines it, correcting a result in the aforementioned paper. 1991 Mathematics Subject Classification 05C50,15A29 1. Introduction With a (simple) graph G=(V,E) with vertex set V=\{v_{1},\ldots,v_{n}\} , we associate the set of real symmetric matrices \mathcal{S}(G)=\{M\in\mathbb{R}^{n\times n}\colon M=M^{T},(\forall i\neq j)\left[m_{ij}\neq 0\Longleftrightarrow\{v_{i},v_{j}\}\in E\right]\}, namely the set of real symmetric matrices whose nonzero off-diagonal entries are precisely the entries corresponding to the edges of G . There is no constraint on diagonal entries. We say that G is the underlying graph of a matrix M\in\mathcal{S}(G) . A parameter that has caught the attention of numerous researchers (see [ 1 , 4 , 6 ] and their references) is q(G) , the minimum number of distinct eigenvalues over all matrices in \mathcal{S}(G) , i.e., the minimum degree of the minimal polynomial of any matrix in \mathcal{S}(G) . More than computing q(G) , there has been interest in explicitly constructing a matrix M\in\mathcal{S}(G) for which the set \DSpec(M) of distinct eigenvalues of M satisfies |\DSpec(M)|=q(G) , which we call a realization of q(G) . In this paper, we address this problem for trees. Following the terminology of previous work [ 10 , 11 , 12 ] , the diameter d(T) of a tree T is the number of vertices on a longest path in T * * * In the graph theory community, it is more common to define the diameter of a tree T as the number of edges on a longest path in T . Since we shall work with trees with fixed diameter, it is easy to translate our statements with respect to this other definition. . It is not hard to show (see Leal-Duarte and Johnson [ 12 ] ) that, for any tree T , the inequality q(T)\geq d(T) holds and that it is tight for some trees. Moreover, researchers such as Barioli and Fallat [ 3 ] found examples of trees T for which q(T)>d(T) . Hence, it is natural to characterize those trees T for which q(T)=d(T) , which are called diameter minimal trees (or diminimal trees , for short). More generally, for any tree T , Johnson and Saiago [ 10 ] defined its disparity D(T)=q(T)-d(T) , so that D(T)=0 if and only if T is diminimal. Also because of [ 3 ] , we know that, for any positive integer k , there is a tree T such that D(T)>k . On the other hand, [ 10 , Theorem 4] shows that, for any d\geq 1 , the quantity C(d)=\max\{q(T)\colon d(T)=d\} is well defined. For any fixed integer d\geq 1 , it is easy to see that the set \mathcal{D}_{d} of diminimal trees of diameter d is nonempty, as the d -vertex path P_{d} lies in \mathcal{D}_{d} . Johnson and Saiago [ 10 , 11 ] have shown that the families \mathcal{D}_{d} are infinite for every d . In particular, Theorem 3 in [ 10 ] states that all trees of diameter d\leq 6 are diminimal, thus D(T)=0 for all trees such that d(T)\leq 6 . This is not true for trees of diameter d=7 , as shown in [ 3 ] . A full characterization of diminimal trees of diameter d\geq 7 is still elusive. To be better able to construct diminimal trees, Johnson and Saiago [ 10 ] defined a decomposition of the set of trees of any fixed diameter d based on a finite set of irreducible trees, known as seeds , and on an operation, known as combinatorial branch duplication , which we now describe. Given a tree T , we say that U is a branch of T at a vertex v if U is a connected component of T-v . We say that U is rooted at the vertex u\in V(U) that is adjacent to v in T . An s - combinatorial branch duplication ( s -CBD, for short) of a branch U of a tree T at vertex v results in a new tree T^{\prime} where s copies of U are appended to T at v . A tree \tilde{T} obtained from a tree T through a sequence of CBDs is called an unfolding of T . An example is depicted in Figure 1 . We shall restrict our attention to s -CBDs that keep the diameter unchanged, as done in [ 2 , 10 , 11 ] . A seed is a tree that is not an unfolding of any smaller tree of the same diameter. For example, there is a single seed of diameter d if d\in\{3,4\} , there are two seeds of diameter 5 , three seeds of diameter 6 , and twelve seeds of diameter 7 . The latter are depicted in Figure 2 . u v (a) Tree T of diameter 7 rooted at v . u v (b) 2 -CBD of U (the branch of T-v that contains u ) at v . Figure 1 . The tree in (B) is an unfolding of the tree T in (A). v_{0} (a) S^{(1)}_{7} v_{0} (b) S^{(4)}_{7} v_{0} (c) S^{(2)}_{7} v_{0} (d) S^{(5)}_{7} v_{0} (e) S^{(3)}_{7} v_{0} (f) S^{(6)}_{7} v_{0} (g) S^{(7)}_{7} v_{0} (h) S^{(10)}_{7} v_{0} (i) S^{(8)}_{7} v_{0} (j) S^{(11)}_{7} v_{0} (k) S^{(9)}_{7} v_{0} (l) S^{(12)}_{7} Figure 2 . The twelve seeds of diameter 7 , denoted S_{7}^{(1)},\ldots,S_{7}^{(12)} . As shown in [ 10 ] (see also [ 11 , 9 ] ), two of the main reasons to consider seeds are the property that, for every d\in\mathbb{N} , there exist finitely many seeds of diameter d , and the property that every tree with diameter d may be obtained as the unfolding of a unique seed of diameter d . In addition to this, Braga, Oliveira, Trevisan and the current authors [ 2 ] have shown that, for any given diameter d ,

Read the complete text