### 66th KPPY Combinatorics Workshop -- September 20, 2014

Date: | September 20, 2014 | |

Time: | 11:00am-5:30pm | |

Location: | Science Building 1, Room 319
Department of Mathematics, Yeungnam University |

Schedule | ||

11:00 - 11:50 |
Yu Hyunju
POSTECH | Isomorphism classes of association schemes induced by Hadamard matrices |

12:00 | Lunch | |

1:30 -2:20 |
Kwon O-Joung
KAIST | Fixed parameter tractability of the thread vertex deletion problem. |

2:30 -3:20 |
Matthew DeVos
Simon Fraser University, Canada | Flows in Bidirected Graphs |

3:40 - 4:30 |
Kim Hee Jung
Seoul National University | Exotic embeddings of surfaces in a four manifold |

4:40 - 5:30 |
Lee Ho Soo
Yeungnam University | Moving averages on convex metric spaces |

6:00 - 8:00 | Banquet |

## Abstracts

Yu Hyunju

Isomorphism classes of association schemes induced by Hadamard matrices

Isomorphism classes of association schemes induced by Hadamard matrices

Every Hadamard matrix $H$ of order $n > 1$ induces a graph with $4n$ vertices, called the Hadamard graph $\Gamma(H)$ of $H$.
Since $\Gamma(H)$ is a distance-regular graph with diameter $4$, it induces a $4$-class association scheme $(\Omega, S)$ of order $4n$.
In this article we deal with fission schemes of $(\Omega, S)$ under certain conditions, and for such a fission scheme we estimate the
number of isomorphism classes with the same intersection numbers as the fission scheme.

Kwon O-Joung

Fixed parameter tractability of the thread vertex deletion problem.

Fixed parameter tractability of the thread vertex deletion problem.

The feedback vertex set problem is one of the well-studied problem, which is to find a vertex subset of size at most k in a given graph so that its removal makes the graph into a forest. Since the forests are exactly the graphs of tree-width at most 1, we can reformulate this problem using tree-width. Then we can naturally think about the variants of this problem by taking different width parameters, or different values. The problem of deleting at most k vertices to obtain a graph of rank-width at most 1 is known to be fixed parameter tractable when the parameter is the solution size k, but it is open whether this problem has a polynomial kernel or not. In this talk, we mainly consider linear rank-width, which is a linearized variant of rank-width. Thread graphs are exactly the graphs of linear rank-width at most 1, that is, the graphs whose vertices can be linearly ordered so that each vertex partition induces a binary matrix of rank 1 over GF(2). We first establish that the problem of deleting at most k vertices to obtain a thread graph (Thread Vertex Deletion) is fixed parameter tractable when the parameter is the solution size k. To show this, we define necklace graphs which are close to thread graphs. Using the class of necklace graphs, we also show that the Thread Vertex Deletion problem has a polynomial kernel. This is joint work with Eunjung Kim, Mamadou Kante, Christophe Paul.

Matthew DeVos

Flows in Bidirected Graphs

Flows in Bidirected Graphs

Tutte showed that for planar dual graphs G and G*, a k-coloring of G is equivalent to the existence of
a nowhere-zero k-flow in G*. This lead him to his famous conjecture that every bridgeless graph has a nowhere-zero
5-flow. Although this conjecture remains open, Seymour has proved that every such graph has a nowhere-zero 6-flow.
Bouchet studied this flow-coloring duality on more general surfaces, and this prompted him to introduce the notion
of nowhere-zero flows in bidirected graphs. He conjectured that every bidirected graph without a certain obvious
obstruction has a nowhere-zero 6-flow. Improving on a sequence of earlier theorems, we show that every such graph
has a nowhere-zero 12-flow.

Kim Hee Jung

Exotic embeddings of surfaces in a four manifold

Exotic embeddings of surfaces in a four manifold

The most striking result in 4-dimensional topology is the discovery of infinitely many exotic smooth structures on a smooth 4-manifold, while other dimensional manifolds allow only finitely many exotic smooth structures. The same phenomenon happens to embeddings with co-dimension 2 i.e. surfaces in a 4-manifold, and thus the classification problem of surfaces is more interesting. In this talk, I will discuss the results, giving infinitely many smooth embeddings of surface in a 4-manifold, that are topologically equivalent, but not smoothly.

Lee Ho Soo

Moving averages on convex metric spaces

Moving averages on convex metric spaces

We show that the moving average induced by a contractive mean on a complete metric space converges.
This general scheme of convergence covers the moving arithmetic average studied recently by Bauschke,
Sarada and Wang (also by D. Borwein, J. M. Borwein and Sims). Significant portions of the derivation can
be carried out in general convex metric spaces, which means that the results have broader applications beyond the setting of Banach spaces.