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.     

An asymptotic expansion for the expected number of real zeros of real random polynomials spanned by OPUC

Let ${\{{\phi }_i\}}_{i=0}^{\infty }$ be a sequence of orthonormal polynomials on the unit circle with respect to a positive Borel measure μ that is symmetric with respect to conjugation. We study asymptotic behavior of the expected number of real zeros, say ${\mathbb{E}}_n(\mu )$, of random polynomials

$P_n(z):=\sum _{i=0}^n{\eta }_i{\phi }_i(z),$

where ${\eta }_0,\dots ,{\eta }_n$ are i.i.d. standard Gaussian random variables. When μ is the acrlength measure such polynomials are called Kac polynomials and it was shown by Wilkins that ${\mathbb{E}}_n(|\mathrm{d}\xi |)$ admits an asymptotic expansion of the form

${\mathbb{E}}_n(|\mathrm{d}\xi |)～\frac{2}{\pi }\log ?(n+1)+\sum _{p=0}^{\infty }{A}_p{(n+1)}^{?p}$

(Kac himself obtained the leading term of this expansion). In this work we generalize the result of Wilkins to the case where μ is absolutely continuous with respect to arclength measure and its Radon–Nikodym derivative extends to a holomorphic non-vanishing function in some neighborhood of the unit circle. In this case ${\mathbb{E}}_n(\mu )$ admits an analogous expansion with the coefficients $A_p$ depending on the measure μ for $p\ge 1$ (the leading order term and $A_0$ remain the same).     

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.     

On color isomorphic subdivisions

Given a graph H and an integer $k?2$, let $f_k(n,H)$ be the smallest number of colors C such that there exists a proper edge-coloring of the complete graph $K_n$ with C colors containing no k vertex-disjoint color isomorphic copies of H. In this paper, we prove that $f_2(n,H_t)=\mathrm{\Omega }(n^{1+\frac{1}{2t?3}})$ where $H_t$ is the 1-subdivision of the complete graph $K_t$. This answers a question of Conlon and Tyomkyn (2021) [4].     

On the concentration phenomenon of L2-subcritical constrained minimizers for a class of Kirchhoff equations with potentials

In this paper, we study the existence and concentration behavior of minimizers for $i_V(c)=\underset{u\in S_c}{\inf }?I_V(u)$, here $S_c=\{u\in H^1({\mathbb{R}}^N)|{\int }_{{\mathbb{R}}^N}V(x)|u{|}^2<+\infty ,|u{|}_2=c>0\}$ and

$I_V(u)=\frac{1}{2}\underset{{\mathbb{R}}^N}{\int }(a|\mathrm{?}u{|}^2+V(x)|u{|}^2)+\frac{b}{4}{(\underset{{\mathbb{R}}^N}{\int }|\mathrm{?}u{|}^2)}^2?\frac{1}{p}\underset{{\mathbb{R}}^N}{\int }|u{|}^p,$

where $N=1,2,3$ and $a,b>0$ are constants. By the Gagliardo–Nirenberg inequality, we get the sharp existence of global constraint minimizers of $i_V(c)$ for $2<p<2^{?}$ when $V(x)\ge 0$, $V(x)\in {L^{\infty }}_{loc}({\mathbb{R}}^N)$ and $\underset{|x|\to +\infty }{\lim }?V(x)=+\infty$. For the case $p\in (2,\frac{2N+8}{N})\backslash \{4\}$, we prove that the global constraint minimizers $u_c$ of $i_V(c)$ behave like

$u_c(x)\approx \frac{c}{|Q_p{|}_2}{\left(\frac{m_c}{c}\right)}^{\frac{N}{2}}{Q}_p(\frac{m_c}{c}x?z_c),$

for some $z_c\in {\mathbb{R}}^N$ when c is large, where $Q_p$ is, up to translations, the unique positive solution of $?\frac{N(p?2)}{4}\mathrm{\Delta }{Q}_p+\frac{2N?p(N?2)}{4}{Q}_p=|Q_p{|}^{p?2}{Q}_p$ in ${\mathbb{R}}^N$ and $m_c={(\frac{\sqrt{a^2{D}_1^2?4b{D}_2{i}_0(c)}+a{D}_1}{2b{D}_2})}^{\frac{1}{2}}$, $D_1=\frac{Np?2N?4}{2N(p?2)}$ and $D_2=\frac{2N+8?Np}{4N(p?2)}$.     

Hamiltonian cycles in 7-tough (P3 ∪ 2P1)-free graphs

The toughness of a noncomplete graph G is the maximum real number t such that the ratio of $|S|$ to the number of components of $G?S$ is at least t for every cutset S of G. Determining the toughness for a given graph is NP-hard. Chvátal's toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3\cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3\cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chvátal's toughness conjecture for $(P_3\cup 2P_1)$-free graphs by showing that every 7-tough $(P_3\cup 2P_1)$-free graph on at least three vertices is hamiltonian.     

Existence and multiplicity of positive radial solutions for singular superlinear elliptic systems in the exterior of a ball

We prove the existence and multiplicity of positive radial solutions to the nonlinear system

$\{\begin{array}{c}\hfill ?\mathrm{\Delta }{u}_i=\lambda K_i(|x|)f_i(u_j)\text{ in }\mathrm{\Omega },\hfill \\ \hfill d_i\frac{?u_i}{?n}+{\stackrel{?}{c}}_i(u_i)u_i=0\text{ on }|x|=r_0,\hfill \\ \hfill u_i(x)\to 0\text{ as }|x|\to \infty ,\hfill \end{array}$

for a certain range of $\lambda >0$, where $i,j\in \{1,2\},i\ne j$, $\mathrm{\Omega }=\{x\in {\mathbb{R}}^N:|x|>r_0>0\}$, $N>2,d_i\ge 0$, $K_i:[r_0,\infty )\to (0,\infty )$, $\stackrel{?}{c}:[0,\infty )\to [0,\infty ),f_i:(0,\infty )\to \mathbb{R}$ are continuous with possible singularity ±∞ at 0 and satisfy a combined superlinear condition at ∞.     

Stability of attractors for the Kirchhoff wave equation with strong damping and critical nonlinearities

The paper investigates longtime dynamics of the Kirchhoff wave equation with strong damping and critical nonlinearities: $u_{tt}?(1+?{\Vert \mathrm{?}u\Vert }^2)\mathrm{\Delta }u?\mathrm{\Delta }{u}_t+h(u_t)+g(u)=f(x)$, with $?\in [0,1]$. The well-posedness and the existence of global and exponential attractors are established, and the stability of the attractors on the perturbation parameter ? is proved for the IBVP of the equation provided that both nonlinearities $h(s)$ and $g(s)$ are of critical growth.