A geometry characteristic of Banach spaces with c 1-norm

Let E be a Banach space with the cl-norm｜｜·｜｜ in E／{0}, and let S（E） = {e ∈ E： ｜｜e｜｜ = 1}. In this paper, a geometry characteristic for E is presented by using a geometrical construct of S（E）. That is, the following theorem holds： the norm of E is of eI in E／{0} if and only if S（E） is a c1 submanifold of E, with codimS（E） = 1. The theorem is very clear, however, its proof is non-trivial, which shows an intrinsic connection between the continuous differentiability of the norm ｜｜·｜｜ in E／{0} and differential structure of S（E）.     

Searching for an edge in a graph with restricted test sets

Consider the (2,n) group testing problem with test sets of cardinality at most 2. We determine the worst case number c₂ of tests for this restricted group testing problem.Furthermore, using a game theory approach we solve the generalization of this group testing problem to the following search problem, which was suggested by Aigner in [M. Aigner, Combinatorial Search, Wiley-Teubner, 1988]: Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with |X|≤2. What is the minimum number c₂(G) of questions, which are needed in the worst case to identify e?We derive sharp upper and lower bounds for c₂(G). We also show that the determination of c₂(G) is an NP-complete problem. Moreover, we establish some results on c₂ for random graphs.     

Complexity of the pipeline computation of a family of inner products

We are interested in the minimum time T(S) necessary for computing a family S = { < S_i, S_j >: ? S_i, S_j?R^p, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.     

Homological properties of modules over semigroup algebras

Let S be a semigroup. In this paper we investigate the injectivity of ?¹(S) as a Banach right module over ?¹(S). For weakly cancellative S this is the same as studying the flatness of the predual left module c₀(S). For such semigroups S, we also investigate the projectivity of c₀(S). We prove that for many semigroups S for which the Banach algebra ?¹(S) is non-amenable, the ?¹(S)-module ?¹(S) is not injective. The main result about the projectivity of c₀(S) states that for a weakly cancellative inverse semigroup S, c₀(S) is projective if and only if S is finite.     

Improving multicut in directed trees by upgrading nodes

In this paper, we consider the network improvement problem for multicut by upgrading nodes in a directed tree T = (V, E) with multiple sources and multiple terminals. In a node based upgrading model, a node v can be upgraded at the expense of c(v) and such an upgrade reduces weights on all edges incident to v. The objective is to upgrade a minimum cost subset S ⊆ V of nodes such that the resulting network has a multicut in which no edge has weight larger than a given value D. We first obtain a minimum cardinality node multicut V_c for tree T, then find the minimum cost upgrading set based on the upgrading sets for the subtrees rooted at the nodes in V_c. We show that our algorithm is polynomial when the number of source–terminal pairs is upper bounded by a given value.     

Value distribution and shared sets of differences of meromorphic functions

We investigate value distribution and uniqueness problems of difference polynomials of meromorphic functions. In particular, we show that for a finite order transcendental meromorphic function f with λ(1/f)<ρ(f) and a non-zero complex constant c, if n?2, then fn(z)f(z+c) assumes every non-zero value a∈C infinitely often. This research also shows that there exist two sets S₁ with 9 (resp. 5) elements and S₂ with 1 element, such that for a finite order nonconstant meromorphic (resp. entire) function f and a non-zero complex constant c, Ef(z)(Sj)=Ef(z+c)(Sj)(j=1,2) imply f(z)≡f(z+c). This gives an answer to a question of Gross concerning a finite order meromorphic function f and its shift.     

Module character amenability of Banach algebras

In this paper we introduce the notion of module character amenable Banach algebras and show that they possess module character virtual (approximate) diagonals. As a basic example, we show that for an inverse semigroup S with the set of idempotents E, the semigroup algebra ? ¹(S) is module character amenable as an ? ¹(E)-module if only if S is amenable.     

Representations for eigenfunctions of expected value operators in the Wishart distribution

Recent articles by Kushner and Meisner (1980) and Kushner, Lebow and Meisner (1981) have posed the problem of characterising the ‘EP’ functions f(S) for which Ef(S) for which E(f(S)) = λ_nf(Σ) for some λ_n ? $\text{R}$, whenever the m × m matrix S has the Wishart distribution W(m, n, Σ). In this article we obtain integral representations for all nonnegative EP functions. It is also shown that any bounded EP function is harmonic, and that EP polynomials may be used to approximate the functions in certain L^p spaces.     

A Hard-Core Model on a Cayley Tree: An Example of a Loss Network

The paper is about a nearest-neighbor hard-core model, with fugacity λ>0, on a homogeneous Cayley tree of order k(with k+1 neighbors). This model arises as as a simple example of a loss network with a nearest-neighbor exclusion. We focus on Gibbs measures for the hard core model, in particular on ‘splitting’ Gibbs measures generating a Markov chain along each path on the tree. In this model, ?λ>0 and k≥1, there exists a unique translation-invariant splitting Gibbs measure μ^*. Define λ_c=1/(k?1)×(k/(k?1)) ^k . Then: (i) for λ≤λ_c, the Gibbs measure is unique (and coincides with the above measure μ^*), (ii) for λ>λ_c, in addition to μ^*, there exist two distinct translation-periodic measures, μ₊and μ_?, taken to each other by the unit space shift. Measures μ₊and μ_?are extreme ?λ>λ_c. We also construct a continuum of distinct, extreme, non-translational-invariant, splitting Gibbs measures. For $\lambda >1/(\sqrt k - 1) \times (\sqrt k /\sqrt k - 1))^k $ , measure μ^*is not extreme (this result can be improved). Finally, we consider a model with two fugacities, λ_eand λ_o, for even and odd sites. We discuss open problems and state several related conjectures.     

Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.     

