• home

Abstract: Zero forcing is a type of graph propagation based on the color-change rule: Given graph $G$, if each vertex of $G$ is colored either white or blue, and vertex $v$ is a blue vertex with only one white neighbor $w$, then change the color of $w$ to blue. In this talk we prove a conjecture formulated by the automated conjecturing program called \emph{TxGraffiti}. The conjecture states that in a claw-free graph, the vertex cover number of the graph is at least the zero forcing number of the graph. We also prove a relationships about the zero forcing and independence number of a connected subcubic graph.

Abstract: Eternal domination is a graph game where mobile guards are placed on vertices and then moved in order to defend against sequences of attacks. If only one guard is allowed to move in response to an attack, then it has been shown that there is no benefit to allowing multiple guards to occupy a vertex. It was conjectured that if all guards can move there would similarly be no benefit from multiple guards occupying a vertex. Finbow et al. showed this was untrue, and provided a construction demonstrating that there are graphs which need fewer guards when 2 guards are allowed on the same vertex. We extend these results to show that for any $k$ and $s$ there are $k$-connected graphs which need fewer guards when up to $s$ guards are allowed on any vertex.

This is joint work with Georgia Penner.

Zoom link.

Abstract: For every $k\ge 2$ and $\Delta$, we prove that there exists a constant $C_{\Delta,k}$ such that the following holds. For every graph $H$ with $\chi(H)=k$ and every tree with at least $C_{\Delta,k}|H|$ vertices and maximum degree at most $\Delta$, the Ramsey number $R(T,H)$ is $(k-1)(|T|-1)+\sigma(H)$, where $\sigma(H)$ is the size of a smallest colour class across all proper $k$-colourings of $H$. This is tight up to the value of $C_{\Delta,k}$, and confirms a conjecture of Balla, Pokrovskiy, and Sudakov.

Abstract: A broad class of problems in extremal geometry can be characterized as follows. Fix a positive integer k and a property of k-tuples of points in R^2. The problem is then to determine how many k-tuples in an n-point set in R^2 can have the chosen property. One of the most famous instances of this form of problem is the unit distance problem, asked by Erdős in 1946. Here, the special property is pairs of points being precisely distance one apart. Another pair of well-studied open problems is to determine the maximum number of triples that determine a triangle of unit area or unit perimeter. In this presentation we will discuss recent progress on these triangle problems, particularly our new bounds on the number of unit perimeter triangles from earlier this year.

This talk is based on a joint work with Ritesh Goenka and Ethan White.

A Latin square is an n by n grid filled with n symbols so that each symbol appears exactly once in every row and column. A transversal in a Latin square is a selection of entries with no row, column, or symbol repetition. The study of transversals in Latin squares is as old as combinatorics, going back to Euler's work in the 18th century. A lot of exciting progress has been made in this area in the past few years. In 2020, Kwan proved that, with high probability, a random Latin square contains a full transversal (hitting each row and column). In the other extreme, in 2022, Müyesser and Pokrovskiy characterised the "algebraic" Latin squares which contain full transversals. Very recently, Montgomery proved that all Latin squares contain a transversal hitting all but one row. A key technique that is used in each of these results is the "distributive absorption method", introduced in 2014 by Montgomery to find spanning trees in random graphs. In this talk, we will give a gentle introduction to this technique.

Abstract: Structural Ramsey theory generalizes classical Ramsey theory by considering classes of finite sets with additional structure (such as finite groups or finite partial orders) and colourings of their substructures. When the class satisfies an appropriate amalgamation condition it is possible to assemble all of the structures in the class into a countably infinite structure, which is known as the Fraisse limit of the class. The goal of this talk is to describe a deep connection (due to Kechris, Pestov, and Todorcevic) between the structural Ramsey theory of a class of finite structures and the actions of the automorphism group of the class' Fraisse limit. This connection will be illustrated with a Ramsey theorem for finite-dimensional algebras of matrices.

Abstract: The line graph of a graph $G$ is the graph $L$ with vertex set $E(G)$ in which two vertices are adjacent if and only if the corresponding edges of $G$ share an endpoint. A famous theorem of Beineke characterizes the class of line graphs by a list of 9 forbidden induced subgraphs. In this talk we will be interested in the following question: Given an "explicit description" of a line graph $L$, when does the underlying graph $G$ also have an "explicit description"? To use the precise terminology (which I will define in the talk), when is a Borel graph $L$ a line graph of a Borel graph $G$? It turns out that to answer this question, we need to expand Beineke's list to include a tenth forbidden subgraph. This is joint work with James Anderson.

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.