Maximum-cover source location problems with objective edge-connectivity three

Given a graph G = (V, E), a set of vertices covers a vertex if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k.     

Uniform Mixed Hypergraphs: The Possible Numbers of Colors

For a mixed hypergraph , where and are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every meets some class in more than one vertex, and every has a nonempty intersection with at least two classes. The feasible set of , denoted , is the set of integers k such that admits a coloring with precisely k nonempty color classes. It was proved by Jiang et al. [Graphs and Combinatorics 18 (2002), 309–318] that a set S of natural numbers is the feasible set of some mixed hypergraph if and only if either or S is an ‘interval’ for some integer k ≥ 1. In this note we consider r-uniform mixed hypergraphs, i.e. those with |C| = |D| = r for all and all , r ≥ 3. We prove that S is the feasible set of some r-uniform mixed hypergraph with at least one edge if and only if either for some natural number k ≥ r − 1, or S is of the form where S′′ is any (possibly empty) subset of and S′ is either the empty set or {r − 1} or an ‘interval’ {k, k + 1, ..., r − 1} for some k, 2 ≤ k ≤ r − 2. We also prove that all these feasible sets can be obtained under the restriction , i.e. within the class of ‘bi-hypergraphs’. Research supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613.     

Hypersurfaces of restricted type in Minkowski space

A submanifold M _n ^r of Minkowski space is said to be of restricted type if its shape operator with respect to the mean curvature vector is the restriction of a fixed linear transformation of to the tangent space of M _n ^r at every point of M _n ^r . In this paper we completely classify hypersurfaces of restricted type in . More precisely, we prove that a hypersurface of is of restricted type if and only if it is either a minimal hypersurface, or an open part of one of the following hypersurfaces: S ^k × , S _k ¹ × , H ^k × , S _n ¹ , H ⁿ , with 1kn–1, or an open part of a cylinder on a plane curve of restricted type.This work was done when the first and fourth authors were visiting Michigan State University.Aangesteld Navorser N.F.W.O., Belgium.     

On Some Properties of Randomly Indexed Sequences of Random Elements

Let be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N _n ,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F _k ,k≥1} be a family of probability laws and let X be some random element defined on and taking values in (S,ρ). In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X _n,k ,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that , and moreover as  n→∞. Furthermore, we consider the speed of convergence to X as n→∞.      

Subdirectly irreducible \mathcal{RGC} -commutative right H-semigroups

A semigroup S is said to be ℛ-commutative if, for all elements a,b∈S, there is an element x∈S ¹ such that ab=bax. A semigroup S is called a generalized conditionally commutative (briefly, -commutative) semigroup if it satisfies the identity aba ²=a ² ba. An ℛ-commutative and -commutative semigroup is called an -commutative semigroup. A semigroup S is said to be a right H-semigroup if every right congruence of S is a congruence of S. In this paper we characterize the subdirectly irreducible semigroups in the class of -commutative right H-semigroups. Research supported by the Hungarian NFSR grant No T029525.     

Convex Sets in Acyclic Digraphs

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with and . We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n − k + 1. This is a strengthening of a theorem of Gutin and Yeo.     

Families of planar sets having starlike union

Let be a finite family of compact sets in the plane, and letk be a fixed natural number. If every three (not necessarily distinct) members of have a union which is simply connected and starshaped viak-paths, then and is starshaped viak-paths. Analogous results hold for paths of length at most , > 0, and for staircase paths, although not for staircasek-paths.Supported in part by NSF grant DMS-9504249     

On Sums of Products of Bernoulli Variables and Random Permutations

Let {X _k } _k1 be independent Bernoulli random variables with parameters p _k . We study the distribution of the number or runs of length 2: that is . Let S=lim _n S _n . For the particular case p _k =1/(k+B), B being given, we show that the distribution of S is a Beta mixture of Poisson distributions. When B=0 this is a Poisson(1) distribution. For the particular case p _k =p for all k we obtain the generating function of S _n and the limiting distribution of S _n for .     

Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time

For any ℓ>0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P ₁≤0,…,P _s ≤0, where each P _i ∈R[X ₁,…,X _k ] has degree≤2, and computes the top ℓ Betti numbers of S, b _k−1(S),…,b _k−ℓ (S), in polynomial time. The complexity of the algorithm, stated more precisely, is . For fixed ℓ, the complexity of the algorithm can be expressed as , which is polynomial in the input parameters s and k. To our knowledge this is the first polynomial time algorithm for computing nontrivial topological invariants of semialgebraic sets in R ^k defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed s, we obtain, by letting ℓ=k, an algorithm for computing all the Betti numbers of S whose complexity is . An erratum to this article can be found at     

Module Arens regularity for semigroup algebras

We extend the concept of Arens regularity of a Banach algebra to the case that there is an -module structure on , and show that when S is an inverse semigroup with totally ordered subsemigroup E of idempotents, then A=ℓ ¹(S) is module Arens regular if and only if an appropriate group homomorphic image of S is finite. When S is a discrete group, this is just Young’s theorem which asserts that ℓ ¹(S) is Arens regular if and only if S is finite. An erratum to this article can be found at     

On Positive Sasakian Geometry

