Seminar on Combinatorics

主講者: 羅元勳 博士 (國立師範大學數學系)
講題: 1. Conflict-avoiding codes and graph-packing problems 2. Joint Equidistributions on Classical Coxeter Groups
時間: 2013-12-13 (Fri.)  14:00 - 17:00
地點: 數學所 617 研討室 (台大院區)
Abstract: 1. Conflict-avoiding codes (CACs) have been studied for a multiple-access channel (collision channel) without feedback. In such communication system, all users (may be active or inactive) want to share a common communication channel. If two or more active users access the channel at the same time, some collision will occur. The size of a CAC equals to the number of potential users that can be supported in the system. A CAC with maximum size is called optimal. In this talk, the problem will be formulated as a graph-packing problem, and some optimal CACs will be presented. In addition, a shift version of CACs, called partially CACs, is considered. 2. The classical Coxeter groups consist of the symmetric group $\mathfrak{S}_n$, signed permutation group $B_n$ and even signed permutation group $D_n$. Petersen [3] discovered a new statistic, called $sorting index$, on these groups and proved that it is Mahonian, i.e., is equidistributed with the corresponding length function. He also proved that ($inv$, $lmin$) and ($sor$, $cyc$) are joint equildistributed over $\mathfrak{S}_n$. A generalization to $B_n$ and $D_n$ is obtained by Chen et al [1]. In this work we generalize these results further to three or four statistics. Our main results consist of a collection of equidistributed triple or quadruple statistics for each type. For example, over $\mathfrak{S}_n$ we define a new Stirling statistic $lmic_1$ and derive the following generating function: $\sum_{\mathfrak{S}_n} q^{inv}x^{rmin} y^{lmin}= \sum_{\mathfrak{S}_n} q^{sor}x^{cyc} y^{lmic_1}= xy\prod_{i=2}^{n} (x+[i]_q+yq^{i-1}-1-q^{i-1}).$ For $B_n$ and $D_n$, we have the following $5$-variable and $4$-variable generating functions respectively: $\sum_{B_n} q^{inv_B}x_1^{rmin^+} x_2^{rmin^-} y_1^{lmin^+} y_2^{lmin^-} =\sum_{B_n} q^{sor_B}x_1^{cyc^+} x_2^{cyc^-} y_1^{lmic_1^+} y_2^{lmic_1^-} =(x_1y_1+x_2y_2q)\prod_{i=2}^n \left(x_1+q+\cdots+q^{i-2}+y_1q^{i-1}+y_2q^i+q^{i+1}+\cdots+q^{2i-2}+x_2q^{2i-1}\right)$, and $\sum_{D_n} q^{inv_D}x_1^{rmin_D^+} x_2^{rmin_D^-} y^{lmin} =\sum_{D_n} q^{sor_D}x_1^{cyc_D^+} x_2^{cyc_D^-} y^{lmic_1} =(x_1y)\prod_{i=2}^{n} \left(x_1+q+\cdots+q^{i-2}+(2y)q^{i-1}+q^{i}+\cdots+q^{2i-3}+x_2q^{2i-2}\right).$
  || Close window ||