# KPP 43

Dan Drake, Byungchan Kim, David Cariolaro, Jung Wook Lim, Shinya Fujita

Dec 18 2010 at KNU

Schedule | ||

11:00am - 11:50 |
Dan Drake KAIST, Daejeon | Paths, polynomials, partitions, and paths |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Byungchan Kim Seoul National University, Seoul | Combinatorics of Partial Theta Functions |

2:30 - 3:20 |
David Cariolaro Xi’an Jiaotong-Liverpool University, China | Excessive Factorizations |

3:30 - 4:20 |
Jung Wook Lim Postech University, Pohang | Zero-divisor graphs over a commutative ring |

4:30 - 5:20 |
Shinya Fujita Gunma National College of Technology, Japan | Rainbow Ramsey Numbers and Related Topics |

## Abstracts

Dan Drake

Paths, polynomials, partitions, and paths

Paths, polynomials, partitions, and paths

We start with weighted Motzkin paths, then discuss how those paths are the basis of a combinatorial theory of orthogonal polynomials. Four sets of "classical" orthogonal polynomials naturally describe a hierarchy of noncrossing complete matchings, complete matchings, set partitions, and permutations. From matchings and set partitions, we move on to consider $k$-distant noncrossing matchings and set partitions, and end with a bijection from 2-distant noncrossing matchings to weighted Motzkin paths, thus returning us to where we started.

Byungchan Kim

Combinatorics of Partial Theta Functions

Combinatorics of Partial Theta Functions

A partial theta function is a sum of the form $\sum_{n=0}^{\infty} (-1)^{n}q^{n(n-1)/2}x^{n}$. Combinatorially, identities containing partial theta function are very interesting since they indicate what remains after numerous cancellations of certain kinds of partitions. In this talk, we will discuss the combinatorics of some identities involving partial theta functions in Ramanujan's lost notebook.

David Cariolaro

Excessive Factorizations

Excessive Factorizations

An excessive factorization of a graph $G$ is a minimum set of perfect matchings of $G$ whose union is $E(G)$. The excessive index of $G$ is the number of perfect matchings in an excessive factorization of $G$ (or $\infty,$ if the graph does not admit an excessive factorization). More generally, let $m$ be a positive integer. An excessive $[m]$-factorization of a graph $G$ is a minimum set of matchings, all of size exactly $m$, whose union is the edge set of $G$. The excessive $[m]$-index of $G$ is the number of matchings in an excessive $[m]$-factorization of $G$ (or $\infty,$ if the graph does not admit an excessive $[m]$-factorization).
In this talk we shall aim to give an introduction to the theory of excessive (and excessive $[m]$-)factorizations.

The content of this talk is joint work with Arrigo Bonisoli, Hung-Lin Fu, Giuseppe Mazzuoccolo and Romeo Rizzi.

The content of this talk is joint work with Arrigo Bonisoli, Hung-Lin Fu, Giuseppe Mazzuoccolo and Romeo Rizzi.

Jung Wook Lim

Zero-divisor graphs over a commutative ring

Zero-divisor graphs over a commutative ring

In 1988 , Beck first introduced the concept of zero-divisor graphs over a commutative ring with identity. Especially, he was interested in coloring problems. Later, in 1999, Anderson and Livingston defined a new concept of zero-divisor graphs over commutative rings. Following Anderson et al., the zero-divisor graph of a commutative ring $R$, denoted by $\Gamma(R)$, is the graph with vertices $Z(R)^*$, the set of nonzero zero-divisors of $R$, and for distinct $x, y \in Z(R)^*$, the vertices $x$ and $y$ are adjacent if and only if $xy=0$. In the first part of this talk, I will survey some properties of zero-divisor graphs. Next, I will prove some basic results about the zero-divisor graphs of the rings $A+XB[X]$ and $A+XB[\![X]\!]$, where $A \subseteq B$ is an extension of commutative rings with the same total quotient ring $T(A)$.

Shinya Fujita

Rainbow Ramsey Numbers and Related Topics

Rainbow Ramsey Numbers and Related Topics

Gallai-colorings of complete graphs - edge colorings such that no triangle is colored with three distinct colors - occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai-colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. In this talk, I will introduce some recent results on this topic, and I will also mention a related topic concerning rainbow ramsey numbers.