Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Ordering uniform supertrees by their spectral radii

A supertree is a connected and acyclic hypergraph. For a hypergraph H, the maximal modulus of the eigenvalues of its adjacency tensor is called the spectral radius of H. By applying the operation of moving edges on hypergraphs and the weighted incidence matrix method, we determine the ninth and the tenth k-uniform supertrees with the largest spectral radii among all k-uniform supertrees on n vertices, which extends the known result.     

On the Spectrum of the Generalised Petersen Graphs

We show that the gap between the two greatest eigenvalues of the generalised Petersen graphs P(n, k) tends to zero as \(n \rightarrow \infty \). Moreover, we provide explicit upper bounds on the size of this gap. It follows that these graphs have poor expansion properties for large values of n. We also show that there is a positive proportion of the eigenvalues of P(n, k) tending to three.     

Unicyclic graphs with bicyclic inverses

A graph is nonsingular if its adjacency matrix A(G) is nonsingular. The inverse of a nonsingular graph G is a graph whose adjacency matrix is similar to A(G)^?1 via a particular type of similarity. Let H denote the class of connected bipartite graphs with unique perfect matchings. Tifenbach and Kirkland (2009) characterized the unicyclic graphs in H which possess unicyclic inverses. We present a characterization of unicyclic graphs in H which possess bicyclic inverses.     

On the traces of Sobolev functions on Lipschitz surfaces

Functions from the Sobolev spaces W _p ¹(Q) are considered on a unit cube Q ? R ⁿ , and the properties of their traces on Lipschitz surfaces are examined. The relation is found between the Hölder exponent α and the Hausdorff dimension of the family of poor k-dimensional planes Γ on which the traces do not belong to C ^α(Γ). For the corresponding families of poor k-dimensional Lipschitz surfaces, estimates in terms of p-modules are obtained.     

Spectral (isotropic) manifolds and their dimension

A set of n × n symmetric matrices whose ordered vector of eigenvalues belongs to a fixed set in ?ⁿ is called spectral or isotropic. In this paper, we establish that every locally symmetric C^k submanifoldMof ?ⁿ gives rise to a C^k spectral manifold for k ∈ {2, 3, …,∞,ω}. An explicit formula for the dimension of the spectral manifold in terms of the dimension and the intrinsic properties of M is derived. This work builds upon the results of Sylvester and ?ilhavý and uses characteristic properties of locally symmetric submanifolds established in recent works by the authors.     

Extreme value analysis for the sample autocovariance matrices of heavy-tailed multivariate time series

We provide some asymptotic theory for the largest eigenvalues of a sample covariance matrix of a p-dimensional time series where the dimension p = p _n converges to infinity when the sample size n increases. We give a short overview of the literature on the topic both in the light- and heavy-tailed cases when the data have finite (infinite) fourth moment, respectively. Our main focus is on the heavy-tailed case. In this case, one has a theory for the point process of the normalized eigenvalues of the sample covariance matrix in the iid case but also when rows and columns of the data are linearly dependent. We provide limit results for the weak convergence of these point processes to Poisson or cluster Poisson processes. Based on this convergence we can also derive the limit laws of various function als of the ordered eigenvalues such as the joint convergence of a finite number of the largest order statistics, the joint limit law of the largest eigenvalue and the trace, limit laws for successive ratios of ordered eigenvalues, etc. We also develop some limit theory for the singular values of the sample autocovariance matrices and their sums of squares. The theory is illustrated for simulated data and for the components of the S&P 500 stock index.     

Order of magnitude of multiple Fourier coefficients of functions of bounded <Emphasis Type="Italic">p</Emphasis>-variation

For a Lebesgue integrable complex-valued function f defined over the n-dimensional torus \(\mathbb{T}^n \):= [0, 2π) ⁿ , let \(\hat f\)(k) denote the Fourier coefficient of f, where k = (k ₁, … k _n ) ∈ ? ⁿ . In this paper, defining the notion of bounded p-variation (p ≧ 1) for a function from [0, 2π] ⁿ to ? in two diffierent ways, the order of magnitude of Fourier coefficients of such functions is studied. As far as the order of magnitude is concerned, our results with p = 1 give the results of Móricz [5] and Fülöp and Móricz [3].     

On the additive complexity of GCD and LCM matrices

In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the n × n matrix formed by the numbers GCD^r(i, k) over the basis {x + y} is asymptotically equal to rn log²n as n→∞, and the complexity of the n × n matrix formed by the numbers LCM^r(i, k) over the basis {x + y,?x} is asymptotically equal to 2rn log₂n as n→∞.     

Tensor convolutions and Hankel tensors

