# KPPY 85

Jae-baek Lee, Kyoung-Tark Kim, Jinyoung Park, Mark Siggers, Alexander Gavrilyuk

Dec 15, 2017. 11:00am-5:30pm at YNU

Schedule | ||

11:00am - 11:50 |
Jae-baek Lee KNU | Digraph Recolouring |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Kyoung-Tark Kim Sogang University | Knot invariants and periodic knots |

2:30 - 3:20 |
Jinyoung Park Rutgers University | Stability for Maximal Independent Sets |

3:30 - 4:20 |
Mark Siggers KNU | The Mixing Problem for Reflexive Graphs |

4:30 - 5:20 |
Alexander Gavrilyuk PNU | On a characterization of the Grassmann graphs |

## Abstracts

Jae-baek Lee

Digraph Recolouring

Digraph Recolouring

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.

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.

Kyoung-Tark Kim

Knot invariants and periodic knots

Knot invariants and periodic knots

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.

This is joint work with Joonoh Kim.

Jinyoung Park

Stability for Maximal Independent Sets

Stability for Maximal Independent Sets

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.

This is joint work with Jeff Kahn.

Mark Siggers

The Mixing Problem for Reflexive Graphs

The Mixing Problem for Reflexive Graphs

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.

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

Alexander Gavrilyuk

On a characterization of the Grassmann graphs

On a characterization of the Grassmann graphs

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.

This talk is based on joint work with Jack Koolen.