Archive for the ‘2010’ Category

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.

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.

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.

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.

(Colloquium) Shakhar Smorodinsky, Conflict-Free colorings

Wednesday, September 1st, 2010
Conflict-Free colorings
Shakhar Smorodinsky
Department of Mathematics, Ben-Gurion University, Israel
2010/9/16 Thu 4:30PM-5:30PM (Room 1501)

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. When all hyperedges in H have cardinality two (i.e., when H is a simple graph), this coloring coincides with the classical graph coloring. The study of this coloring is motivated by frequency assignment problems in wireless networks and several other applications. We will survey this notion and introduce some fascinating open problems.