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.     

A tight bound for conflict-free coloring in terms of distance to cluster

Given an undirected graph $G=(V,E)$, a conflict-free coloring with respect to open neighborhoods (CFON coloring) is a vertex coloring such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for such a coloring is the CFON chromatic number of G, denoted by ${\chi }_{ON}(G)$.In previous work [WG 2020], we showed the upper bound ${\chi }_{ON}(G)\le \mathsf{dc}(G)+3$, where $\mathsf{dc}(G)$ denotes the distance to cluster parameter of G. In this paper, we obtain the improved upper bound of ${\chi }_{ON}(G)\le \mathsf{dc}(G)+1$. We also exhibit a family of graphs for which ${\chi }_{ON}(G)>\mathsf{dc}(G)$, thereby demonstrating that our upper bound is tight.     

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.     

A note on the Hambleton-Taylor-Williams conjecture

I. Hambleton, L. Taylor and B. Williams conjectured a general formula in the spirit of H. Lenstra for the decomposition of $G_n(RG)$ for any finite group G and noetherian ring R. The conjectured decomposition was shown to hold for some large classes of finite groups. D. Webb and D. Yao discovered that the conjecture failed for the symmetric group $S_5$, but remarked that it still might be reasonable to expect the HTW-decomposition for solvable groups. In this paper we show that the solvable group $\mathrm{SL}(2,{\mathbb{F}}_3)$ is also a counterexample to the conjectured HTW-decomposition. Nevertheless, we prove that for any finite group G the rank of $G_1(\mathbb{Z}G)$ does not exceed the rank of the expression in the HTW-decomposition. We also show that the HTW-decomposition predicts correct torsion for $G_1(\mathbb{Z}G)$ for any finite group G. Furthermore, we prove that for any degree other than $n=1$ the conjecture gives a correct prediction for the rank of $G_n(\mathbb{Z}G)$.     

Asymptotic stability of superposition of stationary solutions and rarefaction waves for 1D Navier–Stokes/Allen–Cahn system

In this paper, we investigate the large time behavior of the solutions to the inflow problem for the one-dimensional Navier–Stokes/Allen–Cahn system in the half space. First, we assume that the space-asymptotic states $({\rho }_{+},u_{+},{\chi }_{+})$ and the boundary data $({\rho }_b,u_b,{\chi }_b)$ satisfy some conditions so that the time-asymptotic state of solutions for the inflow problem is a nonlinear wave which is the superposition of a stationary solution and a rarefaction wave. Then, we show the existence of the stationary solution by the center manifold theorem. Finally, we prove that the nonlinear wave is asymptotically stable when the initial data is a small perturbation of the nonlinear wave. The proof is mainly based on the energy method by taking into account the effect of the concentration χ and the complexity of nonlinear wave.     

A note on Hamilton sequences of extremal Beltrami differentials

Let X be a hyperbolic Riemann surface and let μ be an extremal Beltrami differential on X with ${6\mu 6}_{\infty }\in (0,1)$. It is proved that, if $\{{?}_n\}$ is a Hamilton sequence of μ, then $\{{?}_n\}$ must be a Hamilton sequence of any extremal Beltrami differential ν contained in $[\mu ]$. This result proved a conjecture of the first author of this paper in 1996. This result is also a generalization of two known results.     

Twisted Steinberg algebras

We introduce twisted Steinberg algebras over a commutative unital ring R. These generalise Steinberg algebras and are a purely algebraic analogue of Renault's twisted groupoid C*-algebras. In particular, for each ample Hausdorff groupoid G and each locally constant 2-cocycle σ on G taking values in the units $R^{\times }$, we study the algebra $A_R(G,\sigma )$ consisting of locally constant compactly supported R-valued functions on G, with convolution and involution “twisted” by σ. We also introduce a “discretised” analogue of a twist Σ over a Hausdorff étale groupoid G, and we show that there is a one-to-one correspondence between locally constant 2-cocycles on G and discrete twists over G admitting a continuous global section. Given a discrete twist Σ arising from a locally constant 2-cocycle σ on an ample Hausdorff groupoid G, we construct an associated twisted Steinberg algebra $A_R(G;\mathrm{\Sigma })$, and we show that it coincides with $A_R(G,{\sigma }^{?1})$. Given any discrete field ${\mathbb{F}}_d$, we prove a graded uniqueness theorem for $A_{{\mathbb{F}}_d}(G,\sigma )$, and under the additional hypothesis that G is effective, we prove a Cuntz–Krieger uniqueness theorem and show that simplicity of $A_{{\mathbb{F}}_d}(G,\sigma )$ is equivalent to minimality of G.     

The secret life of μ-clubs

Let $\mu <\kappa <\lambda$ be three infinite cardinals, the first two being regular. We compare five versions for $P_{\kappa }(\lambda )$ of the ideal $N{S}_{\kappa }|E_{\mu }^{\kappa }$ (the restriction of the nonstationary ideal on κ to the set of all limit ordinals less than κ of cofinality μ): $N{S}_{\kappa ,\lambda }|E_{\mu }^{\kappa ,\lambda }$ (the restriction of the nonstationary ideal on $P_{\kappa }(\lambda )$ to the set of all a in $P_{\kappa }(\lambda )$ of uniform cofinality μ), $N{S}_{\mu ,\kappa ,\lambda }$ (the smallest $(\mu ,\kappa )$-normal ideal on $P_{\kappa }(\lambda )$), $J(\mu ,\kappa ,\lambda )$ (the smallest projection on $P_{\kappa }(\lambda )$ of a restriction of the nonstationary ideal on some $P_{\kappa }(\pi )$ to the set of all x in $P_{\kappa }(\pi )$ such that $x\cap \lambda$ can be reconstructed from a subset of x of size μ (and any of its subsets of size μ)), the ideal Nμ-$S_{\kappa ,\lambda }$ dual to the μ-club filter on $P_{\kappa }(\lambda )$ and the game ideal $N{G}_{\kappa ,\lambda }^{\mu }$. We show that if $\lambda <{\kappa }^{+\omega }$, then the first four ideals (and even all five ideals in case ${\rho }^{<\mu }<\kappa$ for any cardinal $\rho <\kappa$) coincide. Our main result asserts that if there are no large cardinals in an inner model, then Nμ-$S_{\kappa ,\lambda }=J(\mu ,\kappa ,\lambda )$. This throws some light on the so far rather mysterious μ-club filter.