37th KPP Combinatorics Workshop - January 16 2010

Date: | January 16, 2010 |

Time: | 11am - 5:30pm ( dinner from 6pm ) |

Location: | School of Natural Sciences Room 218 |

Schedule | ||

11:00 | Jeong Ok Choi Trinity College, Connecticut, USA | A decomposition problem of regular hypergraphs |

12:00 | Lunch | |

1:30 | Hye Jin Yoon Kyungpook National University, Daegu | On the Bollobas-Riordan polynomial of covering ribbon graphs |

2:30 | Seog Jin Kim Konkuk University, Seoul | Identifying Codes in q-ary Hypercubes |

3:30 | Jack Koolen Postech University, Pohang | Hoffman graphs with smallest eigenvalue -3 |

4:30 | Suyoung Choi Osaka City University, Osaka, Japan | Cohomological rigidity of reducible simplicial polytopes |

6:00 | Dinner |

Funded by the KNU Institute of Basic Science

## Abstracts

Jeong Ok Choi

A decomposition problem of regular hypergraphs

A decomposition problem of regular hypergraphs

An *-block* is a -matrix in which every row has sum .
Let
be the set of pairs such that the columns of any -block with
rows split into a -block and an -block. We determine for .
In particular,

, |

, and |

and each value in divides or . |

Hye Jin Yoon

On the Bollobas-Riordan polynomial of covering ribbon graphs

On the Bollobas-Riordan polynomial of covering ribbon graphs

It is well-known that the Jones polynomial of a knot
is related to the Tutte polynomial of a spacial graph obtained from
a regular projection of the knot. The Bollobas-Riordan polynomial
is the generalized version of the Tutte polynomial which is related
to the Kauffman bracket polynomial of the corresponding ribbon
graph. In this paper, we review the construction of the covering
ribbon graphs from a voltage assignment and study the Bollobas-Riordan
polynomial of the covering ribbon graphs in terms of the
Bollobas-Riordan polynomial of the base ribbon graph and the
voltage assignment. And we calculate some Bollobas-Riordan polynomials of the covering ribbon graph about simple ribbon graphs.

Seog Jin Kim

Identifying Codes in q-ary Hypercubes

Identifying Codes in q-ary Hypercubes

Let be any integer . In this paper, we consider the
-ary -dimensional cube whose vertex set is
and
two vertices
and
are
adjacent if their Lee distance is . As a natural extension of
identifying codes in binary Hamming spaces, we further study
identifying codes in the above -ary hypercube. We let
denote the smallest cardinality of -identifying
codes of length in
. Little is known about
ternary or quaternary identifying codes. It is known that
where is the
number of vertices of
and is the degree of any
vertex of
. In a similar manner, we show that
, where is the
degree and is the number of vertices of
for
and , respectively. This is joint work with Jon-Lark
Kim.

Jack Koolen

Hoffman graphs with smallest eigenvalue -3

Hoffman graphs with smallest eigenvalue -3

A line graph has smallest eigenvalue -2. In 1976 Cameron et
al showed that except for a few exception all graphs with smallest
eigenvalue -2 are generalized line graphs, that is, a line graph with
Cocktail party graphs attached in a certain way.
In 1977 Hoiffman showed that the next limit point equals -1 - 2

^{1/2}(coming from the cartesian product of a complete graph with a path of length 2.) In recent years the work of Hoffman has been extended by Woo and Neumaier(1995) and Taniguchi(2009), using the concept of Hoffman graphs. in this talk i will discuss the Hoffman graphs with smallest eigenvalue -3. Suyoung Choi

Cohomological rigidity of reducible simplicial polytopes

Cohomological rigidity of reducible simplicial polytopes

A simplicial (or simple) polytope is said to be cohomologically
rigid if whenever there exists another polytope with an
isomorphism of their Tor-algebra there is a combinatorial equivalence
. In this talk, we find a necessary condition to be
combinatorially rigid for -dimensional reducible simplicial
polytopes. This question is quite related to so-called toric topology.
We also discuss about the relation between theory of polytopes and
toric topology.