Search

We exhibit non-switching-isomorphic signed graphs that share a common underlying graph and common chromatic polynomials, thereby answering a question posed by Zaslavsky. For various joins of all-positive or all-negative signed complete graphs, we derive a closed-form expression for their chromatic polynomials. As a generalisation of the chromatic polynomials for a signed graph, we introduce a new pair of bivariate chromatic polynomials. We establish recursive dominating-vertex deletion formulae for these bivariate chromatic polynomials. Finally, we show that for certain families of signed threshold graphs, isomorphism is equivalent to the equality of bivariate chromatic polynomials., Comment: 24 pages

We characterise graphs that have three distinct eigenvalues and coherent ranks 8 and 9, linking the former to certain symmetric 2-designs and the latter to specific quasi-symmetric 2-designs. This characterisation leads to the discovery of a new biregular graph with three distinct eigenvalues. Additionally, we demonstrate that the coherent rank of a triregular graph with three distinct eigenvalues is at least 14. Finally, we introduce a conjecturally infinite family of biregular graphs with three distinct eigenvalues, obtained by switching the block graphs of orthogonal arrays., Comment: 36 pages

Random matrix theory is a useful tool in the study of the physics of multiple scattering systems, often striking a balance between computation speed and physical rigour. Propagation of waves through thick disordered media, as arises in for example optical scattering or electron transport, typically necessitates cascading of multiple random matrices drawn from an underlying ensemble for thin media, greatly increasing computational burden. Here we propose a dual pool based bootstrapping approach to speed up statistical studies of scattering in thick random media. We examine how potential matrix reuse in a pool based approach can impact statistical estimates of population averages. Specifically, we discuss how both bias and additional variance in the sample mean estimator are introduced through bootstrapping. In the diffusive scattering regime, the extra estimator variance is shown to originate from samples in which cascaded transfer matrices are permuted matrix products. Through analysis of the combinatorics and cycle structure of permutations we quantify the resulting correlations. Proofs of several analytic formulae enumerating the frequency with which correlations of different strengths occur are derived. Extension to the ballistic regime is briefly considered., Comment: 1 figure, 3 tables, 13 pages, submitted to journal 11 Sep 23. Supplementary movies available upon request

We provide a method to construct $t$-designs from weighing matrices and walk-regular graphs. One instance of our method can produce a $3$-design from any (symmetric or skew-symmetric) conference matrix, thereby providing a partial answer to a question of Gunderson and Semeraro JCTB 2017. We explore variations of our method on some matrices that satisfy certain combinatorial restrictions. In particular, we show that there exist various infinite families of partially balanced incomplete block designs with block size four on the binary Hamming schemes and the $3$-class association schemes attached to symmetric designs, and regular pairwise balanced designs with block sizes three and four., Comment: 31 pages

We show that the maximum cardinality of an equiangular line system in $\mathbb R^{18}$ is at most $59$. Our proof includes a novel application of the Jacobi identity for complementary subgraphs. In particular, we show that there does not exist a graph whose adjacency matrix has characteristic polynomial $(x-22)(x-2)^{42} (x+6)^{15} (x+8)^2$., Comment: 26 pages. Updated to match the published, journal version

We investigate properties of signed graphs that have few distinct eigenvalues together with a symmetric spectrum. Our main contribution is to determine all signed $(0,2)$-graphs with vertex degree at most $6$ that have precisely two distinct eigenvalues $\pm \lambda$. Next, we consider to what extent induced subgraphs of signed graph with two distinct eigenvalues $\pm \lambda$ are determined by their spectra. Lastly, we classify signed $(0,2)$-graphs that have a symmetric spectrum with three distinct eigenvalues and give a partial classification for those with four distinct eigenvalues., Comment: 21 pages, 3 figures

We investigate spectral conditions on Hermitian matrices of roots of unity. Our main results are conjecturally sharp upper bounds on the number of residue classes of the characteristic polynomial of such matrices modulo ideals generated by powers of $(1-\zeta)$, where $\zeta$ is a root of unity. We also prove a generalisation of a classical result of Harary and Schwenk about a relation for traces of powers of a graph-adjacency matrix, which is a crucial ingredient for the proofs of our main results., Comment: 25 pages

