KPPY 85

The Hom-Graph $\operatorname{Hom}(G,H)$ is a digraph defined for two digraphs $G$ and $H$. Its vertices are the homomorphisms from $G$ to $H$, and $(\phi,\psi)$ is an arc if $\phi(u) \to \psi(v)$ for every arc $u \to v$ in $G$. In the problem $H$-recolouring, you are given two homomorpisms $\phi$ and $\psi$ from $G$ to $H$, and are asked to decide if there is a path between them in $\operatorname{Hom}(G,H)$.

The complexity of the $H$-recoloring problem has been considered in recent years by various authors. We consider the problem for reflexive digraphs $H$. In particular, we show that the problem of $H$-recolouring is polynomial time sovable, for reflexive instances $G$ when $H$ is a reflexive digraph cycle. We also consider the problem where instances need not be reflexive, and find that in this case, the problem can become PSPACE complete.

This is joint work with Rick Brewster and Mark Siggers.

In this talk, I will introduce friendly to basic link invariants in knot theory. Also, with some link invariants, I will mention about the recent ongoing project on periodic knots. The audience does not have to know any preparatory knowledges on knot theory.

This is joint work with Joonoh Kim.

For a given graph $G$, a subset $I$ of $V(G)$ is independent if no two vertices in $I$ are adjacent. Some time ago, Erdős and Moser asked what is the maximum possible number of maximal independent sets in a graph $G$ with $n$ vertices, and Moon and Moser showed that the maximum is achieved iff $G$ is a disjoint union of triangles. In this talk, we will discuss a `stability' version of the Moon-Moser result: if the number of maximal independent sets in $G$ is close to the maximum, then $G$ must contain a large number of disjoint triangles.

This is joint work with Jeff Kahn.

In the mixing problem for a graph $H$ one must decide if one can get between any two $H$-colourings of $G$ via small changes; that is, via a path in the Hom-graph $\operatorname{Hom}(G,H)$. We consider the problem for reflexive graphs, showing in particular that the problem in $NP$-complete for any triangle-free reflexive graph.

This is joint work with Jon Noel and Jae-Baek Lee.

The Grassmann graph $J_q(n,d)$ has as vertices all $d$-dimensional subspaces of the $n$-dimensional space over $\mathbb{F}_q$, with two vertices being adjacent if their intersection has dimension $d-1$. This graph is distance-regular and has diameter ${\rm min}\{d,n-d\}$. In 1995, Metsch showed that the Grassmann graph $J_q(n,d)$ of diameter at least $3$ can be characterized by its intersection numbers if $n\ne 2d$, or $n\ne 2d\pm 1$, or $n\ne 2d\pm 2$ if $q\in \{2,3\}$, or $n\ne 2d\pm 3$ if $q=2$. We will discuss a characterization of the Grassmann graphs with these exceptional parameters.

This talk is based on joint work with Jack Koolen.