Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition

A hidden Markov model (HMM) is said to have path-mergeable states   if for any two states i,j$i,j$ there exist a word w$w$ and state k$k$ such that it is possible to transition from both i$i$ and j$j$ to k$k$ while emitting w$w$. We show that for a finite HMM with path-mergeable states the block estimates of the entropy rate converge exponentially fast. We also show that the path-mergeability property is asymptotically typical in the space of HMM topologies and easily testable.     

Polychromatic 4-coloring of cubic even embeddings on the projective plane

A polychromatic     k$k$-coloring   of a map G$G$ on a surface is a k$k$-coloring such that each face of G$G$ has all k$k$ colors on its boundary vertices. An even embedding     G$G$ on a surface is a map of a simple graph on the surface such that each face of G$G$ is bounded by a cycle of even length. In this paper, we shall prove that a cubic even embedding G$G$ on the projective plane has a polychromatic proper 4-coloring if and only if G$G$ is not isomorphic to a Möbius ladder with an odd number of rungs. For proving the theorem, we establish a generating theorem for 3-connected Eulerian multi-triangulations on the projective plane.     

Constant-factor approximation of the domination number in sparse graphs

The k$k$-domination number   of a graph is the minimum size of a set D$D$ such that every vertex of G$G$ is at distance at most k$k$ from D$D$. We give a linear-time constant-factor algorithm for approximation of the k$k$-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, proper classes closed on topological minors and classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge.     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

[1, 2]-sets in graphs

A subset S⊆V$S\subseteq V$ in a graph G=(V,E)$G=(V,E)$ is a [j,k]$[j,k]$-set if, for every vertex v∈V?S$v\in V?S$, j≤|N(v)∩S|≤k$j\le |N\left(v\right)\cap S|\le k$ for non-negative integers j$j$ and k$k$, that is, every vertex v∈V?S$v\in V?S$ is adjacent to at least j$j$ but not more than k$k$ vertices in S$S$. In this paper, we focus on small j$j$ and k$k$, and relate the concept of [j,k]$[j,k]$-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k$k$-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G$G$, the restrained domination number is equal to the domination number of G$G$.     

A combinatorial proof of the skew K-saturation theorem

We give a combinatorial proof of the skew version of the K-saturation theorem. More precisely, for any positive integer k$k$, we give an explicit injection from the set of skew semistandard Young tableaux with skew shape kλ/kμ$k\lambda /k\mu$ and type kν$k\nu$, to the set of skew semistandard Young tableaux of shape λ/μ$\lambda /\mu$ and type ν$\nu$.     

A note on distance-regular graphs with a small number of vertices compared to the valency

In this note we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given α>2$\alpha >2$, there are finitely many distance-regular graphs Γ$\Gamma$ with valency k$k$, diameter D≥3$D\ge 3$ and v$v$ vertices satisfying v≤αk$v\le \alpha k$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite). We also show, as a consequence of this result, that there are finitely many distance-regular graphs with valency k≥3$k\ge 3$, diameter D≥3$D\ge 3$ and _c2≥εk$c_2\ge \epsilon k$ for a given 0<ε<1$0<\epsilon <1$ unless (D=3$D=3$ and Γ$\Gamma$ is imprimitive) or (D=4$D=4$ and Γ$\Gamma$ is antipodal and bipartite).     

On topological entropy of commuting tree maps

Let T$T$ be a tree with s$s$ ends and f,g$f,g$ be continuous maps from T$T$ to T$T$ with f°g=g°f$f°g=g°f$. In this note we show that if there exists a positive integer m≥2$m\ge 2$ such that gcd(m,l)=1$gcd(m,l)=1$ for any 2≤l≤s$2\le l\le s$ and f,g$f,g$ share a periodic point which is a km$km$-periodic point of f$f$ for some positive integer k$k$, then the topological entropy of f°g$f°g$ is positive.     

Quandle cocycles from invariant theory

Let G$G$ be a group. Any G$G$-module M$M$ has an algebraic structure called a G$G$-family of Alexander quandles. Given a 2-cocycle of a cohomology associated with this G$G$-family, topological invariants of (handlebody) knots in the 3-sphere are defined. We develop a simple algorithm to algebraically construct n$n$-cocycles of this G$G$-family from G$G$-invariant group n$n$-cocycles of the abelian group M$M$. We present many examples of 2-cocycles of these G$G$-families using facts from (modular) invariant theory.     

Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

Fixed point theorem for generalized Φ -pseudocontractive mappings

Let E$E$ be a real Banach space, C$C$ be a nonempty closed convex subset of E$E$ and T:C→C$T:C\to C$ be a continuous generalized Φ$\Phi$-pseudocontractive mapping. It is proved that T$T$ has a unique fixed point in C$C$.     

Oscillation of harmonic functions for subordinate Brownian motion and its applications

In this paper, we establish an oscillation estimate of nonnegative harmonic functions for a pure-jump subordinate Brownian motion. The infinitesimal generator of such subordinate Brownian motion is an integro-differential operator. As an application, we give a probabilistic proof of the following form of relative Fatou theorem for such subordinate Brownian motion X$X$ in a bounded κ$\kappa$-fat open set; if u$u$ is a positive harmonic function with respect to X$X$ in a bounded κ$\kappa$-fat open set D$D$ and h$h$ is a positive harmonic function in D$D$ vanishing on D^c$D^c$, then the non-tangential limit of u/h$u/h$ exists almost everywhere with respect to the Martin-representing measure of h$h$.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Every point is critical

We show that, for any compact Alexandrov surface S$S$ (without boundary) and any point y$y$ in S$S$, there exists a point x$x$ in S$S$ for which y$y$ is a critical point. Moreover, we prove that uniqueness characterizes the surfaces homeomorphic to the sphere among smooth orientable surfaces.     

On prime ideals and radicals of polynomial rings and graded rings

We extend some known results on radicals and prime ideals from polynomial rings and Laurent polynomial rings to Z$\mathbb{Z}$-graded rings, i.e, rings graded by the additive group of integers. The main of them concerns the Brown–McCoy radical G$G$ and the radical S$S$, which for a given ring A$A$ is defined as the intersection of prime ideals I$I$ of A$A$ such that A/I$A/I$ is a ring with a large center. The studies are related to some open problems on the radicals G$G$ and S$S$ of polynomial rings and situated in the context of Koethe’s problem.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.