We show that the maximum cardinality of an equiangular line system in 17 dimensions is 48, thereby solving a longstanding open problem. Furthermore, by giving an explicit construction, we improve the lower bound on the maximum cardinality of an equiangular line system in 18 dimensions to 57., Comment: 39 pages. Contains tables referenced in the journal version. arXiv admin note: text overlap with arXiv:2002.08085

We investigate equiangular lines in finite orthogonal geometries, focusing specifically on equiangular tight frames (ETFs). In parallel with the known correspondence between real ETFs and strongly regular graphs (SRGs) that satisfy certain parameter constraints, we prove that ETFs in finite orthogonal geometries are closely aligned with a modular generalization of SRGs. The constraints in our finite field setting are weaker, and all but~18 known SRG parameters on $v \leq 1300$ vertices satisfy at least one of them. Applying our results to triangular graphs, we deduce that Gerzon's bound is attained in finite orthogonal geometries of infinitely many dimensions. We also demonstrate connections with real ETFs, and derive necessary conditions for ETFs in finite orthogonal geometries. As an application, we show that Gerzon's bound cannot be attained in a finite orthogonal geometry of dimension~5.

We introduce the study of frames and equiangular lines in classical geometries over finite fields. After developing the basic theory, we give several examples and demonstrate finite field analogs of equiangular tight frames (ETFs) produced by modular difference sets, and by translation and modulation operators. Using the latter, we prove that Gerzon's bound is attained in each unitary geometry of dimension $d = 2^{2l+1}$ over the field $\mathbb{F}_{3^2}$. We also investigate interactions between complex ETFs and those in finite unitary geometries, and we show that every complex ETF implies the existence of ETFs with the same size over infinitely many finite fields.

In this paper, we study the order of a maximal clique in an amply regular graph with a fixed smallest eigenvalue by considering a vertex that is adjacent to some (but not all) vertices of the maximal clique. As a consequence, we show that if a strongly regular graph contains a Delsarte clique, then the parameter $\mu$ is either small or large. Furthermore, we obtain a cubic polynomial that assures that a maximal clique in an amply regular graph is either small or large (under certain assumptions). Combining this cubic polynomial with the claw-bound, we rule out an infinite family of feasible parameters $(v,k,\lambda,\mu)$ for strongly regular graphs. Lastly, we provide tables of parameters $(v,k,\lambda,\mu)$ for nonexistent strongly regular graphs with smallest eigenvalue $-4, -5, -6$ or $-7$.

We show that the maximum cardinality of an equiangular line system in 14 and 16 dimensions is 28 and 40, respectively, thereby solving a longstanding open problem. We also improve the upper bounds on the cardinality of equiangular line systems in 19 and 20 dimensions to 74 and 94, respectively., Comment: 23 pages

We exhibit a new construction of edge-regular graphs with regular cliques that are not strongly regular. The infinite family of graphs resulting from this construction includes an edge-regular graph with parameters $(24,8,2)$. We also show that edge-regular graphs with $1$-regular cliques that are not strongly regular must have at least $24$ vertices., Comment: 7 pages

We give constructions of some special cases of $[n,k]$ Reed-Solomon codes over finite fields of size at least $n$ and $n+1$ whose generator matrices have constrained support. Furthermore, we consider a generalisation of the GM-MDS conjecture proposed by Lovett in 2018. We show that Lovett's conjecture is false in general and we specify when the conjecture is true., Comment: 21 pages

For $e$ a positive integer, we find restrictions modulo $2^e$ on the coefficients of the characteristic polynomial $\chi_S(x)$ of a Seidel matrix $S$. We show that, for a Seidel matrix of order $n$ even (resp. odd), there are at most $2^{\binom{e-2}{2}}$ (resp. $2^{\binom{e-2}{2}+1}$) possibilities for the congruence class of $\chi_S(x)$ modulo $2^e\mathbb Z[x]$. As an application of these results, we obtain an improvement to the upper bound for the number of equiangular lines in $\mathbb R^{17}$, that is, we reduce the known upper bound from $50$ to $49$., Comment: 21 pages, fixed typo in Lemma 2.1

We show that the Smith normal form of a skew-symmetric D-optimal design of order $n\equiv 2\pmod{4}$ is determined by its order. Furthermore, we show that the Smith normal form of such a design can be written explicitly in terms of the order $n$, thereby proving a recent conjecture of Armario. We apply our result to show that certain D-optimal designs of order $n\equiv 2\pmod{4}$ are not equivalent to any skew-symmetric D-optimal design. We also provide a correction to a result in the literature on the Smith normal form of D-optimal designs., Comment: 19 pages

