• home

Abstract (plain text):
Given a graph H, say that a graph G is properly rainbow H-saturated if there exists a rainbow H-free proper edge-colouring of G and, for any non-edge e of G, every proper edge-colouring of G+e contains a rainbow copy of H. The proper rainbow saturation number is the minimum number of edges in a properly rainbow H-saturated graph on n vertices. This is a natural variant of the graph saturation problem based on the rainbow extremal number. In this talk, we will prove bounds on the proper rainbow saturation number for specific classes of graphs, and we will prove general bounds on the proper rainbow saturation number using related saturation numbers.

Joint work with Natasha Morrison.

For a simple graph $G$ on $n$ vertices, let $\mathcal{S}(G)$ be the set of all $n\times n$ real symmetric matrices $A=[a_{i,j}]$ with $a_{i,j}\neq 0$ if and only if $\{i,j\}$ is an edge of $G$. There are no restrictions on the diagonal entries of $A$. The inverse eigenvalue problem for a graph $G$ (IEP-G) seeks to determine all possible spectra of matrices in $\mathcal{S}(G)$.

One of the relaxations of the IEP-G is to determine the minimum number of distinct eigenvalues of a matrix in $\mathcal{S}(G)$ for a given graph $G$. This parameter is denoted by $q(G)$ and it is called the minimum number of distinct eigenvalues of $G$.

In this presentation, we will review some of the results and the techniques from recent developments about $q(G)$.

Abstract: In 1954, Tutte made a conjecture that every graph without a cut-edge has a nowhere-zero 5-flow. A parallel conjecture to this, but for signed graphs is Bouchet’s Conjecture (1983) that every signed graph without the obvious obstruction has a nowhere-zero 6-flow. We prove that Bouchet’s Conjecture holds in the special case of 3-edge-connected graphs when 6 is replaced with 8.

Abstract: In the eternal eviction game, a set of guards placed on the vertices of (a dominating set of) a graph G must move to defend the graph against attacks on those of its vertices that contain guards, while maintaining a dominating set of G. The eternal eviction number of G is the minimum number of guards required to defend G against any sequence of attacks. In this talk, we will present some recent progress on the game. In particular, we will show that for any integer $k \geq 1$, there exists $f(k)$ such that any graph with independence number at most $k$ has eviction number at most $f(k)$.

This is joint work with Gary MacGillivray and Kieka Mynhardt.

Abstract: A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, then G has a Hamilton cycle. We prove a similar result, implying that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.

Abstract: A famous result of Rado characterises those integer matrices $A$ which are partition regular, that is, for which any finite colouring of $[n]:=\{1,2,\dots,n\}$ (for $n$ sufficiently large) gives rise to a monochromatic solution to the equation $Ax=0$. The probability threshold for when the binomial random set $[n]_p$ has the property above was established via results of R\"odl and Ruci\'nski (for the 0-statement), and Friedgut, R\"odl and Schacht (for the 1-statement). Collectively these results form the Random Rado Theorem.

There has also been interest in Rado-type results in the setting of abelian groups. In this talk we prove an analogue of the Random Rado Theorem in the setting of sequences of (subsets of) abelian groups.

Joint work with Andrea Freschi and Andrew Treglown.

Abstract: The Manickam-Miklós-Singhi Conjecture states that for positive integers n and k with n > (4k - 1), a multi-set X = {x_1,x_2, … ,x_n} with real entries and nonnegative sum has at least \binom{n-1}{k-1} subsets of size k with nonnegative sum.

Abstract: In 2017, Ron Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture: if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most the ceiling of n/r.

I will begin with a summary of recent progress on Aharoni's conjecture based on a new survey article of Katie Clinch, Jackson Goerner, Freddie Illingworth, and myself. I will then sketch a proof that Aharoni's conjecture holds up to an additive constant for each fixed r. The last result is joint work with Patrick Hompe.