Packed words and quotient rings

The coinvariant algebra is a quotient of the polynomial ring $\mathbb{Q}[x_1,\dots ,x_n]$ whose algebraic properties are governed by the combinatorics of permutations of length n. A word $w=w_1\dots w_n$ over the positive integers is packed if whenever $i>2$ appears as a letter of w, so does $i?1$. We introduce a quotient $S_n$ of $\mathbb{Q}[x_1,\dots ,x_n]$ which is governed by the combinatorics of packed words. We relate our quotient $S_n$ to the generalized coinvariant rings of Haglund, Rhoades, and Shimozono as well as the superspace coinvariant ring.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

On the chromatic number of some P5-free graphs

Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, $V(H)$ can be partitioned into A and B such that $H[A]$ is perfect and $\omega (H[B])<\omega (H)$. We use $P_t$ and $C_t$ to denote a path and a cycle on t vertices, respectively. For two disjoint graphs $F_1$ and $F_2$, we use $F_1\cup F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and use $F_1+F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy|x\in V(F_1)\text{ and }y\in V(F_2)\}$. In this paper, we prove that (i) $(P_5,C_5,K_{2,3})$-free graphs are perfectly divisible, (ii) $\chi (G)\le 2{\omega }^2(G)?\omega (G)?3$ if G is $(P_5,K_{2,3})$-free with $\omega (G)\ge 2$, (iii) $\chi (G)\le \frac{3}{2}({\omega }^2(G)?\omega (G))$ if G is $(P_5,K_1+2K_2)$-free, and (iv) $\chi (G)\le 3\omega (G)+11$ if G is $(P_5,K_1+(K_1\cup K_3))$-free.     

The component counts of random functions

Consider functions $f:A\to A\cup C$, where A and C are disjoint finite sets. The weakly connected components of the digraph of such a function are cycles of rooted trees, as in random mappings, and isolated rooted trees. Let $n_1=|A|$ and $n_3=|C|$. When a function is chosen from all ${(n_1+n_3)}^{n_1}$ possibilities uniformly at random, then we find the following limiting behaviour as $n_1\to \infty$. If $n_3=o(n_1)$, then the size of the maximal mapping component goes to infinity almost surely; if $n_3～\gamma n_1$, $\gamma >0$ a constant, then process counting numbers of mapping components of different sizes converges; if $n_1=o(n_3)$, then the number of mapping components converges to 0 in probability. We get estimates on the size of the largest tree component which are of order $\log ?n_3$ when $n_3～\gamma n_1$ and constant when $n_3～n_1^{\alpha }$, $\alpha >1$. These results are similar to ones obtained previously for random injections, for which the weakly connected components are cycles and linear trees.     

Atomic decompositions for noncommutative martingales

We prove an atomic type decomposition for the noncommutative martingale Hardy space ${\mathsf{h}}_p$ for all $0<p<2$ by an explicit constructive method using algebraic atoms as building blocks. Using this elementary construction, we obtain a weak form of the atomic decomposition of ${\mathsf{h}}_p$ for all $0<p<1$, and provide a constructive proof of the atomic decomposition for $p=1$ which resolves a main problem on the subject left open for the last twelve years. We also study ${(p,\infty )}_c$-atoms, and show that every ${(p,2)}_c$-atom can be decomposed into a sum of ${(p,\infty )}_c$-atoms; consequently, for every $0<p\le 1$, the ${(p,q)}_c$-atoms lead to the same atomic space for all $2\le q\le \infty$. As applications, we obtain a characterization of the dual space of the noncommutative martingale Hardy space ${\mathsf{h}}_p$ ($0<p<1$) as a noncommutative Lipschitz space via the weak form of the atomic decomposition. Our constructive method can also be applied to prove some sharp martingale inequalities.