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.     

( m,n)-Equidista nt Sets i n $\ mathbb{R}^{k},\ mathbb{S}^{k}$ , a nd ℙk

We call a metric space X (m,n)-equidistant if, when A⊆X has exactly m points, there are exactly n points in X each of which is equidistant from (the points of) A. We prove that, for k≥2, the Euclidean space ℝ ^k contains an (m,1)-equidistant set if and only if k≥m. Although the sphere is (3,2)-equidistant, and ℝ⁴ contain no (4,2)-equidistant sets. We discuss related results about projective spaces, and state a conjecture about analogous to the Double Midset Conjecture.     

Liftings for Haar measure on {0,1} k

We callE ⊆ {0,1} ^k projective if for some countableA ⊆κ there is anE _A ⊆ {0, 1} ^A such thatE=E _A ×{0,1} ^k\A andE _A is a projective subset of the Cantor set {0, 1} ^A . We construct a model where Haar measure on {0,1} ^k has no projective lifting (and in particular no Baire lifting) for anyκ≥ω. Research partially supported by NATO Science Fellowship. The first author would like to thank the Mathematics Department at the University of Essex for its hospitality during the academic year 1988/89 while part of this research was being carried out. This research was initiated while the second author was a postdoctoral fellow at the University of Toronto. Its completion was supported by NSF grant DMS-8505550.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

Alliance free and alliance cover sets

A defensive (offensive) k-alliance in Γ = (V,E) is a set S ⊆ V such that every υ in S (in the boundary of S) has at least k more neighbors in S than it has in V / S. A set X ⊆ V is defensive (offensive) k-alliance free, if for all defensive (offensive) k-alliance S, S/X ≠ ∅, i.e., X does not contain any defensive (offensive) k-alliance as a subset. A set Y ⊆ V is a defensive (offensive) k-alliance cover, if for all defensive (offensive) k-alliance S, S ∩ Y ≠ ∅, i.e., Y contains at least one vertex from each defensive (offensive) k-alliance of Γ. In this paper we show several mathematical properties of defensive (offensive) k-alliance free sets and defensive (offensive) k-alliance cover sets, including tight bounds on their cardinality.     

Equivalence of quotient Hilbert modules

LetM be a Hilbert module of holomorphic functions over a natural function algebraA(Ω), where Ω ⊆ ℂ ^m is a bounded domain. LetM ₀ ⊆M be the submodule of functions vanishing to orderk on a hypersurfaceZ ⊆ Ω. We describe a method, which in principle may be used, to construct a set of complete unitary invariants for quotient modulesQ =M ⊖M ₀ The invariants are given explicitly in the particular case ofk = 2.     

A revised closed graph theorem for quasi-Suslin spaces

Some results about the continuity of special linear maps between F-spaces recently obtained by Drewnowski have motivated us to revise a closed graph theorem for quasi-Suslin spaces due to Valdivia. We extend Valdivia’s theorem by showing that a linear map with closed graph from a Baire tvs into a tvs admitting a relatively countably compact resolution is continuous. This also applies to extend a result of De Wilde and Sunyach. A topological space X is said to have a (relatively countably) compact resolution if X admits a covering {A _α :α ∈ ℕ^ℕ} consisting of (relatively countably) compact sets such that A _α ⊆ A _β for α ⩽ β. Some applications and two open questions are provided.     

An Improvement to “A Note on Euclidean Ramsey Theory”

We characterize those subsets Y⊆ℝ ⁿ such that for every infinite X⊆ℝ ⁿ , there is a red/blue coloring of ℝ ⁿ having no monochromatic red set similar to X and no monochramtic blue set similar to Y.     

A covering lemma for L(ℝ)