Let A be an mth order n-dimensional tensor, where m, n are some positive integers and N:= m(n?1). Then A is called a Hankel tensor associated with a vector v ∈ ?^N+1 if A_σ = v _k for each k = 0, 1,...,N whenever σ = (i₁,..., i_m) satisfies i₁ +· · ·+i_m = m+k. We introduce the elementary Hankel tensors which are some special Hankel tensors, and present all the eigenvalues of the elementary Hankel tensors for k = 0, 1, 2. We also show that a convolution can be expressed as the product of some third-order elementary Hankel tensors, and a Hankel tensor can be decomposed as a convolution of two Vandermonde matrices following the definition of the convolution of tensors. Finally, we use the properties of the convolution to characterize Hankel tensors and (0,1) Hankel tensors.     

Bounds for the signless Laplacian energy of digraphs

Let G be a digraph with n vertices, a arcs, c ₂ directed closed walks of length 2. Let q1; q2;:::; q _n be the eigenvalues of the signless Laplacian matrix of G. The signless Laplacian energy of a digraph G is defined as E _SL (G) = \(\sum\limits_{i = 1}^n {\left| {{q_i} - \frac{a}{n}} \right|} \). In this paper, some lower and upper bounds are derived for the signless Laplacian energy of digraphs.     

Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M ⁿ providing that M ⁿ is not k-connected?     

On generalized Heawood inequalities for manifolds: a van Kampen–Flores-type nonembeddability result

The fact that the complete graph K₅ does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M (other than the Klein bottle) if and only if (n?3)(n?4) ≤ 6b₁(M), where b₁(M) is the first Z₂-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_n+1) embeds in R^2k if and only if n ≤ 2k + 1.Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k ? 1)-connected 2k-manifold with kth Z₂-Betti number b_k only if the following generalized Heawood inequality holds: ( _k+1 ^n?k?1 ) ≤ ( _k+1 ^2k+1 )b_k. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem.In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z₂-Betti number bk, then n ≤ 2b_k( _k ^2k+2 )+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k?1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.     

Almost Sure Limit of the Smallest Eigenvalue of Some Sample Correlation Matrices

Let X ⁽ⁿ⁾=(X _ij ) be a p×n data matrix, where the n columns form a random sample of size n from a certain p-dimensional distribution. Let R ⁽ⁿ⁾=(ρ _ij ) be the p×p sample correlation coefficient matrix of X ⁽ⁿ⁾, and \(S^{(n)}=(1/n)X^{(n)}(X^{(n)})^{\ast}-\bar{X}\bar{X}^{\ast}\) be the sample covariance matrix of X ⁽ⁿ⁾, where \(\bar{X}\) is the mean vector of the n observations. Assuming that X _ij are independent and identically distributed with finite fourth moment, we show that the smallest eigenvalue of R ⁽ⁿ⁾ converges almost surely to the limit \((1-\sqrt{c}\,)^{2}\) as n→∞ and p/n→c∈(0,∞). We accomplish this by showing that the smallest eigenvalue of S ⁽ⁿ⁾ converges almost surely to \((1-\sqrt{c}\,)^{2}\).     

Phragmén-Lindelöf Theorems and p-harmonic Measures for Sets Near Low-dimensional Hyperplanes

We prove estimates of a p-harmonic measure, p∈(n?m,∞], for sets in Rⁿ which are close to an m-dimensional hyperplane Λ?Rⁿ, m∈[0,n?1]. Using these estimates, we derive results of Phragmén-Lindelöf type in unbounded domains Ω?Rⁿ?Λ for p-subharmonic functions. Moreover, we give local and global growth estimates for p-harmonic functions, vanishing on sets in Rⁿ, which are close to an m-dimensional hyperplane.     

A Fiedler-like theory for the perturbed Laplacian

The perturbed Laplacian matrix of a graph G is defined as DL = D?A, where D is any diagonal matrix and A is a weighted adjacency matrix of G. We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use the notion of Perron component for the perturbed Laplacian matrix of a graph and show how its second smallest eigenvalue can be characterized using this definition.     

Calculating the Isotropic Subspace of a Symmetric Quasi-Definite Matrix

Solutions to the sesquilinear matrix equation X*DX + AX + X*B + C = 0, where all matrices are of size n × n, are put in correspondence with n-dimensional neutral (or isotropic) subspaces of the associated matrix M of order 2n. A way of constructing such subspaces is proposed for when M is a symmetric quasi-definite matrix of the (n, n) type.     

Distance mean-regular graphs

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let \(\Gamma \) be a graph with vertex set V, diameter D, adjacency matrix \(\varvec{A}\), and adjacency algebra \(\mathcal{A}\). Then, \(\Gamma \) is distance mean-regular when, for a given \(u\in V\), the averages of the intersection numbers \(p_{ij}^h(u,v)=|\Gamma _i(u)\cap \Gamma _j(v)|\) (number of vertices at distance i from u and distance j from v) computed over all vertices v at a given distance \(h\in \{0,1,\ldots ,D\}\) from u, do not depend on u. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of \(\Gamma \) and, hence, they generate a subalgebra of \(\mathcal{A}\). Some other algebras associated to distance mean-regular graphs are also characterized.     

On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n?k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n?k.