The security number of lexicographic products

A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] ? S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results.     

Bounds on global secure sets in cactus trees

Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances.     

Expanders obtained from affine transformations

A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ _G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ _G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.     

On a graph’s security number

A secure set S⊆V of graph G=(V,E) is a set whose every nonempty subset can be successfully defended from an attack, under appropriate definitions of “attack” and “defended.” The set S is secure when |N[X]∩S|≥|N[X]−S| for every X⊆S. The smallest cardinality of a secure set in G is the security number of G. New bounds for the security number are established, the effect of some graph modifications on the security number is investigated, and the exact value of the security number for some families of graphs is given.     

On cardinality bounds involving the weak Lindelöf degree

We give a general closing-off argument in Theorem 2.3 from which several corollaries follow, including (1) if X is a locally compact Hausdorff space then |X| ≤ 2^wL(X)ψ(X), and (2) if X is a locally compact power homogeneous Hausdorff space then |X| ≤ 2^wL(X)t(X). The first extends the well-known cardinality bound 2^ψ(X) for a compactum X in a new direction. As |X| ≤ 2^wL(X)χ(X) for a normal spaceX[4], this enlarges the class of known Tychonoff spaces for which this bound holds. In 2.12 we give a short, direct proof of (1) that does not use 2.3. Yet 2.3 is broad enough to establish results much more general than (1), such as if X is a regular space with a π-base ? such that |B| ≤ 2^wL(X)χ(X) for all B ∈ ?, then |X| ≤ 2^wL(X)χ(X).

Separately, it is shown that if X is a regular space with a π-base whose elements have compact closure, then |X| ≤ 2^{wL(X)ψ(X)t(X)}. This partially answers a question from [4] and gives a third, separate proof of (1). We also show that if X is a weakly Lindelöf, normal, sequential space with χ(X) ≤ 2^?0, then |X| ≤ 2^?0.

