### 60th KPPY Combinatorics Workshop -- Nov. 09 2013

Date: | Nov. 09 2013 | |

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

Location: | Kyungpook National University Natural Sciences Building Room 313 |

Schedule | ||

11:30 - 12:20 |
Alexander Stoimenow Keimyung University | On dual triangulations of surfaces |

12:30 | Lunch | |

2:00 -2:50 |
Hemanshu Kaul Illinois Institute of Technology | Finding Large Subgraphs |

3:00 -3:50 |
Semin Oh Pusan National University | The number of ideals of $\mathbb{Z}[x]/(x^3-4x)$ of a given index. |

4:00 - 4:50 |
O-joung Kwon KAIST | Tree-like structure of distance-hereditary graphs |

5:30 - 7:30 | Banquet |

## Abstracts

Alexander Stoimenow

On dual triangulations of surfaces

On dual triangulations of surfaces

The goal is to report on some long-term work on certain
combinatorial properties of knot/link diagrams of given
canonical genus. These turned out to have various ramifications
and applications, including (1) enumeration of alternating knots
by genus, (2) words in formal alphabets (Wicks forms), (3) graph
embedding problems on surfaces, (4) markings and the $sl_N$ graph
polynomial, (5) hyperbolic volume of polyhedra, graphs and links.
I will try to explain (at least as far as time allows) some
interrelations between these topics.

Hemanshu Kaul

Finding Large Subgraphs

Finding Large Subgraphs

The maximum subgraph problem for a fixed graph property $P$ asks: Given a graph $G$, find a subgraph $H$ of $G$ that satisfies property $P$ that has the maximum number of edges. Similarly, we can talk about maximum induced subgraph problem. The property $P$ can be planarity, acyclicity, bipartiteness, etc.
We will discuss some old and new problems of this flavor, focusing on the algorithmic aspects of these problems. In particular, we will describe some old results on the maximum bipartite subgraph problem and some new results on the maximum series-parallel subgraph problem.

Semin Oh

The number of ideals of $\mathbb{Z}[x]/(x^3-4x)$ of a given index.

The number of ideals of $\mathbb{Z}[x]/(x^3-4x)$ of a given index.

Let $L$ be the ring $\mathbb{Z}[x]/(x^3-4x)$. Let $G$ be the quadrangle graph and let $A_G$ be the adjacency matrix of $G$. Then $x^3-4x$ is the minimal polynomial of $A_G$. Thus $L$ is the ring related to $G$.
Let $\Lambda$ be the subring of $\mathbb{Q}[x]/(x^3-4x)$ satisfying $\Lambda$ is isomorphic to $L$. In this talk, our aim is to obtain the Dirichlet series of the number of $\Lambda$-submodules of $L$. We applied Louis Solomon's works to this calculation by using computer program GAP. We will introduce how to calculate the Dirichlet series.

O-joung Kwon

Tree-like structure of distance-hereditary graphs

Tree-like structure of distance-hereditary graphs

In this talk, we will discuss distance-hereditary graphs.
Distance-hereditary graphs are exactly the graphs
preserving the distance between two vertices when taking any connected induced subgraph.
There are many characterizations of distance-hereditary graphs, one being that they have tree-like structure with respect to a certain "split" operation. However, there are few known theorems using this structure.
We provide the following, using the tree-like structure of distance-hereditary graphs.

- A characterization of distance-hereditary graphs having linear rank-width at most k.
- Two variants of Bouchet's Tree Theorem to cographs and diamond-free chordal graphs.
- A test of local equivalent in distance-hereditary graphs.