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.

The Logarithmic Jacobian and extension of torsors over families of degenerating curves

Molcho and Wise constructed the log Picard group, a canonical compactification of the Picard group of families of nodal curves that is smooth, proper and possesses a group structure, but which can only be represented in the category of logarithmic spaces. Afterwards, it was shown that the restriction of this log Picard group to the degree zero log line bundles – which gives the so called Logarithmic Jacobian- is in fact the log Néron model of the Jacobian of the smooth locus.
In this talk, I will start by explaining why log geometry provides a natural setting for the problem of compactification. Then, I will show that the Logarithmic Jacobian classifies finite log torsors over families of nodal curves, generalizing the classical situation for smooth curves. Finally, we will see that the Néron property of the Log Jacobian allows to get a result on extending fppf torsors into log torsors over families of nodal curves.
This is a joint work with Thibault Poiret.

Formally certifying rings of integers

Formalizing mathematics involves teaching a computer mathematical definitions, theorems, and proofs, which can then be automatically checked for correctness. Crucial to formalizing number-theoretical results and algorithms is verifying the ring of integers of an explicitly given number field. But, unlike with a traditional computer algebra system, every computation step needs to be formally justified, including all the underlying theoretical foundations. In this talk, I will start with a general introduction to formalizing mathematics, particularly in the Lean proof assistant. I will then discuss a formal certificate for the ring of integers, which works locally prime-by-prime and only requires the verification of simple equalities aided by Lean’s automation.

On elliptic curves congruent modulo 23 to y^2=x^3-23

Let p be an odd prime and E, F be two elliptic curves over Q. We say that E and F are congruent modulo p if, as modules over Gal(Qbar/Q), their p-torsion subgroups are isomorphic. The study of such situations dates back to works of Serre and Mazur. While families of examples are known for p <= 13, such congruences are expected to be much rarer for large primes, a claim known as the Frey-Mazur conjecture. After recalling this background, I will sketch the proof strategy of the following result, proved in my PhD thesis: “let E_{23} be the elliptic curve with equation y^2=x^3-23. Then any elliptic curve congruent to E_{23} modulo 23 is isogenous to E_{23}”.

Connectivity and linear codes

Connectivity is a notion that emerges in graph theory and was later extended to matroid theory. Several notions of matroid connectivity exist, most notably Tutte connectivity and vertical connectivity. In this talk we will discuss some properties of the connectivity of a matroid associated to a linear code and how it relates to the original code.

Capacitated Network Bargaining Games: Stability and Structure

Capacitated network bargaining games are popular combinatorial games that involve the structure of matchings in graphs. We show that computing a minimum amount of vertex-capacity to reduce to make an instance stable is a polynomial-time solvable problem. We then exploit this to give approximation results for the NP-hard problem of stabilizing a graph via edge-removal operations.
Our work extends and generalizes previous results in the literature that dealt with a unit-capacity version of the problem, using several new arguments. In particular, while previous results mainly used combinatorial techniques, we here rely on polyhedral arguments.

Linking of strands in Special Diagonal Braids

Braids and their diagrams are widely studied in topology and algebra. In this talk, I introduce the class of special diagonal braids, whose closures can be viewed as generalisations of torus links. The definition of these braids is motivated by the requirement that they be realisable from rigidly identical strands in space, a condition necessary for modelling crystalline molecular braids. We associate special diagonal braids with graphs that represent the linking behaviour between the strands. We characterise unlinked as well as minimally linked special diagonal braids by the types of their braid words, and show that there exists exactly one special diagonal braid that is Borromean.
This talk is based on joint work with Dr. Senja Barthel.

Hypersurfaces passing through the Galois orbit of a point

Many geometric constructions have a notion of “general position,” allowing us to avoid degenerate cases: three colinear points, four points on a common circle, and so on. We investigate the extent to which the orbit of a point under a Galois group action behaves like a set of points in general position. More precisely, we prove that for any field $K$, any degree $r$ separable extension $L/K$, and any positive integers $n$ and $d$, there exists a point in $\mathbb{P}^n(L)$ for which the space of degree $d$
hypersurfaces passing through the Galois orbit of $P$ has the same dimension as for a set of $r$ points in general position. We will focus on the hardest case $K=\mathbb{F}_2$, which requires a careful study of the singular locus of complete intersection varieties. This is joint work with Shamil Asgarli and Chi Hoi Yip.

Ramsey numbers and extremal structures in polar spaces

We give a construction of triangle-free graphs using a binary projective cap, which has low complementary rank over the reals. This improves the bounds in the recently introduced rank-Ramsey problem and it gives better constructions of large partial m-ovoids for m > 2 in the binary symplectic space.

Hoffman colorings of graphs

Hoffman’s bound is a well-known spectral bound on the chromatic number of a graph, known to be tight for instance for bipartite graphs. While Hoffman colorings (colorings attaining the bound) were studied before for regular graphs, for irregular graphs not much is known. In this talk we investigate tightness of the Hoffman bound, with a particular focus on irregular graphs, obtaining several results on the graph structure of Hoffman colorings. Since several graph coloring parameters are known to be sandwiched between the Hoffman bound and the chromatic number, as a byproduct of our results on Hoffman colorability, we obtain the values of such chromatic parameters.