Result (2) above is a new generalization of the cardinality bound 2^t(X) for a power homogeneous compactum X (Arhangel'skii, van Mill, and Ridderbos [3], De la Vega in the homogeneous case [10]). To this end we show that if U ? clD ? X, where X is power homogeneous and U is open, then |U| ≤ |D|^πχ(X). This is a strengthening of a result of Ridderbos [19].     

Sperner families over a subset

Let |X| = n > 0, |Y| = k > 0, and Y ? X. A family A of subsets of X is a Sperner family of X over Y if A₁A₂ for every pair of distinct members of A and every member of A has a nonempty intersection with Y. The maximum cardinality f(n, k) of such a family is determined in this paper. $\text{f(n,k)=(}\text{n}\text{[n}\text{2]}\text{)?(}\text{?k}\text{[n}\text{2]}\text{)}$.     

Torsion units in integral group rings of some metabelian groups,II

We prove that any torsion unit of the integral group ring ZG is rationally conjugate to a trivial unit if G = A ⋊ X with both A and X abelian, |Xz.sfnc; < p for every prime p dividing |A| provided either |X| is prime or A ic cyclic.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

When is a Pixley-Roy hyperspace CCC?

A space X is said to satisfy condition (C) if for every Y?X with |Y|=ω₁, any family $\text{G}$ of open subsets of Y with |$\text{G}$|=ω₁ has a countable network. It is easy to see that if X satisfies condition (C), then its Pixley-Roy hyperspace $\text{F}$[X] is CCC. We show that under MA_ω1 condition (C) is also necessary for $\text{F}$[X] to be CCC, but under CH it is not.     

On sets of integers whose shifted products are powers

Let N be a positive integer and let A be a subset of {1,…,N} with the property that aa^′+1 is a pure power whenever a and a^′ are distinct elements of A. We prove that |A|, the cardinality of A, is not large. In particular, we show that |A|?(logN)^2/3(loglogN)^1/3.     

Automata accepting primitive words

LeA be an automaton whose set of inputs equalsX (|X|≧2) and whose cardinality of the set of states equalsn (n≧2), and letQ be the set of all primitive words overX. ByT(A) we denote the language accepted byA. In this paper, we give the following results:

Projective versions of selection principles

All spaces are assumed to be Tychonoff. A space X is called projectively P (where P is a topological property) if every continuous second countable image of X is P. Characterizations of projectively Menger spaces X in terms of continuous mappings , of Menger base property with respect to separable pseudometrics and a selection principle restricted to countable covers by cozero sets are given. If all finite powers of X are projectively Menger, then all countable subspaces of Cp(X) have countable fan tightness. The class of projectively Menger spaces contains all Menger spaces as well as all σ-pseudocompact spaces, and all spaces of cardinality less than d. Projective versions of Hurewicz, Rothberger and other selection principles satisfy properties similar to the properties of projectively Menger spaces, as well as some specific properties. Thus, X is projectively Hurewicz iff Cp(X) has the Monotonic Sequence Selection Property in the sense of Scheepers; βX is Rothberger iff X is pseudocompact and projectively Rothberger. Embeddability of the countable fan space Vω into Cp(X) or Cp(X,2) is characterized in terms of projective properties of X.     

Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances

Let Ω^Ω be the semigroup of all mappings of a countably infinite set Ω. If U and V are subsemigroups of Ω^Ω, then we write U≈V if there exists a finite subset F of Ω^Ω such that the subsemigroup generated by U and F equals that generated by V and F. The relative rank of U in Ω^Ω is the least cardinality of a subset A of Ω^Ω such that the union of U and A generates Ω^Ω. In this paper we study the notions of relative rank and the equivalence ≈ for semigroups of endomorphisms of binary relations on Ω.The semigroups of endomorphisms of preorders, bipartite graphs, and tolerances on Ω are shown to lie in two equivalence classes under ≈. Moreover such semigroups have relative rank 0, 1, 2, or d in Ω^Ω where d is the minimum cardinality of a dominating family for N^N. We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in Ω^Ω are 0, 1, 2, and d.We show that the endomorphism semigroups of graphs, in general, fall into at least four classes under ≈ and that there exist graphs where the relative rank of the endomorphism semigroup is 2^ℵ₀.     

A Spanning Tree with High Degree Vertices

Let G be a connected graph, let ${X \subset V(G)}$ and let f be a mapping from X to {2, 3, . . .}. Kaneko and Yoshimoto (Inf Process Lett 73:163–165, 2000) conjectured that if |N _G (S) ? X| ≥ f (S) ? 2|S| + ω _G (S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ . In this paper, we show a result with a stronger assumption than this conjecture; if |N _G (S) ? X| ≥ f (S) ? 2|S| + α(S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ .     

A fixed point theorem for the pseudo-circle

Let f:C→C be a self-map of the pseudo-circle C. Suppose that C is embedded into an annulus A, so that it separates the two components of the boundary of A. Let F:A→A be an extension of f to A (i.e. F|C=f). If F is of degree d then f has at least |d−1| fixed points. This result generalizes to all plane separating circle-like continua.     

Higher syzygies of hyperelliptic curves

Let X be a hyperelliptic curve of arithmetic genus g and let f:X→P¹ be the hyperelliptic involution map of X. In this paper we study higher syzygies of linearly normal embeddings of X of degree d≤2g. Note that the minimal free resolution of X of degree ≥2g+1 is already completely known. Let A=f^∗O_P¹(1), and let L be a very ample line bundle on X of degree d≤2g. For , we call the pair (m,d−2m)the factorization type ofL. Our main result is that the Hartshorne-Rao module and the graded Betti numbers of the linearly normal curve embedded by |L| are precisely determined by the factorization type of L.     

A first countable linearly Lindelöf not Lindelöf topological space

A topological space X is called linearly Lindelöf if every increasing open cover of X has a countable subcover. It is well known that every Lindelöf space is linearly Lindelöf. The converse implication holds only in particular cases, such as X being countably paracompact or if nw(X)<ℵω.Arhangel?skii and Buzyakova proved that the cardinality of a first countable linearly Lindelöf space does not exceed ℵ₀². Consequently, a first countable linearly Lindelöf space is Lindelöf if ℵω>ℵ₀². They asked whether every linearly Lindelöf first countable space is Lindelöf in ZFC. This question is supported by the fact that all known linearly Lindelöf not Lindelöf spaces are of character at least ℵω. We answer this question in the negative by constructing a counterexample from MA+ℵω<ℵ₀².A modification of Alster?s Michael space that is first countable is presented.     

Fixed points on model solvmanifold pairs

In this paper we define model solvmanifold pairs and their diagonal type selfmaps in the tradition of Heath and Keppelmann. We derive an explicit formula for computing the relative Nielsen number N(F;X,A) on these spaces and selfmaps F:(X,A)→(X,A). We find that model solvmanifold pairs often exhibit interesting Schirmer theory, meaning N(F;X,A)>max{N(F),N(F|_A)}.     

Distinguishing labeling of group actions

Suppose Γ is a group acting on a set X. An r-labeling f:X→{1,2,…,r} of X is distinguishing (with respect to Γ) if the only label preserving permutation of X in Γ is the identity. The distinguishing number, D_Γ(X), of the action of Γ on X is the minimum r for which there is an r-labeling which is distinguishing. This paper investigates the relation between the cardinality of a set X and the distinguishing numbers of group actions on X. For a positive integer n, let D(n) be the set of distinguishing numbers of transitive group actions on a set X of cardinality n, i.e., D(n)={D_Γ(X):|X|=n and Γ acts transitively on X}. We prove that . Then we consider the problem of an arbitrary fixed group Γ acting on a large set. We prove that if for any action of Γ on a set Y, for each proper normal subgroup H of Γ, D_H(Y)≤2, then there is an integer n such that for any set X with |X|≥n, for any action of Γ on X with no fixed points, D_Γ(X)≤2.     

The Kähler Ricci flow on Fano surfaces (I)

Suppose {(M, g(t)), 0 ≤ t < ∞} is a Kähler Ricci flow solution on a Fano surface. If |Rm| is not uniformly bounded along this flow, we can blowup at the maximal curvature points to obtain a limit complete Riemannian manifold X. We show that X must have certain topological and geometric properties. Using these properties, we are able to prove that |Rm| is uniformly bounded along every Kähler Ricci flow on toric Fano surface, whose initial metric has toric symmetry. In particular, such a Kähler Ricci flow must converge to a Kähler Ricci soliton metric. Therefore we give a new Ricci flow proof of the existence of Kähler Ricci soliton metrics on toric Fano surfaces.