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

 Date: Nov. 09 2013 Time: 11:30am-5:30pm Location: Kyungpook National UniversityNatural 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
Program

## Abstracts

Alexander Stoimenow
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
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.
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
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.
This is joint work with Mamadou Kante and Isolde Idler.