Search

The Ellis semigroup of a discrete dynamical system (X, f) is denoted by E(X, f). We only consider surjective continuous functions $$f:[0,1]\rightarrow [0,1]$$ such that $$\{ f^n : n\in {\mathbb {N}}\}$$ is infinite. The main result asserts that the Ellis semigroup E([0, 1], f) is always a compactification of the natural numbers with the discrete topology. We also prove some results estimating the cardinality of the Ellis semigroup of certain dynamical systems: we show that if $$f:[0,1]\rightarrow [0,1]$$ is a continuous function with positive topological entropy, then $$|E([0,1],f)|= 2^{2^{\aleph _0}}$$ , and if $$f:[0,1]\rightarrow [0,1]$$ is a $$2^{n}$$ -function for some $$n \in {\mathbb {N}}$$ , then $$|E([0,1],f)-\{f^n:n\in {\mathbb {N}}\}|=2^n.$$

In the recent paper, authors introduced a graph topological structure, called open subset intersection graph of a topological space ϒ(τ) on a finite set X. In this present paper, we continue the st...

Let $$A$$ and $$B$$ be $$C^{*}$$ -algebras, and let $$B$$ be stable. In this paper, we construct an endofunctor $$ \mathfrak R_{X}$$ in the category of $$C^{*}$$ -algebras for every discrete metric space $$X$$ of bounded geometry and introduce the notion of $$ \mathfrak R_{X}$$ -homotopy of $$*$$ -homomorphisms from $$A$$ to $$ \mathfrak R_{X}B$$ . We study the existence problem for a group structure on the set of $$ \mathfrak R_{X}$$ -homotopy classes.

UDC 519.1 Topologies on a finite set are described by a nondecreasing sequence of nonnegative integers (the vector of topologies). We study $T_0$ -topologies on the $n$-element set that induce topologies with $k > 2^{n - 1} $ on the $(n - 1)$-element set (these induced topologies are called close to the discrete topology). Let $k$ denote the number of open sets in a topology. We obtain the form of the vector of $T_0$ -topologies with $k \geq 5 \cdot 2^{n - 4}$, which are described in works by Stanley and Kolli, and find the values $k \in [5 \cdot 2^{n - 4}, 2^{n - 1}]$, for which $T_0$ -topologies with k open sets do not exist. We describe all labeled $T_0$-topologies and indicate their number for each $k \geq 13 \cdot 2^{n - 5}$ . It is shown that there exist values $k \in (2^{n - 2}, 5 \cdot 2^{n - 4})$ such that any $T_0$ -topology with k open sets can not induce a topology close to the discrete one on an $(n - 1)$-element subset.

In this paper, we determine automorphisms of j(τ) and prove some results on j(τ),when topological space (X, τ) is finite. Also we determine necessary and sufficient condition for the open subset in...

We continue to study cluster sets of a function defined on an open subset of a topological space. In our previous papers we characterized the cluster multifunction of any function and of a continuous function. The next aim was to study cluster sets of a quasi-continuous function. But here we solve a more specific problem on cluster sets of a quasi-locally constant function (i.e., a function that is quasi-continuous with respect to the discrete topology on the range space). We prove that for any open dense subset D of a metrizable space X and a dense subspace Y of a metrizable compact space $${\overline{Y}}$$, every upper continuous compact-valued multifunction $$\Phi :X\setminus D\multimap {\overline{Y}}$$ is the cluster multifunction $${\overline{f}}$$ of some quasi-locally constant function $$f:D\rightarrow Y$$.

The continuous-time quantum walk is a particle evolving by Schr\"odinger's equation in discrete space. Encoding the space as a graph of vertices and edges, the Hamiltonian is proportional to the discrete Laplacian. In some physical systems, however, the Hamiltonian is proportional to the adjacency matrix instead. It is well-known that these quantum walks are equivalent when the graph is regular, i.e., when each vertex has the same number of neighbors. If the graph is irregular, however, the quantum walks evolve differently. In this paper, we show that for some irregular graphs, if the particle is initially localized at a certain vertex, the probability distributions of the two quantum walks are identical, even though the amplitudes differ. We analytically prove this for a graph with five vertices and a graph with six vertices. By simulating the walks on all 1,018,689,568 simple, connected, irregular graphs with eleven vertices or less, we found sixty-four graphs with this notion of equivalence. We also give eight infinite families of graphs supporting these equivalent walks., Comment: 23 pages, 15 figures

In this paper we introduce a graph topological structure, called open subset inclusion graph of a topological space on a finite set X, where the vertex set is the collection of nonempty pro...

