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
Program

Abstracts

Yu Hyunju
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.
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
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
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
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.