Event Details


The Diamant symposium of Fall 2024 will take place on Thursday 21 and Friday 22 November in De Werelt (Lunteren).

Confirmed invited speakers are Krystal Guo (UvA), Jan van de Heuvel (LSE), Erik Jan van Leeuwen (UU) and Alina Ostafe (UNSW Sydney).

How to contribute a talk

PhD students and postdocs are warmly welcomed to submit a contributed talk (15-20 mins.) to the symposium. In the registration form (see below) there is an option to submit title and abstract. Alternatively, after registration, a title and abstract can be sent at a later date.

Conference fee & Accommodation

The symposium hotel is De Werelt in Lunteren. There is full DIAMANT support for DIAMANT members, meaning that we cover lunches and coffee breaks on both days, dinner on Thursday, accommodation, and breakfast on Friday. DIAMANT members are those people listed here, as well as their research group members.

Speakers and abstracts

INVISIBLE

Krystal Guo (University of Amsterdam)

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.

Jan van de Heuvel (London School of Economics and Political Science)

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?

Erik Jan van Leeuwen (Utrecht University)

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.

Alina Ostafe (The University of New South Wales)

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.

 

Sign up for this event

Registration is required and can be done here.