We establish that an uncountable space X must be essentially uncountable whenever its extent and tightness are countable. As a consequence, the equality $$\mathrm{ext}(X)= t(X)=\omega $$ implies that the space $$C_{p}(X, [0,1])$$ is discretely selective. If X is a metrizable space, then $$C_{p}(X, [0,1])$$ has the Banakh property if and only if so does $$C_{p}(Y, [0,1])$$ for some closed separable $$Y\subset X$$. We apply the above results to show that, for a metrizable X, the space $$C_{p}(X, [0,1])$$ is strongly dominated by a second countable space if and only if X is homeomorphic to $$D\,{\oplus }\, M$$ where D is a discrete space and M is countable. For a metrizable space X, we also prove that $$C_{p}(X,[0,1])$$ has the Lindelof $$\Sigma $$-property if and only if the set of non-isolated points of X is second countable. Our results solve several open questions.

Given a coarse space (X, E), we endow X with the discrete topology and denote X ♯ = {p ∈ βG : each member P ∈ p is unbounded }. For p, q ∈ X ♯ , p||q means that there exists an entourage E ∈ E such that E[P] ∈ q for each P ∈ p. We say that (X, E) is orbitally discrete if, for every p ∈ X ♯ , the orbit p = {q ∈ X ♯ : p||q} is discrete in βG. We prove that every orbitally discrete space is almost finitary and scattered.

In the recent paper, authors introduced a concept of union graph \(\mho (\tau )\) of a topological space (X, τ) and discussed some basic properties such as connectedness, diameter, and girth of union graph. They proved that \(\omega (\mho (\tau ))\) and \(\chi (\mho (\tau )) \) of union graph of (X, τ) are equal, if |X| > 3. Moreover, we discussed some results on domination number, independence number, degree, etc., of a union graph. In this paper, we discuss some important properties of \(\mho (\tau ).\) It is shown that if τ be any topology defined on X with |X| = 3, then the union graph \(\mho (\tau ) \) is the connected graph if and only if topology τ is discrete topology or τ = {ϕ, X, U, V = Uc}. Moreover, we show that if τ be any topology other than discrete topology defined on X with |X| = n and if Kn or Pn+1 is a subgraph of a simple connected graph G having at most (2n − 3) vertices, then G is not a union graph of (X, τ).