Jensen's celebrated Covering Lemma states that if 0^# does not exist, then for any uncountable set of ordinals X, there is a Y∈L such that X⊆Y and |X| = |Y|. Working in ZF + AD alone, we establish the following analog: If ℝ^# does not exist, then L(ℝ) and V have exactly the same sets of reals and for any set of ordinals X with |X| ≥Θ ^{L (ℝ)}, there is a Y∈L(ℝ) such that X⊆Y and |X| = |Y|. Here ℝ is the set of reals and Θ is the supremum of the ordinals which are the surjective image of ℝ. Received: 29 October 1999 / Published online: 12 December 2001     

Vector bundles as direct images of line bundles

LetX be a smooth irreducible projective variety over an algebraically closed fieldK andE a vector bundle onX. We prove that, if dimX ≥ 1, there exist a smooth irreducible projective varietyZ overK, a surjective separable morphismf:Z →X which is finite outside an algebraic subset of codimension ≥ 3 inX and a line bundleL onX such that the direct image ofL byf is isomorphic toE. WhenX is a curve, we show thatZ, f, L can be so chosen thatf is finite and the canonical mapH ¹(Z, O) →H ¹(X, EndE) is surjective. Dedicated to the memory of Professor K G Ramanathan     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Varieties for Modules of Quantum Elementary Abelian Groups

We define a rank variety for a module of a noncocommutative Hopf algebra A = L \rtimes GA = \Lambda \rtimes G where L = k[X₁, ..., X_m]/(X₁^l, ..., X_m^l), G = (\mathbbZ/l\mathbbZ)^m\Lambda = k[X_1, \dots, X_m]/(X_1^{\ell}, \dots, X_m^{\ell}), G = (\mathbb{Z}/\ell\mathbb{Z})^m and char k does not divide ℓ, in terms of certain subalgebras of A playing the role of “cyclic shifted subgroups”. We show that the rank variety of a finitely generated module M is homeomorphic to the support variety of M defined in terms of the action of the cohomology algebra of A. As an application we derive a theory of rank varieties for the algebra Λ. When ℓ=2, rank varieties for Λ-modules were constructed by Erdmann and Holloway using the representation theory of the Clifford algebra. We show that the rank varieties we obtain for Λ-modules coincide with those of Erdmann and Holloway.     

Moments of randomly stopped sums-revisited

Conditions are obtained for (*)E|S _T |^γ<∞, γ>2 whereT is a stopping time and {S _n=∑ ₁ ⁿ ,X _j ℱ _n ,n⩾1} is a martingale and these ensure when (**)X _n ,n≥1 are independent, mean zero random variables that (*) holds wheneverET ^γ/2<∞, sup _n≥1 E|X _n |^γ<∞. This, in turn, is applied to obtain conditions for the validity ofE|S _k,T |^γ<∞ and of the second moment equationES _k,T ² =σ ² EΣ _j=k ^T S _k−1,j−1 ² where and {X _n , n≥1} satisfies (**) and ,n≥1. The latter is utilized to elicit information about a moment of a stopping rule. It is also shown for i.i.d. {X _n , n≥1} withEX=0,EX ²=1 that the a.s. limit set of {(n log logn)^−k/2 S _k,n ,n≥k} is [0,2 ^k/2/k!] or [−2 ^k/2/k!] according ask is even or odd and this can readily be reformulated in terms of the corresponding (degenerate kernel)U-statistic .     

Moment convergence rates in the law of the logarithm for dependent sequences

Let {X _n ; n ≥ 1} be a strictly stationary sequence of negatively associated random variables with mean zero and finite variance. Set S _n = Σ _k=1 ⁿ X _k , M _n = max _k≤n |S _k |, n ≥ 1. Suppose σ ² = EX ₁² + 2Σ _k=2^∞ EX ₁ X _k (0 < σ < ∞). In this paper, the exact convergence rates of a kind of weighted infinite series of E{M _n −σɛ√n log n}₊ and E{|S _n | − σɛ√n log n}₊ as ɛ ↘ 0 and E{σɛ√π ² π/8logn − M _n }₊ as ɛ ↗ ∞ are obtained.     

Rigidity for pseudo pretheories

