Search

The goal of this article is to display a Q -polynomial structure for the Attenuated Space poset A q (N , M). The poset A q (N , M) is briefly described as follows. Start with an (N + M) -dimensional vector space H over a finite field with q elements. Fix an M -dimensional subspace h of H. The vertex set X of A q (N , M) consists of the subspaces of H that have zero intersection with h. The partial order on X is the inclusion relation. The Q -polynomial structure involves two matrices A , A ⁎ ∈ Mat X (C) with the following entries. For y , z ∈ X the matrix A has (y , z) -entry 1 (if y covers z); q dim y (if z covers y); and 0 (if neither of y , z covers the other). The matrix A ⁎ is diagonal, with (y , y) -entry q − dim y for all y ∈ X. By construction, A ⁎ has N + 1 eigenspaces. By construction, A acts on these eigenspaces in a (block) tridiagonal fashion. We show that A is diagonalizable, with 2 N + 1 eigenspaces. We show that A ⁎ acts on these eigenspaces in a (block) tridiagonal fashion. Using this action, we show that A is Q -polynomial. We show that A , A ⁎ satisfy a pair of relations called the tridiagonal relations. We consider the subalgebra T of Mat X (C) generated by A , A ⁎. We show that A , A ⁎ act on each irreducible T -module as a Leonard pair. [ABSTRACT FROM AUTHOR]

A graph is determined by its spectrum if there is not another graph with the same spectrum. Cámara and Haemers proved that the graph K n ∖ C k , obtained from the complete graph K n with n vertices by deleting all edges of a cycle C k with k vertices, is determined by its spectrum for k ∈ { 3 , 4 , 5 } , but not for k = 6. In this paper, we show that k = 6 is the unique exception for the spectral determination of K n ∖ C k. [ABSTRACT FROM AUTHOR]

We compute the elementary divisors of the adjacency and Laplacian matrices of families of polar graphs. These graphs have as vertices the isotropic one-dimensional subspaces of finite vector spaces with respect to non-degenerate forms, with adjacency given by orthogonality. [ABSTRACT FROM AUTHOR]

The critical group of a finite connected graph is an abelian group defined by the Smith normal form of its Laplacian. Let q be a power of a prime and H be a multiplicative subgroup of K = F q. By Cay (K , H) we denote the Cayley graph on the additive group of K with "connection" set H. A strongly regular graph of the form Cay (K , H) is called a cyclotomic strongly regular graph. Let ℓ > 2 and p be primes such that p is primitive (mod ℓ). We compute the critical groups of a family of cyclotomic strongly regular graphs for which q = p (ℓ − 1) t (with t ∈ N) and H is the unique multiplicative subgroup of order k = q − 1 ℓ. These graphs were first discovered by van Lint and Schrijver in [24]. [ABSTRACT FROM AUTHOR]

Abstract Motivated by the study of genomes evolving by reversals, we consider pseudograph transformations known as "pressing sequences". In particular, we address the question of when a graph has precisely one pressing sequence resulting in the empty graph, thus answering an question from Cooper and Davis (2015) [13]. We characterize such "uniquely pressable" graphs, count the number of them on a given number of vertices, and provide a polynomial-time recognition algorithm. We conclude with several open questions. [ABSTRACT FROM AUTHOR]

For every finite Coxeter group Γ, each positive braid in the corresponding braid group admits a unique decomposition as a finite sequence of elements of Γ, the so-called Garside-normal form. The study of the associated adjacency matrix Adj ( Γ ) allows to count the number of Garside-normal form of a given length. In this paper we prove that the characteristic polynomial of Adj ( B n ) divides the one of Adj ( B n + 1 ) . The key point is the use of a Hopf algebra based on signed permutations. A similar result was already known for the type A . We observe that this does not hold for type D . The other Coxeter types ( I , E , F and H ) are also studied. [ABSTRACT FROM AUTHOR]

Let Z n be the ring of residue classes modulo n , and let Z n ⁎ be the group of its units. 90 years ago, Brauer obtained a formula for the number of representations of c ∈ Z n as the sum of k units. Recently, Yang and Tang (2015) [6] gave a formula for the number of solutions of the equation x 1 2 + x 2 2 = c with x 1 , x 2 ∈ Z n ⁎ . In this paper, we generalize this result. We find an explicit formula for the number of solutions of the equation x 1 2 + ⋯ + x k 2 = c with x 1 , … , x k ∈ Z n ⁎ . [ABSTRACT FROM AUTHOR]

Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random. [ABSTRACT FROM AUTHOR]

