Tsai-Lien Wong

A proper total weighting of a graph $G$ is a mapping $\phi$ which assigns to each vertex and each edge of $G$ a real number as its weight so that for any edge $uv$ of $G$, $\sum_{e \in E(v)}\phi(e)+\phi(v) \ne \sum_{e \in E(u)}\phi(e)+\phi(u)$. A $(k,k')$-list assignment of $G$ is a mapping $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ permissible weights and to each edge $e$ a set $L(e)$ of $k'$ permissible weights. An $L$-total weighting is a total weighting $\phi$ with $\phi(z) \in L(z)$ for each $z \in V(G) \cup E(G)$. A graph $G$ is called $(k,k')$-choosable if for every $(k,k')$-list assignment $L$ of $G$, there exists a proper $L$-total weighting. As a strenghtening of the well-known 1-2-3 conjecture, it was conjectured in [ Wong and Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] that every graph without isolated edge is $(1,3)$-choosable. It is easy to verified this conjecture for trees, however, to prove it for wheels seemed to be quite non-trivial. In this paper, we develop some tools and techniques which enable us to prove this conjecture for generalized Halin graphs.

This paper studies the generalizations of the Stirling numbers of both kinds and the Lah numbers in association with the normal order problem in the Weyl algebra $W=\langle x,D|Dx-xD=1\rangle$. Any word $\omega\in W$ with $m$ $x$'s and $n$ $D$'s can be expressed in the normally ordered form $\omega=x^{m-n}\sum_{k\ge 0} {{\omega}\brace {k}} x^{k}D^{k}$, where ${{\omega}\brace {k}}$ is known as the Stirling number of the second kind for the word $\omega$. This study considers the expansions of restricted words $\omega$ in $W$ over the sequences $\{(xD)^{k}\}_{k\ge 0}$ and $\{xD^{k}x^{k-1}\}_{k\ge 0}$. Interestingly, the coefficients in individual expansions turn out to be generalizations of the Stirling numbers of the first kind and the Lah numbers. The coefficients will be determined through enumerations of some combinatorial structures linked to the words $\omega$, involving decreasing forest decompositions of quasi-threshold graphs and non-attacking rook placements on Ferrers boards. Extended to $q$-analogues, weighted refinements of the combinatorial interpretations are also investigated for words in the $q$-deformed Weyl algebra.

A total weighting of a graph $G$ is a mapping $f$ which assigns to each element $z \in V(G) \cup E(G)$ a real number $f(z)$ as its weight. The vertex sum of $v$ with respect to $f$ is $\phi_f(v)=\sum_{e \in E(v)}f(e)+f(v)$. A total weighting is proper if $\phi_f(u) \ne \phi_f(v)$ for any edge $uv$ of $G$. A $(k,k')$-list assignment is a mapping $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ permissible weights, and assigns to each edge $e$ a set $L(e)$ of $k'$ permissible weights. We say $G$ is $(k,k')$-choosable if for any $(k,k')$-list assignment $L$, there is a proper total weighting $f$ of $G$ with $f(z) \in L(z)$ for each $z \in V(G) \cup E(G)$. It was conjectured in [T. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] that every graph is $(2,2)$-choosable and every graph with no isolated edge is $(1,3)$-choosable. A promising tool in the study of these conjectures is Combinatorial Nullstellensatz. This approach leads to conjectures on the permanent indices of matrices $A_G$ and $B_G$ associated to a graph $G$. In this paper, we establish a method that reduces the study of permanent of matrices associated to a graph $G$ to the study of permanent of matrices associated to induced subgraphs of $G$. Using this reduction method, we show that if $G$ is a subcubic graph, or a $2$-tree, or a Halin graph, or a grid, then $A_G$ has permanent index $1$. As a consequence, these graphs are $(2,2)$-choosable. \end{abstract} {\small \noindent{{\bf Key words: } Permanent index, matrix, total weighting}

A graph $G$ is $(k,k')$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and assigns to each edge $e$ a set $L(e)$ of $k'$ real numbers, there is a total weighting $\phi: V(G) \cup E(G) \to R$ such that $\phi(z) \in L(z)$ for $z \in V \cup E$, and $\sum_{e \in E(u)}\phi(e)+\phi(u) \ne \sum_{e \in E(v)}\phi(e)+\phi(v)$ for every edge $uv$. This paper proves the following results: (1) If $G$ is a connected $d$-degenerate graph, and $k>d$ is a prime number, and $G$ is either non-bipartite or has two non-adjacent vertices $u,v$ with $d(u)+d(v) < k$, then $G$ is $(1,k)$-choosable. As a consequence, every planar graph with no isolated edges is $(1,7)$-choosable, and every connected $2$-degenerate non-bipartite graph other than $K_2$ is $(1,3)$-choosable. (2) If $d+1$ is a prime number, $v_1, v_2, \ldots, v_n$ is an ordering of the vertices of $G$ such that each vertex $v_i$ has back degree $d^-(v_i) \le d$, then there is a graph $G'$ obtained from $G$ by adding at most $d-d^-(v_i)$ leaf neighbours to $v_i$ (for each $i$) and $G'$ is $(1,2)$-choosable. (3) If $G$ is $d$-degenerate and $d+1$ a prime, then $G$ is $(d,2)$-choosable. In particular, $2$-degenerate graphs are $(2,2)$-choosable. (4) Every graph is $(\lceil\frac{{\rm mad}(G)}{2}\rceil+1, 2)$ -choosable. In particular, planar graphs are $(4,2)$-choosable, planar bipartite graphs are $(3,2)$-choosable.

We define a new statistic $\mathsf{sor}$ on the set of colored permutations $\mathsf{G}_{r,n}$ and prove that it has the same distribution as the length function. For the set of restricted colored permutations corresponding to the arrangements of $n$ non-attacking rooks on a fixed Ferrers shape we show that the following two sequences of set-valued statistics are joint equidistributed: $(\ell,\mathsf{Rmil}^0,\mathsf{Rmil}^1,...,\mathsf{Rmil}^{r-1}$, $\mathsf{Lmil}^0,\mathsf{Lmil}^1,...,\mathsf{Lmil}^{r-1}$, $\mathsf{Lmal}^0,\mathsf{Lmal}^1,...,\mathsf{Lmal}^{r-1}$, $\mathsf{Lmap}^0,\mathsf{Lmap}^1,...,\mathsf{Lmap}^{r-1})$ and $(\mathsf{sor},\mathsf{Cyc}^0,\mathsf{Cyc}^{r-1},...,\mathsf{Cyc}^{1}$, $\mathsf{Lmic}^0,\mathsf{Lmic}^{r-1},...,\mathsf{Lmic}^{1}$, $\mathsf{Lmal}^0,\mathsf{Lmal}^1,...,\mathsf{Lmal}^{r-1}$, $\mathsf{Lmap}^0,\mathsf{Lmap}^1,...,\mathsf{Lmap}^{r-1})$. Analogous results are also obtained for Coxeter group of type $D$. Our results extend recent results of Petersen, Chen-Gong-Guo and Poznanovi\'{c}.