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

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.     

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.     

Modules satisfying the weak Nakayama property

Let R$R$ be a commutative ring with identity. We will say that an R$R$-module M$M$ satisfies the weak Nakayama property, if IM=M$IM=M$, where I$I$ is an ideal of R$R$, implies that for any x∈M$x\in M$ there exists a∈I$a\in I$ such that (a−1)x=0$(a-1)x=0$. In this paper, we will study modules satisfying the weak Nakayama property. It is proved that if R$R$ is a local ring, then R$R$ is a Max ring if and only if J(R)$J\left(R\right)$, the Jacobson radical of R$R$, is T$T$-nilpotent if and only if every R$R$-module satisfies the weak Nakayama property.     

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.     

Disjoint cycles with different length in 4-arc-dominated digraphs

A d$d$-arc-dominated digraph is a digraph D$D$ of minimum out-degree d$d$ such that for every arc (x,y)$(x,y)$ of D$D$, there exists a vertex u$u$ of D$D$ of out-degree d$d$ such that (u,x)$(u,x)$ and (u,y)$(u,y)$ are arcs of D$D$. Henning and Yeo [Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012) 687–694] conjectured that a digraph with minimum out-degree at least four contains two vertex-disjoint cycles of different length. In this paper, we verify this conjecture for 4-arc-dominated digraphs.     

An upper bound for a valence of a face in a parallelohedral tiling

Consider a face-to-face parallelohedral tiling of R^d${\mathbb{R}}^d$ and a (d−k)$(d-k)$-dimensional face F$F$ of the tiling. We prove that the valence of F$F$ (i.e. the number of tiles containing F$F$ as a face) is not greater than 2^k$2^k$. If the tiling is affinely equivalent to a Voronoi tiling for some lattice (the so called Voronoi case), this gives a well-known upper bound for the number of vertices of a Delaunay k$k$-cell. Yet we emphasize that such an affine equivalence is not assumed in the proof.     

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

On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence

In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s$s$-dimensional sequence m$m$, whose elements are vectors obtained by concatenating d$d$-dimensional vectors from a low-discrepancy sequence q$q$ with (s−d)$(s-d)$-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0$\epsilon >0$ the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$ is bounded by ε$\epsilon$ with probability at least 1−2exp(−ε²N/2)$1-2exp(-{\epsilon }^{2}N/2)$ for N$N$ sufficiently large. The authors did not study how large N$N$ actually has to be and if and how this actually depends on the parameters s$s$ and ε$\epsilon$. In this note we derive a lower bound for N$N$, which significantly depends on s$s$ and ε$\epsilon$. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N$N$ points of m$m$ and q$q$, which holds without any restrictions on N$N$. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N$N$. We compare this bound to other known bounds.     

Time homogeneous diffusions with a given marginal at a deterministic time

In this article, it is proved that for any probability law μ$\mu$ over R$\mathbb{R}$ with finite first moment and a given deterministic time t>0$t>0$, there exists a gap diffusion with law μ$\mu$ at the prescribed time t$t$.     

Parametric inference for discretely observed multidimensional diffusions with small diffusion coefficient

We consider a multidimensional diffusion X$X$ with drift coefficient b(α,_Xt)$b(\alpha ,X_t)$ and diffusion coefficient ?σ(β,_Xt)$?\sigma (\beta ,X_t)$. The diffusion sample path is discretely observed at times _tk=kΔ$t_k=k\Delta$ for k=1…n$k=1\dots n$ on a fixed interval [0,T]$[0,T]$. We study minimum contrast estimators derived from the Gaussian process approximating X$X$ for small ?$?$. We obtain consistent and asymptotically normal estimators of α$\alpha$ for fixed Δ$\Delta$ and ?→0$?\to 0$ and of (α,β)$(\alpha ,\beta )$ for Δ→0$\Delta \to 0$ and ?→0$?\to 0$ without any condition linking ?$?$ and Δ$\Delta$. We compare the estimators obtained with various methods and for various magnitudes of Δ$\Delta$ and ?$?$ based on simulation studies. Finally, we investigate the interest of using such methods in an epidemiological framework.     

Frobenius groups and retract rationality

Let k$k$ be any field, G$G$ be a finite group acting on the rational function field k(_xg:g∈G)$k(x_g:g\in G)$ by h⋅_xg=_xhg$h\cdot x_g=x_{hg}$ for any h,g∈G$h,g\in G$. Define k(G)=k(_xg:g∈G)^G$k\left(G\right)=k{(x_g:g\in G)}^G$. Noether’s problem asks whether k(G)$k\left(G\right)$ is rational (= purely transcendental) over k$k$. A weaker notion, retract rationality introduced by Saltman, is also very useful for the study of Noether’s problem. We prove that, if G$G$ is a Frobenius group with abelian Frobenius kernel, then k(G)$k\left(G\right)$ is retract k$k$-rational for any field k$k$ satisfying some mild conditions. As an application, we show that, for any algebraic number field k$k$, for any Frobenius group G$G$ with Frobenius complement isomorphic to S_L2(_F5)$S{L}_2\left({\mathbb{F}}_5\right)$, there is a Galois extension field K$K$ over k$k$ whose Galois group is isomorphic to G$G$, i.e. the inverse Galois problem is valid for the pair (G,k)$(G,k)$. The same result is true for any non-solvable Frobenius group if k(_ζ8)$k\left({\zeta }_8\right)$ is a cyclic extension of k$k$.     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.