A Sasakian structure =(\xi,\eta,\Phi,g) on a manifold Mis called positiveif its basic first Chern class c₁( ) can be represented by a positive (1,1)-form with respect to its transverse holomorphic CR-structure. We prove a theorem that says that every positive Sasakian structure can be deformed to a Sasakian structure whose metric has positive Ricci curvature. This provides us with a new technique for proving the existence of positive Ricci curvature metrics on certain odd dimensional manifolds. As an example we give a completely independent proof of a result of Sha and Yang that for every nonnegative integer kthe 5-manifolds k#(S ²×S ³) admits metrics of positive Ricci curvature.     

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then , while if k is odd, then . We show that both bounds are tight. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

On zero-sum sequences of prescribed length

Summary. Let k ≥ 1 be any integer. Let G be a finite abelian group of exponent n. Let s_k(G) be the smallest positive integer t such that every sequence S in G of length at least t has a zero-sum subsequence of length kn. We study this constant for groups when d = 3 or 4. In particular, we prove, as a main result, that for every k ≥ 4, and for every prime p ≥ 5.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

On a connection between the existence ofk-trees and the toughness of a graph

A graphG has toughnesst(G) ift(G) is the largest numbert such that for any subsetS of the vertices ofG, the number of vertices inS is at leastt times the number of components ofG on deletion of the vertices inS, provided that there is then more than one component. Ak-tree of a connected graph is a spanning tree with maximum degree at mostk. We show here that if , withk 3, thenG has ak-tree. The notion of ak-tree generalizes the casek = 2 of a hamiltonian path, so that this result, as we discuss, may be of some interest in connection with Chvátal's conjecture that, for somet, every graph with toughness at leastt is hamiltonian.     

Decomposing <Emphasis Type="Italic">k</Emphasis>-ARc-Strong Tournaments Into Strong Spanning Subdigraphs

  The so-called Kelly conjecture states that every regular tournament on 2k+1 vertices has a decomposition into k-arc-disjoint hamiltonian cycles. In this paper we formulate a generalization of that conjecture, namely we conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. We prove several results which support the conjecture:If D = (V, A) is a 2-arc-strong semicomplete digraph then it contains 2 arc-disjoint spanning strong subdigraphs except for one digraph on 4 vertices.Every tournament which has a non-trivial cut (both sides containing at least 2 vertices) with precisely k arcs in one direction contains k arc-disjoint spanning strong subdigraphs. In fact this result holds even for semicomplete digraphs with one exception on 4 vertices.Every k-arc-strong tournament with minimum in- and out-degree at least 37k contains k arc-disjoint spanning subdigraphs H ₁, H ₂, . . . , H _k such that each H _i is strongly connected.The last result implies that if T is a 74k-arc-strong tournament with speci.ed not necessarily distinct vertices u ₁, u ₂, . . . , u _k , v ₁, v ₂, . . . , v _k then T contains 2k arc-disjoint branchings where is an in-branching rooted at the vertex u _i and is an out-branching rooted at the vertex v _i , i=1,2, . . . , k. This solves a conjecture of Bang-Jensen and Gutin [3].We also discuss related problems and conjectures.

Selmer groups of abelian varieties in extensions of function fields

Let k be a field of characteristic q, a smooth geometrically connected curve defined over k with function field . Let A/K be a non-constant abelian variety defined over K of dimension d. We assume that q = 0 or >  2d + 1. Let p ≠ q be a prime number and a finite geometrically Galois and étale cover defined over k with function field . Let (τ′, B′) be the K′/k-trace of A/K. We give an upper bound for the -corank of the Selmer group Sel _p (A × _K K′), defined in terms of the p-descent map. As a consequence, we get an upper bound for the -rank of the Lang–Néron group A(K′)/τ′B′(k). In the case of a geometric tower of curves whose Galois group is isomorphic to , we give sufficient conditions for the Lang–Néron group of A to be uniformly bounded along the tower. This work was partially supported by CNPq research grant 305731/2006-8.     

Monotone Solutions of a Higher-Order Neutral Difference Equation

A real sequence x _k is said to be (*)-monotone with respect to a sequence p _k and a positive integer if x _k > 0 and . This paper is concerned with the existence of (*)-monotone solutions of a neutral difference equation. Existence criteria are derived by means of a comparison theorem and by establishing explicit existence criteria for positive and/or bounded solutions of a majorant recurrence relation.     

Restriction De La Cohomologie D’une Variété De Shimura à Ses Sous-variétés

Let G be a connected semisimple group over . Given a maximal compact subgroup K ⊂ G() such that X = G()/K is a Hermitian symmetric domain, and a convenient arithmetic subgroup Γ ⊂ G(), one constructs a (connected) Shimura variety S = S(Γ) = Γ\X. If H ⊂ G is a connected semisimple subgroup such that H() / K is maximal compact, then Y = H()/K is a Hermitian symmetric subdomain of X. For each g ∈ G() one can construct a connected Shimura variety S(H, g) = (H() ∩ g ⁻¹Γg)\Y and a natural holomorphic map j _g : S(H, g) → S induced by the map H() → G(), h → gh. Let us assume that G is anisotropic, which implies that S and S(H, g) are compact. Then, for each positive integer k, the map j _g induces a restriction map

On the Homological Dimension of Lattices

Let L be a finite lattice and let . It is shown that if the order complex satisfies then |L| ≥ 2 ^k . Equality |L| = 2 ^k holds iff L is isomorphic to the Boolean lattice {0,1} ^k . Research supported by the Israel Science Foundation.