Analytical relationships between metric and centrality measures of a network and its dual

The centrality and efficiency measures of a network G are strongly related to the respective measures on the dual G^? and the bipartite B(G) associated networks. We show some relationships between the Bonacich centralities c(G), c(G^?) and c(B(G)) and between the efficiencies E(G) and E(G^?) and we compute the behavior of these parameters in some examples.     

Least and most colored bases

Consider a matroid M=(E,B), where B denotes the family of bases of M, and assign a color c(e) to every element e∈E (the same color can go to more than one element). The palette of a subset F of E, denoted by c(F), is the image of F under c. Assume also that colors have prices (in the form of a function π(?), where ? is the label of a color), and define the chromatic price as: π(F)=∑_?∈c(F)π(?). We consider the following problem: find a base B∈B such that π(B) is minimum. We show that the greedy algorithm delivers a lnr(M)-approximation of the unknown optimal value, where r(M) is the rank of matroid M. By means of a reduction from SETCOVER, we prove that the lnr(M) ratio cannot be further improved, even in the special case of partition matroids, unless . The results apply to the special case where M is a graphic matroid and where the prices π(?) are restricted to be all equal. This special case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the ln(n-1)+1 ratio achieved by Wan, Chen and Xu in 2002. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function π(F), where F is a common independent set on matroids M₁,…,M_k and, more generally, to independent systems characterized by the k-for-1 property.     

Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M ⁰, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M ⁰ can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n ³).     

Polynomial and exponential stability for one-dimensional problem in thermoelastic diffusion theory

We consider one-dimensional problem for the thermoelastic diffusion theory and we obtain polynomial decay estimates. Then we show that the solution decays exponentially to zero as time goes to infinity; that is, denoting by E(t) the first-order energy of the system, we show that positive constants C ₀ and c ₀ exist which satisfy E(t) ≤ C ₀ E(0)e ^{?c ₀ t} .     

Exponentially fitted one-step methods for the numerical solution of the scalar Riccati equation

Using stability analysis and information from the constant coefficient problem, we motivate an explicit exponentially fitted one-step method to approximate the solution of a scalar Riccati equation ϵy′ = c(x)y² + d(x)y + e(x), 0 < x ⩽ x, y(0) = y₀, where ϵ > 0 is a small parameter and the coefficients c, d and e are assumed to be real valued and continuous. An explicit Euler-type scheme is presented which, when applied to the numerical integration of the continuous problem, give solutions satisfying a uniform (in ϵ) error estimate with order one (where suitable restrictions are imposed on the coefficients c, d and e together with the choice of y(0)). Using a counterexample, we show that, for a particular class of problems, the solutions of the fitted scheme do not converge uniformly (in ϵ) to the corresponding solutions of the continuous problems. Numerical results are presented which compare the fitted scheme with a number of implicit schemes when applied to the numerical integration of some sample problems.     

Spanning trails containing given edges

A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e^′ and e^″ in E(G), G has a spanning (e^′,e^″)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any X⊆E(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that X⊆E(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.     

Module amenability of the second dual and module topological center of semigroup algebras

In this paper we define the module topological center of the second dual $\mathcal{A}^{**}$ of a Banach algebra $\mathcal{A}$ which is a Banach $\mathfrak{A}$ -module with compatible actions on another Banach algebra $\mathfrak{A}$ . We calculate the module topological center of ? ¹(S)^**, as an ? ¹(E)-module, for an inverse semigroup S with an upward directed set of idempotents E. We also prove that ? ¹(S)^** is ? ¹(E)-module amenable if and only if an appropriate group homomorphic image of S is finite.     

Analytic scattering theory of two-body Schrödinger operators

We consider the self-adjoint analytic family of operators H(z) in L²(R^m) defined for $\text{z ? S}{}_{\mathrm{\alpha }}\text{= {z ∥}\text{Arg}\text{z ¦ < α}}$, associated with the operator H = H(1) = H₀ + V, where H₀ = ?Δ and V is a dilation-analytic short-range potential. The analytic connection between the local wave and scattering operators associated with the operators H(e^i?) is established. The scattering matrix S(?) of H has a meromorphic continuation S(z) to S_α with poles precisely at the resolvent resonances of H, and the local scattering operators of e^?2i?H(e^i?) have representations in terms of the analytically continued scattering matrix S(?e^i?).     

Module derivation problem for inverse semigroups

The derivation problem for a locally compact group G asserts that each bounded derivation from L ¹(G) to L ¹(G) is implemented by an element of M(G). Recently a simple proof of this result was announced. We show that basically the same argument with some extra manipulations with idempotents solves the module derivation problem for inverse semigroups, asserting that for an inverse semigroup S with set of idempotents E and maximal group homomorphic image G _S , if E acts on S trivially from the left and by multiplication from the right, any bounded module derivation from ? ¹(S) to ? ¹(G _S ) is inner.