Sharp Reilly-type inequalities for a class of elliptic operators on submanifolds

Let M be an $n(>2)$-dimensional closed orientable submanifold in an $(n+p)$-dimensional space form ${\mathbb{R}}^{n+p}(c)$. We obtain an optimal upper bound for the second eigenvalue of a class of elliptic operators on M defined by $L_{T}f=-\text{div}(T\mathrm{\nabla }f)$, where T is a general symmetric, positive definite and divergence-free $(1,1)$-tensor on M. The upper bound is given in terms of an integration involving tr T and $|H_T{|}^2$, where tr T is the trace of the tensor T and $H_T={\sum }_{i=1}^{n}A(T{e}_i,e_i)$ is a normal vector field associated with T and the second fundamental form A of M. Furthermore, we give the sufficient and necessary conditions when the upper bound is attained. Our main theorem can be viewed as an extension of the famous “Reilly inequality”. The operator $L_T$ can be regarded as a natural generalization of the well-known operator $L_r$ which is the linearized operator of the first variation of the $(r+1)$-th mean curvature for hypersurfaces in a space form. As applications of our main theorem, we generalize the results of Grosjean [17] and Li–Wang [20] in codimension one to arbitrary codimension.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

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.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.     

Context-free grammars,generating functions and combinatorial arrays

Let ${\left[R_{n,k}\right]}_{n,k\ge 0}$ be an array of nonnegative numbers satisfying the recurrence relation $R_{n,k}=(a_{1}n+a_{2}k+a_3)R_{n-1,k}+(b_{1}n+b_{2}k+b_3)R_{n-1,k-1}+(c_{1}n+c_{2}k+c_3)R_{n-1,k-2}$ with $R_{0,0}=1$ and $R_{n,k}=0$ unless $0\le k\le n$. In this paper, we first prove that the array ${\left[R_{n,k}\right]}_{n,k\ge 0}$ can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of ${\left[R_{n,k}\right]}_{n,k\ge 0}$. Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type $B$, and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong $q$-log-convexity of some generating functions.     

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].     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).