CIRCA Seminar 12th March 1pm
There will be a CIRCA lunchtime seminar on Thursday 12th March at 1pm in Maths Lecture Theatre C.
Duncan Adamson and Violeta Lopez Lopez will speak.
Duncan’s Title: Colouring Temporal Graphs
Duncan’s Abstract: Temporal graphs are a generalisation of (static) graphs, representing networks that change over time via the addition and removal of edges. These graphs are comprised of a sequence of “snapshots’’, static graphs defined over a common vertex set with a changing edge set. In this talk, we will talk about one generalisation of the well known colouring problem to temporal graphs, the “temporal recolouring problem”. In this problem, we are given a temporal graph $G$, chromatic number $\chi$, and budget $B$, and asked if we can make a sequence of colourings such that the number of changes between sequential snapshots is at most $B$. On the negative side, we show that this problem is NP-hard, even when every snapshot is bipartite. On the positive side, we show that this problem for bipartite colourings can be solved in $O(n T 2^k)$ time for an $n$ vertex graph with $T$ snapshots, and at most $k$ bipartite components per snapshot, and approximated within a factor of $O(\sqrt{\log nT})$ in $\tilde{O}(n^3 T^3)$ time.
This is a joint work with George B. Mertzios and Paul G. Spirakis, based on the paper “Maintaining Bipartite Colourings on Temporal Graphs on a Budget”, available here https://arxiv.org/abs/2511.20338
Violeta’s Title: Lines in a cubic surface: complex and real
Violeta’s Abstract: This talk will be about algebraic cubic surfaces, i.e., solution sets of degree three polynomials in four variables. A classical result in Algebraic Geometry, due to Cayley and Salmon, states that every complex cubic surface contains exactly 27 lines. After a brief introduction, we will check the analogous result for cubic surfaces defined over the real numbers. The contents of this talk are based on my undergrad thesis.
Details on the University Events as follows:- Centre for Interdisciplinary Research in Computational Algebra (CIRCA) seminar | Events