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]