Graph eigenvalues are examples of totally real algebraic integers, i.e. roots of real-rooted monic polynomials with integer coefficients. Conversely, the fact that every totally real algebraic integer occurs as an eigenvalue of some finite graph is a deep and remarkable result, conjectured forty years ago by Hoffman, and proved seventeen years later by Estes. This short paper provides an independent and elementary proof of a stronger statement, namely that the graph may actually be chosen to be a tree. As a by-product, our result implies that the atoms of the limiting spectrum of n × n symmetric matrices with independent Bernoulli ( c n ) entries are exactly the totally real algebraic integers. This settles an open problem raised by Ben Arous (2010). [ABSTRACT FROM AUTHOR]

Abstract: The Randić index R of a graph G is defined as the sum of over all edges of G, where denotes the degree of a vertex in G. is the largest eigenvalue of the signless Laplacian matrix of G, where D is the diagonal matrix with degrees of the vertices on the main diagonal and A is the adjacency matrix of G. Hansen and Lucas [18] conjectured (1) and equality holds for and (2) with equality if and only if for and for , respectively. In this paper, we prove the conjecture (1) and obtain a result very close to the conjecture (2). Moreover, we give some results relating harmonic index and the largest eigenvalue of the adjacency matrix. [Copyright &y& Elsevier]

Abstract: A five-channel (1H, 19F, 31P, 27Al, 13C) 2.5mm magic-angle-spinning (MAS) nuclear magnetic resonance (NMR) probe is used in combination with three separate receivers for the parallel acquisitions of one (1D) and two-dimensional (2D) NMR spectra in model fluorinated aluminophosphate and porous Al-based metal-organic framework (MOF). Possible combinations to record simultaneously spectra using this set-up are presented, including (i) parallel acquisitions of quantitative 1D NMR spectra of solids containing nuclei with contrasted T 1 relaxation rates and (ii) parallel acquisitions of 2D heteronuclear NMR spectra. In solids containing numerous different NMR-accessible nuclei, the number of NMR experiments that have to be acquired to get accurate structural information is high. The strategy we present here, i.e. the multiplication of both the number of irradiation channels in the probe and the number of parallel receivers, offers one possibility to optimize this measurement time. [Copyright &y& Elsevier]

Abstract: Methods of enumeration of spanning trees in a finite graph, a problem related to various areas of mathematics and physics, have been investigated by many mathematicians and physicists. A graph G is said to be n-rotational symmetric if the cyclic group of order n is a subgroup of the automorphism group of G. Some recent studies on the enumeration of spanning trees and the calculation of their asymptotic growth constants on regular lattices with toroidal boundary condition were carried out by physicists. A natural question is to consider the problem of enumeration of spanning trees of lattices with cylindrical boundary condition, which are the so-called rotational symmetric graphs. Suppose G is a graph of order N with n-rotational symmetry and all orbits have size n, which has n isomorphic induced subgraphs . In this paper, we prove that if there exists no edge between and for , then the number of spanning trees of G can be expressed in terms of the product of the weighted enumerations of spanning trees of n graphs ''s for , where has vertices if and vertices otherwise. As applications we obtain explicit expressions for the numbers of spanning trees and asymptotic tree number entropies for five lattices with cylindrical boundary condition in the context of physics. [Copyright &y& Elsevier]

Abstract: Analyzing human crowds is an important issue in video surveillance and is a challenging task due to their nature of non-rigid shapes. In this paper, optical flows are first estimated and then used for a clue to cluster human crowds into groups in unsupervised manner using our proposed method of adjacency-matrix based clustering (AMC). While the clusters of human crowds are obtained, their behaviors with attributes, orientation, position and crowd size, are characterized by a model of force field. Finally, we can predict the behaviors of human crowds based on the model and then detect if any anomalies of human crowd(s) present in the scene. Experimental results obtained by using extensive dataset show that our system is effective in detecting anomalous events for uncontrolled environment of surveillance videos. [Copyright &y& Elsevier]

Abstract: Let k be a positive integer and let G be a graph of order . It is proved that the sum of k largest eigenvalues of G is at most . This bound is shown to be best possible in the sense that for every k there exist graphs whose sum is . A generalization to arbitrary symmetric matrices is given. [Copyright &y& Elsevier]

We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented. [Copyright &y& Elsevier]