DIAMANT Symposium Autumn 2024

Cubic graphs with no eigenvalues in (-1,1)

We prove that, with the exception of two infinite families and 14 sporadic examples, all connected cubic graphs have at least one eigenvalue in the open interval $(-1,1)$. This result is motivated by questions in chemical graph theory, particularly concerning the HOMO-LUMO gap, a measure of molecular stability. Fowler and Pisanski conjectured that, for all but a finite number of subcubic graphs, have their median eigenvalues in [-1,1], which links the HOMO-LUMO problem to spectral graph theory. Our work also relates to various spectral gap problems. Specifically, we show that the interval $(-1,1)$ is a maximal spectral gap for non-bipartite cubic graphs. Our techniques including examination of various substructure and an application of the classification of generalized line graphs. This is based on joint work with Gordon Royle.

Combinatorics of Reconfiguration: Ideas, Applications, Algorithms and Structures

Many mathematical puzzles and problems can be formulated as “Can I transform configuration 1 into configuration 2, if only certain (local) operations are allowed?”. An example of such a question is: given a certain position of the Rubik’s Cube, is it possible to go back to the position with all sides of one colour (and without taking the cube apart!)? A more mathematical example is: given two valid assignments of a logical expression, can I transform the first assignment into the second one, by changing the truth value one variable at a time, and always maintaining a solution of the expression? A final example is: given two k-colourings of a graph, can I transform the first k-colouring into the second one, by recolouring one vertex at a time, and always maintaining a proper k-colouring?

In this talk we shall give an overview of some older and more recent work on this type of problem. In particular we will look at two aspects. What can we say about the computational complexity of the problems: how hard is it to decide if it possible to transform one configuration to another one? And also, if we look at the space of all possible configurations, connected by allowed operations, what kind of structure does that give?

Complexity Framework for Forbidden Subgraphs and Beyond

For any finite set H = H1,…,Hp of graphs, a graph is H-subgraph-free if it does not contain any of H1,…,Hp as a subgraph. We give a new framework that precisely classifies if problems are “efficiently solvable” or “computationally hard” for H-subgraph-free graphs, depending on H. To illustrate the broad applicability of our framework, we study partitioning, covering and packing problems, network design problems and width parameter problems. We apply the framework to obtain a dichotomy (depending on H) between polynomial-time solvability and NP-completeness of those problems. For other problems we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Along the way we unify and strengthen known results from the literature. We also discuss recent insights into the complexity on H-subgraph-free graphs of problems that do not fall within the framework.

On some arithmetic statistics for integer matrices

We consider the set $\mathcal{M}_n(\mathbb{Z}; H))$ of $n\times n$-matrices with integer elements of size at most $H$ and obtain a new upper bound on the number of matrices from $\mathcal{M}_n(\mathbb{Z}; H)$ with a given characteristic polynomial $f \in\mathbb{Z}[X]$, which is uniform with respect to $f$. This complements the asymptotic formula of A. Eskin, S. Mozes and N. Shah (1996) in which $f$ has to be fixed and irreducible. We use our result to address various other questions of arithmetic statistics for matrices from $\mathcal{M}_n(\mathbb{Z}; H)$, eg satisfying certain multiplicative relations. Some of these problems generalise those studied in the scalar case $n=1$ by F. Pappalardi, M. Sha, I. E. Shparlinski and C. L. Stewart (2018) with an obvious distinction due to the non-commutativity of matrices.

Joint works with Kamil Bulinski, Philipp Habegger and Igor Shparlinski.