Domination and upper domination of direct product graphs

Let $X_{\mathbb{Z}∕n\mathbb{Z}}$ denote the unitary Cayley graph of $\mathbb{Z}∕n\mathbb{Z}$. We present results on the tightness of the known inequality $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)$, where $\gamma$ and${\gamma }_t$ denote the domination number and total domination number, respectively, and $g$ is the arithmetic function known as Jacobsthal’s function. In particular, we construct integers $n$ with arbitrarily many distinct prime factors such that $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)?1$. We give lower bounds for the domination numbers of direct products of complete graphs and present a conjecture for the exact values of the upper domination numbers of direct products of balanced, complete multipartite graphs.     

Counting numerical semigroups by genus and even gaps

Let $n_g$ be the number of numerical semigroups of genus $g$. We present an approach to compute $n_g$ by using even gaps, and the question: Is it true that $n_{g+1}>n_g$? is investigated. Let $N_{\gamma }\left(g\right)$ be the number of numerical semigroups of genus $g$ whose number of even gaps equals $\gamma$. We show that $N_{\gamma }\left(g\right)=N_{\gamma }\left(3\gamma \right)$ for $\gamma \le ?g∕3?$ and $N_{\gamma }\left(g\right)=0$ for $\gamma >?2g∕3?$; thus the question above is true provided that $N_{\gamma }(g+1)>N_{\gamma }\left(g\right)$ for $\gamma =?g∕3?+1,\dots ,?2g∕3?$. We also show that $N_{\gamma }\left(3\gamma \right)$ coincides with $f_{\gamma }$, the number introduced by Bras-Amorós (2012) in connection with semigroup-closed sets. Finally, the stronger possibility $f_{\gamma }～{\phi }^{2\gamma }$ arises being $\phi =(1+\sqrt{5})∕2$ the golden number.     

Turán number and decomposition number of intersecting odd cycles