Let K be a compact Hausdorff space and let C(K) be the space of all scalar-valued, continuous functions on K. We show that C(K) is an $$\ell _1(K)$$ -Grothendieck space but not a Grothendieck space exactly when the spaces $$C_p(K)$$ and $$C_p(K \oplus {\mathbb {N}}^{\#})$$ are not linearly isomorphic, where $${\mathbb {N}}^{\#}$$ is the one-point compactificiation of the discrete space of natural numbers. (That is, if C(K) contains a complemented copy of $$c_0$$ , then C(K) fails to be $$\ell _1(K)$$ -Grothendieck if and only if the topologies of pointwise convergence in $$C_p(K)$$ and $$C_p(K \oplus {\mathbb {N}}^{\#})$$ are linearly isomorphic.) Moreover, for infinite compact spaces K and L, there exists a compact space G that has a non-trivial convergent sequence and such that $$C_{p}(K\times L)$$ and $$C_{p}(G)$$ are linearly isomorphic. This extends a remarkable theorem of Cembranos and Freniche. Some examples illustrating the above results are provided.

Let$${\mathbb {K}}$$Kbe a non-trivially valued non-Archimedean complete field. Let$$\ell _{\infty }({\mathbb {N}}, {\mathbb {K}})$$ℓ∞(N,K)[$$\ell _c({\mathbb {N}}, {\mathbb {K}});$$ℓc(N,K);$$c_0({\mathbb {N}}, {\mathbb {K}})$$c0(N,K)] be the space of all sequences in$${\mathbb {K}}$$Kthat are bounded [relatively compact; convergent to 0] with the topology of pointwise convergence (i.e. with the topology induced from$${\mathbb {K}}^{{\mathbb {N}}}$$KN). LetXbe an infinite ultraregular space and let$$C_p(X,{\mathbb {K}})$$Cp(X,K)be the space of all continuous functions fromXto$${\mathbb {K}}$$Kendowed with the topology of pointwise convergence. It is easy to see that$$C_p(X,{\mathbb {K}})$$Cp(X,K)is metrizable if and only ifXis countable. We show that for anyX[with an infinite compact subset] the space$$C_p(X,{\mathbb {K}})$$Cp(X,K)has an infinite-dimensional [closed] metrizable subspace isomorphic to$$c_0({\mathbb {N}}, {\mathbb {K}})$$c0(N,K). Next we prove that$$C_p(X,{\mathbb {K}})$$Cp(X,K)has a quotient isomorphic to$$c_0({\mathbb {N}}, {\mathbb {K}})$$c0(N,K)if and only if it has a complemented subspace isomorphic to$$c_0({\mathbb {N}}, {\mathbb {K}})$$c0(N,K). It follows that for any extremally disconnected compact spaceXthe space$$C_p(X,{\mathbb {K}})$$Cp(X,K)has no quotient isomorphic to the space$$c_0({\mathbb {N}}, {\mathbb {K}})$$c0(N,K); in particular, for any infinite discrete spaceDthe space$$C_p(\beta D, {\mathbb {K}})$$Cp(βD,K)has no quotient isomorphic$$c_0({\mathbb {N}}, {\mathbb {K}})$$c0(N,K). Finally we investigate the question for whichXthe space$$C_p(X,{\mathbb {K}})$$Cp(X,K)has an infinite-dimensional metrizable quotient. We show that for any infinite discrete spaceDthe space$$C_p(\beta D, {\mathbb {K}})$$Cp(βD,K)has an infinite-dimensional metrizable quotient isomorphic to some subspace$$\ell _c^0({\mathbb {N}}, {\mathbb {K}})$$ℓc0(N,K)of$${\mathbb {K}}^{{\mathbb {N}}}$$KN. If$${\mathbb {K}}$$Kis locally compact then$$\ell _c^0({\mathbb {N}}, {\mathbb {K}})=\ell _{\infty }({\mathbb {N}}, {\mathbb {K}})$$ℓc0(N,K)=ℓ∞(N,K). If$$|n1_{{\mathbb {K}}}|\ne 1$$|n1K|≠1for some$$n\in {\mathbb {N}}$$n∈N, then$$\ell _c^0({\mathbb {N}}, {\mathbb {K}})=\ell _c ({\mathbb {N}}, {\mathbb {K}}).$$ℓc0(N,K)=ℓc(N,K).In particular,$$C_p(\beta D, {\mathbb {Q}}_q)$$Cp(βD,Qq)has a quotient isomorphic to$$\ell _{\infty }({\mathbb {N}}, {\mathbb {Q}}_q)$$ℓ∞(N,Qq)and$$C_p(\beta D, {\mathbb {C}}_q)$$Cp(βD,Cq)has a quotient isomorphic to$$\ell _c({\mathbb {N}}, {\mathbb {C}}_q)$$ℓc(N,Cq)for any prime numberq.

Let $M$ be a complete, connected Riemannian surface and suppose that $\mathcal{S} \subset M$ is a discrete subset. What can we learn about $M$ from the knowledge of all distances in the surface between pairs of points of $\mathcal{S}$? We prove that if the distances in $\mathcal{S}$ correspond to the distances in a $2$-dimensional lattice, or more generally in an arbitrary net in $\mathbb{R}^2$, then $M$ is isometric to the Euclidean plane. We thus find that Riemannian embeddings of certain discrete metric spaces are rather rigid. A corollary is that a subset of $\mathbb{Z}^3$ that strictly contains $\mathbb{Z}^2 \times \{ 0 \}$ cannot be isometrically embedded in any complete Riemannian surface., Comment: 36 pages

In applied computations the need arises to define, for example, a discrete field with assigned curl or to represent a div-free field in a given discrete space. In the low degree case this need is often fulfilled by employing tree and co-tree techniques. The definition of tree and co-tree is thus revisited here in the frame of high order Whitney element reconstructions. We consider the case of fields that are reconstructed in a contractible polyhedral domain $$\varOmega \in \mathbb R^3$$ Ω ∈ ℝ 3 , with connected boundary ∂Ω, starting from their weights over suitable “small simplices” in a simplicial mesh $${\mathcal M}$$ ℳ of the domain $$\bar \varOmega $$ Ω ̄ .

We now discuss systems of imprimitivity based on compact group rotations. In this case there are naturally arising dual systems of imprimitivity and the two together yield considerable spectral information. First we recall the definition of a compact group rotation: Let Q ⊆ S1 be a countable infinite group. Let \(G = {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{Q} _d}\) be the compact dual of Q d , where Q d is the group Q with the discrete topology. Let x0 ∈ G be the element defined by x0(q) = q for all q ∈ Q. Let τ : G → G be defined by τx = x + x0, x ∈ G. Then the system (G, τ) is called a compact group rotation.

Let $$\Gamma $$ be an infinite set equipped with the discrete topology. We prove that the space $$\ell _{\infty }(\Gamma ,{\mathbb {C}}),$$ of all complex-valued bounded functions on $$\Gamma $$ , satisfies the Mazur–Ulam property, that is, every surjective isometry from the unit sphere of $$\ell _{\infty }(\Gamma , {\mathbb {C}})$$ onto the unit sphere of an arbitrary complex Banach space X admits a unique extension to a surjective real linear isometry from $$\ell _{\infty }(\Gamma ,{\mathbb {C}})$$ to X.

In this paper we study the distortion ‖ T ‖ ‖ T − 1 ‖ of a linear embedding T : C ( K ) → C 0 ( Γ , X ) where K is a Hausdorff compactum and Γ is an infinite discrete space. We prove that if X has no subspace isomorphic to c 0 and if for some n ω the nth derivative of K is non-empty, then ‖ T ‖ ‖ T − 1 ‖ ≥ 2 n + 1 . This result extends a previous result from [3] and answers an open question from [4] .

In this paper, we shall consider the hyperspace of all nontrivial convergent sequences S c ( X ) of a Frechet-Urysohn nondiscrete space X, which is equipped with the Vietoris topology. We study the spaces X for which S c ( X ) is Baire: this kind of spaces have a dense subset of isolated points (see [12] ). We characterize the spaces X for which S c ( X ) is Baire. This characterization uses a topological game inspired by the Banach-Mazur game. As a consequence, we obtain that if X is completely metrizable and has a dense subset of isolated points, then S c ( X ) is Baire. Our last main result shows that S c ( X ) is pseudocompact iff X is homeomorphic to the one-point compactification of a discrete space of uncountable size. This last assertion provides a characterization of the one-point compactification of a discrete space of uncountable size.

Given a subbase $\mathcal S$ of a space $X$, the game $PO(\mathcal S,X)$ is defined for two players $P$ and $O$ who respectively pick, at the $n$-th move, a point $x_n\in X$ and a set $U_n\in \mathcal S$ such that $x_n\in U_n$. The game stops after the moves $\{x_n,U_n: n\in\o\}$ have been made and the player $P$ wins if $\bigcup_{n\in\o}U_n=X$; otherwise $O$ is the winner. Since $PO(\mathcal S,X)$ is an evident modification of the well-known point-open game $PO(X)$, the primary line of research is to describe the relationship between $PO(X)$ and $PO(\mathcal S,X)$ for a given subbase $\mathcal S$. It turns out that, for any subbase $\mathcal S$, the player $P$ has a winning strategy in $PO(\mathcal S,X)$ if and only if he has one in $PO(X)$. However, these games are not equivalent for the player $O$: there exists even a discrete space $X$ with a subbase $\mathcal S$ such that neither $P$ nor $O$ has a winning strategy in the game $PO(\mathcal S,X)$. Given a compact space $X$, we show that the games $PO(\mathcal S,X)$ and $PO(X)$ are equivalent for any subbase $\mathcal S$ of the space $X$.

We define pseudocompleteness in the category of locales in a conservative way; so that a space is pseudocomplete in the sense of Oxtoby [24] if and only if the locale it determines is pseudocomplete. We show that a pseudocomplete locale whose G δ -sublocales are complemented (for instance if it is scattered) is a Baire locale in the sense of Isbell [20] . Our main theorem is that products of pseudocomplete locales are pseudocomplete. Whereas every discrete space is pseudocomplete, and Boolean locales generalize discrete spaces, we demonstrate that not every Boolean locale is pseudocomplete. In [27] Pichardo-Mendoza asks whether pseudocompleteness (in topological spaces) is an invariant of closed irreducible maps. We answer this in the affirmative.

We introduce and study the concept of the super socle of C(X), denoted by SCF (X) (i.e., the set of elements of C(X), which are zero everywhere except on a countable number of points of X). Using this concept we extend some of the basic results concerning CF (X), the socle of C(X), to SCF (X). In particular, we determine spaces X such that CF (X) and SCF (X) coincide. Spaces X such that Ann(SCF (X)) is generated by an idempotent are fully characterized. It is shown that SCF (X) is an essential ideal in C(X) if and only if the set of countably isolated points (i.e., points with countable neighborhoods) of X is dense in X. The one-point Lindelöffication of uncountable discrete spaces is algebraically characterized via the concept of the super socle. Consequently, it is observed that whenever Ox ⊆ SCF (X) and SCF (X) is a regular ideal (von Neumann), then X is either a countable discrete space or the one-point Lindelöffication of an uncountable discrete space. Consequently, in this case SCF (X) is a prime ideal in C(X) (note, CF (X) is never prime C(X))

We show that every abstract homomorphism φ from a locally compact group L to a graph product G Γ , endowed with the discrete topology, is either continuous or φ ( L ) lies in a ‘small’ parabolic subgroup. In particular, every locally compact group topology on a graph product whose graph is not ‘small’ is discrete. This extends earlier work by Morris-Nickolas. We also show the following. If L is a locally compact group and if G is a discrete group which contains no infinite torsion group and no infinitely generated abelian group, then every abstract homomorphism φ : L → G is either continuous, or φ ( L ) is contained in the normalizer of a finite nontrivial subgroup of G. As an application we obtain results concerning the continuity of homomorphisms from locally compact groups to Artin and Coxeter groups.

In this paper a graph of the discrete topology under some conditions has been created. It is obtained from the composition of the topologies. The properties and domination number on the discrete topology graph have studied. On a modified graph through deleting or adding the vertex, the affection discrete topological graph domination parameter is discussed.

A metric space (X, D) is called circular if it is isometric to a subspace of a metric circle, that is, a circle in which distances are measured by the length of the shorter arc connecting them. We show that the following three conditions are equivalent: (1) X is circular, (2) every 4-point subset of X can be labeled as a, b, c, d so that \(D(a,b)+D(b,c)=D(a,c)\), \(D(b,c)+D(c,d)=D(b,d)\) holds, and (3) every 4-point subset of X is circular.

A finite sequence a → = 〈 a i 〉 i = 1 m in Z ∖ { 0 } is compressed provided a i ≠ a i + 1 for i m . It is known that if a → = 〈 a i 〉 i = 1 m and b → = 〈 b i 〉 i = 1 k are compressed sequences in Z ∖ { 0 } , then there exist idempotents p and q in β Q d ∖ { 0 } such that a 1 p + a 2 p + … + a m p = b 1 q + b 2 q + … + b k q if and only if b → is a rational multiple of a → . In fact, if b → is not a rational multiple of a → , then there is a partition of Q ∖ { 0 } into two cells, neither of which is a member of a 1 p + a 2 p + … + a m p and a member of b 1 q + b 2 q + … + b k q for any idempotents p and q in β Q d ∖ { 0 } . (Here β Q d is the Stone–Cech compactification of the set of rational numbers with the discrete topology.) In this paper we extend these results to direct sums of Q . As a corollary, we show that if b → is not a rational multiple of a → and G is any torsion free commutative group, then there do not exist idempotents p and q in β G d ∖ { 0 } such that a 1 p + a 2 p + … + a m p = b 1 q + b 2 q + … + b k q . We also show that for direct sums of finitely many copies of Q we can separate the corresponding Milliken–Taylor systems, with a similar but weaker result for the direct sum of countably many copies of Q .

The Standard Simplex Conjecture and the Plurality is Stablest Conjecture are two conjectures stating that certain partitions are optimal with respect to Gaussian and discrete noise stability respectively. These two conjectures are natural generalizations of the Gaussian noise stability result by Borell (1985) and the Majority is Stablest Theorem (2004). Here we show that the standard simplex is not the most stable partition in Gaussian space and that Plurality is not the most stable low influence partition in discrete space for every number of parts k ≥ 3, for every value ρ ≠ 0 of the noise and for every prescribed measure for the different parts as long as they are not all equal to 1/k. Our results do not contradict the original statements of the Plurality is Stablest and Standard Simplex Conjectures in their original statements concerning partitions to sets of equal measure. However, they indicate that if these conjectures are true, their veracity and their proofs will crucially rely on assuming that the sets are of equal measures, in stark contrast to Borell’s result, the Majority is Stablest Theorem and many other results in isoperimetric theory. Given our results it is natural to ask for (conjectured) partitions achieving the optimum noise stability.

Let L ( X ) be the free locally convex space over a Tychonoff space X. We show that the following assertions are equivalent: (i) L ( X ) is l ∞ -barrelled, (ii) L ( X ) is l ∞ -quasibarrelled, (iii) L ( X ) is c 0 -barrelled, (iv) L ( X ) is ℵ 0 -quasibarrelled, and (v) X is a P-space. If X is a non-discrete metrizable space, then L ( X ) is c 0 -quasibarrelled but it is neither c 0 -barrelled nor l ∞ -quasibarrelled. We prove that L ( X ) is a ( D F ) -space iff X is a countable discrete space. We show that there is a countable Tychonoff space X such that L ( X ) is a quasi- ( D F ) -space but is not a c 0 -quasibarrelled space. For each non-metrizable compact space K, the space L ( K ) is a ( d f ) -space but is not a quasi- ( D F ) -space. If X is a μ-space, then L ( X ) has the Grothendieck property iff every compact subset of X is finite. We show that L ( X ) has the Dunford–Pettis property for every Tychonoff space X. If X is a sequential space and a μ-space (for example, metrizable), then L ( X ) has the sequential Dunford–Pettis property iff X is discrete.

Let $\Gamma $ be a discrete group that acts on a semi-finite measure space $(\Omega , \mu )$ such that there is no $\Gamma $-invariant function in $L^1(\Omega , \mu )$. We show that the absence of the $\Gamma $-invariant mean on $L^\infty (\Omega ,\mu )$ is equivalent to the property $T$ of the reduced $C^*$-crossed product of $L^\infty (\Omega ,\mu )$ by $\Gamma $. In particular, if $\Lambda $ is a countable group acting ergodically on an infinite $\sigma $-finite measure space $(\Omega , \mu )$, then there exists a $\Lambda $-invariant mean on $L^\infty (\Omega , \mu )$ if and only if the corresponding crossed product does not have property $T$. Moreover, if $\Gamma $ is an ICC group, then $\Gamma $ is inner amenable if and only if $\ell ^\infty (\Gamma \setminus \{e\})\rtimes _{\mathbf {i},r} \Gamma $ does not have property $T$, where $\mathbf {i}$ is the conjugate action. On the other hand, a non-compact locally compact group $G$ is amenable if and only if $L^\infty (G)\rtimes _{\mathbf {lt}, r} G_\mathrm {d}$ does not have property $T$, where $G_\mathrm {d}$ is the group $G$ equipped with the discrete topology and $\mathbf {lt}$ is the left translation.

Influence maximization is the task of finding $k$ seed nodes in a social network such that the expected number of activated nodes in the network (under certain influence propagation model), referred to as the influence spread, is maximized. Lattice influence maximization (LIM) generalizes influence maximization such that, instead of selecting $k$ seed nodes, one selects a vector $\mathbf {x}=(x_{1}, \ldots, x_{d})$ from a discrete space $\mathcal {X}$ called a lattice, where $x_{j}$ corresponds to the $j$ th marketing strategy and $\mathbf {x}$ represents a marketing strategy mix. Each strategy mix $\mathbf {x}$ has probability $h_{u}(\mathbf {x})$ to activate a node $u$ as a seed. LIM is the task of finding a strategy mix under the constraint $\sum _{j} x_{j} \le k$ such that its influence spread is maximized. We adopt the reverse influence sampling (RIS) approach and design scalable algorithms for LIM. We explore two complementary design choices: one algorithm IMM-PRR is based on partial coverage on reverse-reachable sets, and the other IMM-VSN is based on incorporating virtual strategy nodes. IMM-PRR can be applied as a general solution to LIM, and we further improve its efficiency for a large family of models where each strategy independently activates seed nodes. IMM-VSN is explicitly designed for the case of independent strategy activation, and it uses virtual nodes to represent strategies to reduce LIM back to the original influence maximization problem. We prove that both IMM-PRR and IMM-VSN guarantee $1-1/e-\varepsilon $ approximation for small $\varepsilon > 0$ . We further extend LIM to the partitioned budget case where strategies are partitioned into groups, each of which has a separate budget, and show that a minor variation of our algorithms would achieve $1/2 -\varepsilon $ approximation ratio with the same time complexity. Empirically, through extensive tests, we demonstrate that IMM-VSN runs faster than IMM-PRR and much faster than other baseline algorithms while providing the same level of influence spread. We conclude that IMM-VSN is the best one for models with independent strategy activations, while IMM-PRR works for general modes without this assumption.

We consider the Stone space of the Boolean algebra, constructed by M.G. Bell (see Example 2.1 in [2] ), which is the compactification, BN , of the countable discrete space N . Here we consider convergent sequences in B N ∖ N . We prove that if a point x ∈ B N ∖ N is the limit of some sequence { s n : n ∈ ω } from N , or a point x ∈ [ A ] ∖ A , where A ⊆ N is a strict anti-chain in N , then there is a sequence in B N ∖ N , that converges to x . We also prove that if A is a countable discrete set of u -points in B N ∖ N and x ∈ [ A ] ∖ A , then x is not the limit of any sequence of points of B N ∖ N .

Given a stream of rectangles over a discrete space, we consider the problem of computing the total number of distinct points covered by the rectangles. This is the discrete version of the two-dimensional Klee's measure problem for streaming inputs. Given 0 < ? , ? < 1 , we provide ( ? , ? ) -approximations for bounded side length rectangles and for bounded aspect ratio rectangles. For the case of arbitrary rectangles, we provide an O ( log ? U ) -approximation, where U is the total number of discrete points in the two-dimensional space. The time to process each rectangle and the total required space are polylogarithmic in U. The time to answer a query for the total area is constant. We construct efficient transformation techniques that project rectangle areas to one-dimensional ranges and then use a streaming algorithm for the one-dimensional Klee's measure problem to obtain these approximations. The projections are deterministic, and to our knowledge, these are the first approaches of this kind that provide efficiency and accuracy trade-offs in the streaming model.

We study the class H of all topological abelian groups ( G , τ ) with the property that the only locally compact group topology on G strictly finer than τ is the discrete topology. Hewitt showed that the reals R and the circle group T belong to H and Rickert and Rajagopalan characterized the non-discrete locally compact groups in the class H as those that contain either T , R , or the compact group J p of p-adic integers as an open subgroup. We describe the entire class H , providing many examples of non-locally compact groups with this property. This allows us to obtain as a by-product the results of Hewitt, Rajagopalan and Rickert and give some applications to characterized subgroups.

We show that (1) assuming there is no rapid ultrafilter, every countable nondiscrete maximally almost periodic topological group contains a discrete nonclosed subset which is a convergent sequence in some weaker totally bounded group topology, (2) every infinite Abelian totally bounded topological group contains such a discrete subset (in ZFC), and (3) if an extremally disconnected topological group contains such a discrete subset, then there is a selective ultrafilter.

We prove that, for every n , the topological space ω n ω (where ω n has the discrete topology) can be partitioned into ℵ n copies of the Baire space. Using this fact, we then prove two new theorems about completely ultrametrizable spaces. We say that Y is a condensation of X if there is a continuous bijection f : X → Y . First, it is proved that ω ω is a condensation of ω n ω if and only if ω ω can be partitioned into ℵ n Borel sets, and some consistency results are given regarding such partitions. It is also proved that it is consistent with ZFC that, for any n ω , c = ω n and there are exactly n + 3 similarity types of perfect completely ultrametrizable spaces of size c . These results answer two questions of the first author from [1] .

We study massive (reccurent) sets with respect to a certain random walk $S_\alpha $ defined on the integer lattice $\mathbb{Z} ^d$, $d=1,2$. Our random walk $S_\alpha $ is obtained from the simple random walk $S$ on $\mathbb{Z} ^d$ by the procedure of discrete subordination. $S_\alpha $ can be regarded as a discrete space and time counterpart of the symmetric $\alpha $-stable Levy process in $\mathbb{R}^d$. In the case $d=1$ we show that some remarkable proper subsets of $\mathbb{Z}$ , e.g. the set $\mathcal{P}$ of primes, are massive whereas some proper subsets of $\mathcal{P}$ such as Leitmann primes $\mathcal{P}_h$ are massive/non-massive depending on the function $h$. Our results can be regarded as an extension of the results of McKean (1961) about massiveness of the set of primes for the simple random walk in $\mathbb{Z}^3$. In the case $d=2$ we study massiveness of thorns and their proper subsets.

There is a well-known natural topology on the set of compatible total orders on a group, and recent results of Clay [2] , Dabkowska et al. [4] , and Sikora [12] have characterized this topology for certain groups. We consider a similar topology on the set of distinct monomial algebras in polynomial and Laurent polynomial rings. We study the latter topological structure for monomial algebras that come from rings of multiplicative invariants and show that they are either finite discrete spaces or homeomorphic to the Cantor set.

International audience; Rigid motions in $\mathbb{R}^2$ are fundamental operations in 2D image processing. They satisfy many properties: in particular, they are isometric and therefore bijective. Digitized rigid motions, however, lose these two properties. To investigate the lack of injectivity or surjectivity and more generally their local behavior, we extend the framework initially proposed by Nouvel and R\'emila to the case of digitized rigid motions. Yet, for practical applications, the relevant information is not global bijectivity, which is seldom achieved, but bijectivity of the motion restricted to a given finite subset of $\mathbb{Z}^2$. We propose two algorithms testing that condition. Finally, because rotation angles are rarely given with infinite precision, we propose a third algorithm providing optimal angle intervals that preserve this restricted bijectivity.

International audience; Let G = (Ω, E) be a graph and let d be the graph distance. Consider a discrete-time Markov chain {Z t } on Ω whose kernel p satisfies p(x, y) > 0 ⇒ {x, y} ∈ E for every x, y ∈ Ω. In words, transitions only occur between neighboring points of the graph. Suppose further that (Ω, p, d) has coarse Ricci curvature at least 1/α in the sense of Ollivier: For all x, y ∈ Ω, it holds that W 1 (Z 1 | {Z 0 = x}, Z 1 | {Z 0 = y}) ≤ 1 − 1 α d(x, y), where W 1 denotes the Wasserstein 1-distance. In this note, we derive a transport-entropy inequality: For any measure µ on Ω, it holds that W 1 (µ, π) ≤ √(2α/(2-1/α) D(µ ll π)) , where π denotes the stationary measure of {Z t } and D(·ll·) is the relative entropy. Peres and Tetali have conjectured a stronger consequence of coarse Ricci curvature, that a modified log-Sobolev inequality (MLSI) should hold, in analogy with the setting of Markov diffusions. We discuss how our approach suggests a natural attack on the MLSI conjecture.

Most of the previous algorithms focus on computing the convex hull for a set of points. In this paper, we present a method for approximating the convex hull for a set of spheres with various radii in discrete space. Computing the convex hull for a set of spheres is a base technology for many applications that study structural properties of molecules. We present a voxel map data structures, where the molecule is represented as a set of spheres, and corresponding algorithms. Based on CUDA programming for using the parallel architecture of GPU, our algorithm takes less than 40ms for computing the convex hull of 6,400 spheres in average.

For a countable discrete space V, every nondegenerate separable C*-correspondence over c_0(V) is isomorphic to one coming from a directed graph with vertex set V. In this paper we demonstrate why the analogous characterizations fail to hold for higher-rank graphs (where one considers product systems of C*-correspondences) and for topological graphs (where V is locally compact Hausdorff), and we discuss the obstructions that arise., Comment: major revision; stated some results in greater generality

I propose a random network model governed by a Gaussian weight corresponding to Ising link antiferromagnetism as a model for emergent quantum space-time. In this model, discrete space is fundamental, not a regularization, its spectral dimension $d_s$ is not a model input but is, rather, completely determined by the antiferromagnetic coupling constant. Perturbative terms suppressing triangles and favouring squares lead to locally Euclidean ground states that are Ricci flat "large worlds" with power-law extension. I then consider the quenched graphs of lowest energy for $d_s=2$ and $d_s=3$ and I show how quenching leads to the spontaneous emergence of embedding spaces of Hausdorff dimension $d_H=4$ and $d_H=5$, respectively. One of the additional, spontaneous dimensions can be interpreted as time, causality being an emergent property that arises in the large $N$ limit (with $N$ the number of vertices). For $d_s=2$, the quenched graphs constitute a discrete version of a 5D-space-filling surface with a number of fundamental degrees of freedom scaling like $N^{2/5}$, a graph version of the holographic principle. These holographic degrees of freedom can be identified with the squares of the quenched graphs, which, being these triangle-free, are the fundamental area (or loop) quanta., To appear in Physical Review E

A natural duality is obtained for each finitely generated variety B n ( n p -algebras. The duality for B n is based on a schizophrenic object: P −1 in B n is the algebra 2 n ⊕ 1 which generates the variety and P −1 is a topological relational structure carrying the discrete topology and a set of algebraic relations. The relations are (i) the graphs of a (3-element) generating set for the endomorphism monoid of P −1 and (ii) a set of subalgebras of P 2 −2 in one-to-one correspondence with partitions of the integer n . Each of the latter class of relations, regarded as a digraph, is ‘nearly’ the union of two isomorphic trees. The duality is obtained by the piggyback method of Davey and Werner (which has previously yielded a duality in case n ≤ 2), combined with use of the restriction to finite p -algebras of the duality for bounded distributive lattices, which enables the relations suggested by the general theory to be concretely described.

Given the pairwise distances for a set of unknown points in a known metric space, the distance geometry problem DGP is to compute the point coordinates in conformation with the distance constraints. It is a well-known problem in the Euclidean space, has several variations, finds many applications, and so has been attempted by different researchers from time to time. However, to the best of our knowledge, it is not yet fully addressed to its merit, especially in the discrete space. Hence, in this paper we introduce a novel variant of DGP where the pairwise distance between every two unknown points is given a tolerance zone with the objective of finding the solution as a collection of integer points. The solution is based on characterization of different types of annulus intersection, their equivalence, and cardinality bounds of integer points. Necessary implementation details and useful heuristics make it attractive for practical applications in the discrete space.

Although the concept of functional plane for naive plane is studied and reported in the literature in great detail, no similar study is yet found for naive sphere. This article exposes the first study in this line, openingi¾?up further prospects of analyzing the topological properties of sphere in the discrete space. We show that each quadraginta octantQ of a naive sphere forms a bijection with its projected pixeli¾?set on a unique coordinate plane, which thereby serves as the functional plane of Q, and hence gives rise to merely mono-jumps during back projection. The other two coordinate planes serve as para-functional and dia-functional planes for Q, as the former is 'mono-jumping' but not bijective, whereas the latter holds neither of the two. Owing to this, the quadraginta octants form symmetry groups and subgroups with equivalent jump conditions. We also show a potential application in generating a special class of discrete 3D circles based on back projection and jump bridging by Steiner voxels. A circle in this class possesses 4-symmetry, uniqueness, and bounded distance from the underlying real sphere and real plane.

Skeletonization is a necessary process in a variety of applications in image processing and object recognition. However, the concept of a skeleton, defined using either the union of centers of maximal discs or the union of points with more than one generating points, was originally formulated in continuous space. When they are applied to situation in discrete space, the resulting skeletons may become disconnected and further works are needed to link them. In this paper, we propose a novel skeletonization method which extends the concept of a skeleton to include both continuous and discrete space using generalized Voronoi diagrams. We also present a skeleton pruning method which is able to remove noisy branches by evaluating their significance. Three experimental results demonstrate that: (1) our method is stable across a wide range of shapes, and (2) it performs better in accuracy and robustness than previous approaches for processing shapes whose boundaries contain substantial noise.

In this paper we prove that there are operators in the uniform Roe algebra \({C_u^*(G)}\) which cannot be approximated by the truncations of themselves, where G is a finitely generated group. We also give a sufficient condition for the operators which can be approximated by the truncations of themselves. For a countable discrete metric space X, we obtain the similar conclusions.

Let D be a countable discrete space and let p∈D. For any primitive shift σ:D→D∖{p} there are 2c σ-invariant maximal almost disjoint families on D. This implies that there are 2c pairwise non-homeomorphic Ψ⁎ spaces admitting primitive shifts. Under a=c there exists a maximal almost disjoint family F on a countable discrete space D such that the spaces Ψ(F) and Ψ⁎(F) admit no primitive shift.

We characterize those topological spaces Y for which the Isbell and finest splitting topologies on the set C ( X , Y ) of all continuous functions from X into Y coincide for all topological spaces X. We also consider the same question for the coincidence of the restriction of the finest splitting topology on the upper semicontinuous set-valued functions to C ( X , Y ) and the finest splitting topology on C ( X , Y ) . In the first case, the spaces in question are, after identifying points that are in each others closures, subsets of the two point Sierpinski space, which gives a converse and generalization of a result of S. Dolecki, G.H. Greco, and A. Lechicki. In the second case, the spaces in question are, after identifying points that are in each others closures, order bases for bounded complete continuous DCPOs with the Scott topology.