We exhibit infinitely many examples of edge-regular graphs that have regular cliques and that are not strongly regular. This answers a question of Neumaier from 1981., Comment: 11 pages; accepted to the European Journal of Combinatorics

If $\mu_m$ and $d_m$ denote, respectively, the $m$-th largest Laplacian eigenvalue and the $m$-th largest vertex degree of a graph, then $\mu_m \geqslant d_m-m+2$. This inequality was conjectured by Guo in 2007 and proved by Brouwer and Haemers in 2008. Brouwer and Haemers gave several examples of graphs achieving equality, but a complete characterisation was not given. In this paper we consider the problem of characterising graphs satisfying $\mu_m = d_m-m+2$. In particular we give a full classification of graphs with $\mu_m = d_m-m+2 \leqslant 1$., Comment: corrected typo

We develop the theory of equiangular lines in Euclidean spaces. Our focus is on the question of when a Seidel matrix having precisely three distinct eigenvalues has a regular graph in its switching class. We make some progress towards an answer to this question by finding some necessary conditions and some sufficient conditions. Furthermore, we show that the cardinality of an equiangular line system in $18$ dimensional Euclidean space is at most $60$., Comment: 17 pages

We determine new upper bounds for the clique numbers of strongly regular graphs in terms of their parameters. These bounds improve on the Delsarte bound for infinitely many feasible parameter tuples for strongly regular graphs, including infinitely many parameter tuples that correspond to Paley graphs., Comment: 13 pages

It is proved that for any finite connected graph $G$, there exists an orientation of $G$ such that the spectral radius of the corresponding Hermitian adjacency matrix is smaller or equal to the spectral radius of the universal cover of $G$ (with equality if and only if $G$ is a tree). This resolves a problem proposed by Mohar. The proof uses the method of interlacing families of polynomials that was developed by Marcus, Spielman, and Srivastava in their seminal work on the existence of infinite families of Ramanujan graphs.

We show that the existence of $\{\pm 1\}$-matrices having largest possible determinant is equivalent to the existence of certain tournament matrices. In particular, we prove a recent conjecture of Armario. We also show that large submatrices of conference matrices are determined by their spectrum., Comment: 14 pages

We classify the connected graphs with precisely three distinct eigenvalues and second largest eigenvalue at most 1., Comment: 20 pages

We consider nonregular graphs having precisely three distinct eigenvalues. The focus is mainly on the case of graphs having two distinct valencies and our results include constructions of new examples, structure theorems, valency constraints, and a classification of certain special families of such graphs. We also present a new example of a graph with three valencies and three eigenvalues of which there are currently only finitely many known examples., Comment: 28 pages

We give a structural classification of edge-signed graphs with smallest eigenvalue greater than -2. We prove a conjecture of Hoffman about the smallest eigenvalue of the line graph of a tree that was stated in the 1970s. Furthermore, we prove a more general result extending Hoffman's original statement to all edge-signed graphs with smallest eigenvalue greater than -2. Our results give a classification of the special graphs of fat Hoffman graphs with smallest eigenvalue greater than -3., Comment: 25 pages

We solve Lehmer's problem for a class of polynomials arising from Hermitian matrices over the Eisenstein and Gaussian integers, that is, we show that all such polynomials have Mahler measure at least Lehmer's number \tau_0 = 1.17628... .

Building on the classification of all characteristic polynomials of integer symmetric matrices having small span (span less than 4), we obtain a classification of small-span polynomials that are the characteristic polynomial of a Hermitian matrix over some quadratic integer ring. Taking quadratic integer rings as our base, we obtain as characteristic polynomials some low-degree small-span polynomials that are not the characteristic (or minimal) polynomial of any integer symmetric matrix., Comment: 16 pages

We classify all cyclotomic matrices over real quadratic integer rings and we show that this classification is the same as classifying cyclotomic matrices over the compositum all real quadratic integer rings. Moreover, we enumerate a related class of symmetric matrices; those matrices whose eigenvalues are contained inside the interval [-2,2] but whose characteristic polynomials are not in Z[x]., Comment: 13 pages

We classify all cyclotomic matrices over the Eisenstein and Gaussian integers, that is, all Hermitian matrices over the Eisenstein and Gaussian integers that have all their eigenvalues in the interval [-2, 2]., Comment: 24 pages