Assume F is a homotopy invariant pseudo pretheory with torsion values and X is a smooth scheme of finite type over a field k. We show for certain field extensions k⊆K the map F(X)→F(X _K ) is an isomorphism. Mathematics Subject Classification (2000) 14A99     

On the classification of bases in <Emphasis Type="Italic">P</Emphasis><Subscript>k</Subscript> according to the decidability of the completeness problem for automata

The completeness problem for bases of the form Φ ∪ ν, where Φ ⊆ P _k and ν is a finite system of automaton functions, is considered. Previously, the problem for k = 2 was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system Φ∪ν when [Φ] = Pk. The paper is concerned with the case where [Φ] is the maximal (precomplete) class in P _k . The problem of completeness for systems Φ ∪ ν is shown to be undecidable if Φ is embedded in a Slupecki class and algorithmically decidable if Φ contains the class preserving all constants. Thus, the bases in P _k , k ≥ 3, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.     

NON-EMPTY CROSS-2-INTERSECTING FAMILIES OF SUBSETS

Let Cdenote the set of all k-subests of an n-set.Assume Alohtain in Ca,and A lohtain in (A,B) is called a cross-2-intersecting family if |A B≥2 for and A∈A,B∈B.In this paper,the best upper bounds of the cardinalities for non-empty cross-2-intersecting familles of a-and b-subsets are obtained for some a and b,A new proof for a Frankl-Tokushige theorem[6] is also given.     

The structure on the real field generated by the standard part map on an o-minimal expansion of a real closed field

Let R be a sufficiently saturated o-minimal expansion of a real closed field, let be the convex hull of ℚ in R, and let st: → ℝ ⁿ be the standard part map. For X ⊆ R ⁿ define st X:= st (X ∩ ). We let ℝ_ind be the structure with underlying set ℝ and expanded by all sets st X, where X ⊆ R ⁿ is definable in R and n = 1, 2,.... We show that the subsets of ℝ ⁿ that are definable in ℝ_ind are exactly the finite unions of sets st X st Y, where X, Y ⊆ R ⁿ are definable in R. A consequence of the proof is a partial answer to a question by Hrushovski, Peterzil and Pillay about the existence of measures with certain invariance properties on the lattice of bounded definable sets in R ⁿ .     

Convex decompositions in the plane and continuous pair colorings of the irrationals

We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ² which is not presentable as a countable union of convex sets satisfies the following dichotomy:

Waldhausen's theory of k-fold end structures: a survey

Let R⁺ be the space of nonnegative real numbers. F. Waldhausen defines a k-fold end structure on a space X as an ordered k-tuple of continuous maps x_f:X → R⁺, 1 ? j ? k, yielding a proper map x:X → (R⁺)^k. The pairs (X,x) are made into the category E^k of spaces with k-fold end structure. Attachments and expansions in E^k are defined by induction on k, where elementary attachments and expansions in E⁰ have their usual meaning. The category E^k/Z consists of objects (X, i) where i: Z → X is an inclusion in E^k with an attachment of i(Z) to X, and the category E^k6Z consists of pairs (X,i) of E^k/Z that admit retractions X → Z. An infinite complex over Z is a sequence X = {X₁ ? X₂ ? … ? X_n …} of inclusions in E^k6Z. The abelian grou p S₀(Z) is then defined as the set of equivalence classes of infinite complexes dominated by finite ones, where the equivalence relation is generated by homotopy equivalence and finite attachment; and the abelian group S₁(Z) is defined as the set of equivalence classes of X₁, where X ∈ E^k/Z deformation retracts to Z. The group operations are gluing over Z. This paper presents the Waldhausen theory with some additions and in particular the proof of Waldhausen's proposition that there exists a natural exact sequence 0 → S₁(Z × R)→^πS₀(Z) by utilizing methods of L.C. Siebenmann. Waldhausen developed this theory while seeking to prove the topological invariance of Whitehead torsion; however, the end structures also have application in studying the splitting of a noncompact manifold as a product with R[1].