Given a graph $H$, the Turán function $\mathrm{ex}(n,H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain $H$ as a subgraph. Let $s,t$ be integers and let $H_{s,t}$ be a graph consisting of $s$ triangles and $t$ cycles of odd lengths at least 5 which intersect in exactly one common vertex. Erd?s et al. (1995) determined the Turán function $\mathrm{ex}(n,H_{s,0})$ and the corresponding extremal graphs. Recently, Hou et al. (2016) determined $\mathrm{ex}(n,H_{0,t})$ and the extremal graphs, where the $t$ cycles have the same odd length $q$ with $q?5$. In this paper, we further determine $\mathrm{ex}(n,H_{s,t})$ and the extremal graphs, where $s?0$ and $t?1$. Let $?(n,H)$ be the smallest integer such that, for all graphs $G$ on $n$ vertices, the edge set $E\left(G\right)$ can be partitioned into at most $?(n,H)$ parts, of which every part either is a single edge or forms a graph isomorphic to $H$. Pikhurko and Sousa conjectured that $?(n,H)=\mathrm{ex}(n,H)$ for $\chi \left(H\right)?3$ and all sufficiently large $n$. Liu and Sousa (2015) verified the conjecture for $H_{s,0}$. In this paper, we further verify Pikhurko and Sousa’s conjecture for $H_{s,t}$ with $s?0$ and $t?1$.     

On parabolic Kazhdan–Lusztig R-polynomials for the symmetric group

Parabolic R-polynomials were introduced by Deodhar as parabolic analogues of ordinary R-polynomials defined by Kazhdan and Lusztig. In this paper, we are concerned with the computation of parabolic R-polynomials for the symmetric group. Let $S_n$ be the symmetric group on $\{1,2,\dots ,n\}$, and let $S=\{s_i|1\le i\le n?1\}$ be the generating set of $S_n$, where for $1\le i\le n?1$, $s_i$ is the adjacent transposition. For a subset $J?S$, let ${(S_n)}_J$ be the parabolic subgroup generated by J, and let ${(S_n)}^J$ be the set of minimal coset representatives for $S_n/{(S_n)}_J$. For $u\le v\in {(S_n)}^J$ in the Bruhat order and $x\in \{q,?1\}$, let $R_{u,v}^{J,x}(q)$ denote the parabolic R-polynomial indexed by u and v. Brenti found a formula for $R_{u,v}^{J,x}(q)$ when $J=S?\{s_i\}$, and obtained an expression for $R_{u,v}^{J,x}(q)$ when $J=S?\{s_{i?1},s_i\}$. In this paper, we provide a formula for $R_{u,v}^{J,x}(q)$, where $J=S?\{s_{i?2},s_{i?1},s_i\}$ and i appears after $i?1$ in v. It should be noted that the condition that i appears after $i?1$ in v is equivalent to that v is a permutation in ${(S_n)}^{S?\{s_{i?2},s_i\}}$. We also pose a conjecture for $R_{u,v}^{J,x}(q)$, where $J=S?\{s_k,s_{k+1},\dots ,s_i\}$ with $1\le k\le i\le n?1$ and v is a permutation in ${(S_n)}^{S?\{s_k,s_i\}}$.     

Global defensive alliances of trees and Cartesian product of paths and cycles

Given a graph $G$, a defensive alliance of $G$ is a set of vertices $S?V\left(G\right)$ satisfying the condition that for each $v\in S$, at least half of the vertices in the closed neighborhood of $v$ are in $S$. A defensive alliance $S$ is called global if every vertex in $V\left(G\right)?S$ is adjacent to at least one member of the defensive alliance $S$. The global defensive alliance number of $G$, denoted ${\gamma }_a\left(G\right)$, is the minimum size around all the global defensive alliances of $G$. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete $k$-ary trees for $k=2,3,4$. We also establish upper bounds and lower bounds for ${\gamma }_a(P_m\times P_n),{\gamma }_a(C_m\times P_n)$ and ${\gamma }_a(C_m\times C_n)$, and show that the bounds are sharp for certain $m,n$.     

Degree Ramsey numbers for even cycles

Let $H\stackrel{s}{?}G$ denote that any $s$-coloring of $E\left(H\right)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_{\Delta }(G,s)$, is $min\{\Delta \left(H\right):H\stackrel{s}{?}G\}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_{\Delta }(C_{2k},s)\ge 2s$, and Kang and Perarnau showed that $R_{\Delta }(C_4,s)=\Theta \left(s^2\right)$. Our main result is that $R_{\Delta }(C_6,s)=\Theta \left(s^{3∕2}\right)$ and $R_{\Delta }(C_{10},s)=\Theta \left(s^{5∕4}\right)$. Additionally, we substantially improve the lower bound for $R_{\Delta }(C_{2k},s)$ for general $k$.     

On the sum of distinct primes or squares of primes

In 1965 Erd?s introduced $f_2(s)$: $f_2(s)$ is the smallest integer such that every $l>f_2(s)$ is the sum of s distinct primes or squares of primes where a prime and its square are not both used. We prove that for all sufficiently large s, $f_2(s)?p_2+p_3+?+p_{s+1}+3106$, and the set of s with the equality has the density 1.     

On graphs with largest possible game domination number

Let $\gamma \left(G\right)$ and ${\gamma }_g\left(G\right)$ be the domination number and the game domination number of a graph $G$, respectively. In this paper ${\gamma }_g$-maximal graphs are introduced as the graphs $G$ for which ${\gamma }_g\left(G\right)=2\gamma \left(G\right)?1$ holds. Large families of ${\gamma }_g$-maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. ${\gamma }_g$-maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least $3$.     

Interpolating sequences in mean

This paper deals with interpolating sequences ${\left(z_n\right)}_n$ for two spaces of holomorphic functions $f$ in the unit disk $\mathbb{D}$ in $\mathbb{C}$: those that are bounded and those that satisfy a Lipschitz condition $|f\left(z\right)?f\left(w\right)|\le c|z?w{|}^{\alpha }$, $0<\alpha \le 1$. Given a sequence of values ${\left(w_n\right)}_n$ in a certain target space, we look for a function $f$ interpolating ‘in mean”, that is, with $(f\left(z_1\right)+?+f\left(z_n\right))∕n=w_n$, $n\ge 1$. We obtain target spaces when we prescribe that the corresponding interpolating sequences be the uniformly separated ones or the union of two uniformly separated ones.     

List colouring of graphs and generalized Dyck paths

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume $G$ is a graph and $f:V\left(G\right)\to N$ is a mapping. For a nonnegative integer $m$, let $f^{\left(m\right)}$ be the extension of $f$ to the graph $G$

 $\overline{K_m}$ for which $f^{\left(m\right)}\left(v\right)=\left|V\left(G\right)\right|$ for each vertex $v$ of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-paintable. We study the parameter $m_c(K_n,f)$ and $m_p(K_n,f)$ for arbitrary mappings $f$. For $\overrightarrow{x}=(x_1,x_2,\dots ,x_n)$, an $\overrightarrow{x}$-dominated path ending at $(a,b)$ is a monotonic path $P$ of the $a\times b$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i\le x_{j+1}$. Let $\psi \left(\overrightarrow{x}\right)$ be the number of $\overrightarrow{x}$-dominated paths ending at $(x_n,n)$. By this definition, the Catalan number $C_n$ equals $\psi \left((0,1,\dots ,n?1)\right)$. This paper proves that if $G=K_n$ has vertices $v_1,v_2,\dots ,v_n$ and $f\left(v_1\right)\le f\left(v_2\right)\le \dots \le f\left(v_n\right)$, then $m_c(G,f)=m_p(G,f)=\psi \left(\overrightarrow{x}\left(f\right)\right)$, where $\overrightarrow{x}\left(f\right)=(x_1,x_2,\dots ,x_n)$ and $x_i=f\left(v_i\right)?i$ for $i=1,2,\dots ,n$. Therefore, if $f\left(v_i\right)=n$, then $m_c(K_n,f)=m_p(K_n,f)$ equals the Catalan number $C_n$. We also show that if $G=G_1\cup G_2\cup ?\cup G_p$ is the disjoint union of graphs $G_1,G_2,\dots ,G_p$ and $f=f_1\cup f_2\cup ?\cup f_p$, then $m_c(G,f)={\prod }_{i=1}^p{m}_c(G_i,f_i)$ and $m_p(G,f)={\prod }_{i=1}^p{m}_p(G_i,f_i)$. This generalizes a result in Carraher et al. (2014), where the case each $G_i$ is a copy of $K_1$ is considered.     

Star-critical Ramsey numbers for large generalized fans and books

In this paper, we show that for any fixed integers $m\ge 2$ and $t\ge 2$, the star-critical Ramsey number $r_1(K_1+n{K}_t,K_{m+1})=(m?1)tn+t$ for all sufficiently large $n$. Furthermore, for any fixed integers $p\ge 2$ and $m\ge 2$, $r_1(K_p+n{K}_1,K_{m+1})=(m?1+o\left(1\right))n$ as $n\to \infty$.     

Sharpness of exponent bounds for SU(n)

The $p$-primary $v_1$-periodic homotopy groups of a topological space $X$, denoted by $v_1^{?1}{\pi }_1{\left(X\right)}_{\left(p\right)}$, are roughly the parts of the homotopy groups of $X$ localized at a prime $p$ which are detected by $K$-theory. We will use combinatorial number theory to determine, for $p$ an odd prime, the values of $n$ for which $v_1^{?1}{\pi }_{2(n?1)}{\left(SU\left(n\right)\right)}_{\left(p\right)}?\mathbb{Z}/p^{n?1+{\nu }_p\left(?\frac{n}{p}?!\right)}\text{.}$ As a corollary, we obtain new bounds for the $p$-exponent of ${\pi }_1\left(SU\left(n\right)\right)$.     

Regularity of the Eikonal equation with two vanishing entropies

Let $\mathrm{\Omega }?{\mathbb{R}}^2$ be a bounded simply-connected domain. The Eikonal equation $\left|\mathrm{?}u\right|=1$ for a function $u:\mathrm{\Omega }?{\mathbb{R}}^2\to \mathbb{R}$ has very little regularity, examples with singularities of the gradient existing on a set of positive $H^1$ measure are trivial to construct. With the mild additional condition of two vanishing entropies we show ?u is locally Lipschitz outside a locally finite set. Our condition is motivated by a well known problem in Calculus of Variations known as the Aviles–Giga problem. The two entropies we consider were introduced by Jin, Kohn [26], Ambrosio, DeLellis, Mantegazza [2] to study the Γ-limit of the Aviles–Giga functional. Formally if u satisfies the Eikonal equation and if

(1)$\mathrm{?}?({\stackrel{?}{\mathrm{\Sigma }}}_{e_1{e}_2}(\mathrm{?}{u}^{\perp }))=0\text{ and }\mathrm{?}?({\stackrel{?}{\mathrm{\Sigma }}}_{{?}_1{?}_2}(\mathrm{?}{u}^{\perp }))=0\text{ distributionally in }\mathrm{\Omega },$

where ${\stackrel{?}{\mathrm{\Sigma }}}_{e_1{e}_2}$ and ${\stackrel{?}{\mathrm{\Sigma }}}_{{?}_1{?}_2}$ are the entropies introduced by Jin, Kohn [26], and Ambrosio, DeLellis, Mantegazza [2], then ?u is locally Lipschitz continuous outside a locally finite set.Condition (1) is motivated by the zero energy states of the Aviles–Giga functional. The zero energy states of the Aviles–Giga functional have been characterized by Jabin, Otto, Perthame [25]. Among other results they showed that if ${\lim }_{n\to \infty }?I_{{?}_n}(u_n)=0$ for some sequence $u_n\in W_0^{2,2}(\mathrm{\Omega })$ and $u={\lim }_{n\to \infty }?u_n$ then ?u is Lipschitz continuous outside a finite set. This is essentially a corollary to their theorem that if u is a solution to the Eikonal equation $\left|\mathrm{?}u\right|=1$ a.e. and if for every “entropy” Φ (in the sense of [18], Definition 1) function u satisfies $\mathrm{?}?[\mathrm{\Phi }(\mathrm{?}{u}^{\perp })]=0$ distributionally in Ω then ?u is locally Lipschitz continuous outside a locally finite set. In this paper we generalize this result in that we require only two entropies to vanish.The method of proof is to transform any solution of the Eikonal equation satisfying (1) into a differential inclusion $DF\in K$ where $K?M^{2\times 2}$ is a connected compact set of matrices without Rank-1 connections. Equivalently this differential inclusion can be written as a constrained non-linear Beltrami equation. The set K is also non-elliptic in the sense of Sverak [32]. By use of this transformation and by utilizing ideas from the work on regularity of solutions of the Eikonal equation in fractional Sobolev space by Ignat [23], DeLellis, Ignat [15] as well as methods of Sverak [32], regularity is established.     

Rate of decay of s-numbers

For an operator $T\in B(X,Y)$, we denote by $a_m\left(T\right)$, $c_m\left(T\right)$, $d_m\left(T\right)$, and $t_m\left(T\right)$ its approximation, Gelfand, Kolmogorov, and absolute numbers, respectively. We show that, for any infinite-dimensional Banach spaces $X$ and $Y$, and any sequence ${\alpha }_m\searrow 0$, there exists $T\in B(X,Y)$ for which the inequality $3{\alpha }_{?m/6?}?a_m\left(T\right)?max\{c_m\left(t\right),d_m\left(T\right)\}?min\{c_m\left(t\right),d_m\left(T\right)\}?t_m\left(T\right)?{\alpha }_m/9$ holds for every $m\in \mathbb{N}$. Similar results are obtained for other $s$-scales.