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

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
Tree-like structure of distance-hereditary graphs
5:30 - 7:30 Banquet  


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.