Archive for the ‘2010’ Category

« Older Entries
Newer Entries »

Greg Markowsky, Distance-Regular Graphs and Potential Theory

Saturday, October 9th, 2010
Distance-Regular Graphs and Potential Theory
Greg Markowsky
Pohang Mathematics Institute, POSTECH, Pohang, Korea
2010/11/4 Thu 4PM-5PM (Room 3433)

The study of electric potentials on graphs has a close connection with probability theory. On distance-regular graphs the theory is particularly elegant, as known results concerning such graphs allow explicit calculations to be made. In this talk, I will introduce these topics and discuss some recent results that Jacobus Koolen and I have obtained, as well as some conjectures and open problems.

Tags:
Posted in 2010, KAIST Discrete Math Seminar | Comments Closed

Masahiko Yoshinaga (吉永正彦), On the Free Arrangements and Truncated Affine Weyl Arrangements

Saturday, October 9th, 2010
On the free arrangements and truncated affine Weyl arrangements
Masahiko Yoshinaga (吉永正彦)
Department of Mathematics, Kyoto University, Kyoto, Japan.
2010/10/26 Tue 4PM-5PM (Room 3433)

Freeness of a hyperplane arrangement is defined algebraically using module of derivations. I will discuss freeness of certain truncated affine Weyl arrangements, called the extended Catalan/Shi arrangements. I will also talk some enumerative corollaries.

Tags:
Posted in 2010, KAIST Discrete Math Seminar | Comments Closed

Sen-Peng Eu (游森棚), On Cyclic Sieving Phenomena

Saturday, October 9th, 2010
On Cyclic Sieving Phenomena
Sen-Peng Eu (游森棚)
Department of Applied Mathematics, National University of Kaohsiung, Taiwan.
2010/10/25 Mon 4PM-5PM (Room 3433)

The cyclic sieving phenomenon is introduced by Reiner, Stanton and White in 2004. Since then this new topic attracts more and more attentions of researchers in recent years. In this talk we will introduce the cyclic sieving phenomenon and introduce some interesting old and new results. Finally we present a new development on constructing new cyclic sieving phenomena from new ones via elementary representation theory.

Tags:
Posted in 2010, KAIST Discrete Math Seminar | Comments Closed

Shuichi Miyazaki (宮崎 修一), Approximation Algorithms for Finding Maximum Stable Matchings

Thursday, September 16th, 2010
Approximation algorithms for finding maximum stable matchings
Shuichi Miyazaki (宮崎 修一)
Academic Center for Computing and Media Studies, Kyoto University, Kyoto, Japan
2010/10/15 Fri 4PM-5PM

The stable marriage problem is a classical matching problem. An input consists of the set of men, the set of women, and each person’s preference list that orders the members of the opposite sex according to the preference. The problem asks to find a stable matching, that is, a matching that contains no (man, woman) pair, each of which prefers the other to his/her current partner in the matching.

One of the practical extensions is to allow participants to use ties in preference lists and to exclude unacceptable persons from lists. In this variant, finding a stable matching of maximum size is NP-hard. In this talk, we give some of the approximability results on this problem.

Tags:
Posted in 2010, KAIST Discrete Math Seminar | Comments Closed

Shakhar Smorodinsky, List coloring for geometric hypergraphs

Wednesday, September 1st, 2010
List coloring for geometric hypergraphs
Shakhar Smorodinsky
Department of Mathematics, Ben-Gurion University, Israel
2010/9/17 Fri 3PM-4PM

Given a hypergraph H = (V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex whose color is distinct from the colors of all other vertices in S. The study of this notion is motivated by frequency assignment problems in wireless networks. We introduce and study the list-coloring (or choice) version of this notion. Joint work with Panagiotis Cheilaris.

Tags:
Posted in 2010, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »