Convexity properties of gradient maps

We consider the action of a real reductive group G on a Kähler manifold Z which is the restriction of a holomorphic action of a complex reductive group H. We assume that the action of a maximal compact subgroup U of H is Hamiltonian and that G is compatible with a Cartan decomposition of H. We have an associated gradient map μp:Z→p where g=k⊕p is the Cartan decomposition of g. For a G-stable subset Y of Z we consider convexity properties of the intersection of μp(Y) with a closed Weyl chamber in a maximal abelian subspace a of p. Our main result is a Convexity Theorem for real semi-algebraic subsets Y of Z=P(V) where V is a unitary representation of U.     

Spectral shift function and resonances for slowly varying perturbations of periodic Schrödinger operators

We study the spectral shift function s(λ,h) and the resonances of the operator P(h)=-Δ+V(x)+W(hx). Here V is a periodic potential, W a decreasing perturbation and h a small positive constant. We give a representation of the derivative of s(λ,h) related to the resonances of P(h), and we obtain a Weyl-type asymptotics of s(λ,h). We establish an upper bound O(h^-n+1) for the number of the resonances of P(h) lying in a disk of radius h.     

A conjugated version of the countable dense homogeneity

We are interested in finding a homeomorphism h of a space X with h⁻¹○Φ○h(A)=B for a given bijection Φ of X and every pair of countable dense subsets A and B of X. For a separable Banach space X, such a homeomorphism h always exists provided the fixed-point set of Φ has the empty interior. Moreover, h can be chosen to be real-analytic. As a consequence, there exists a real analytic flow that sends A onto B after time t=1. Actually, for X=Rn, any bounded real-analytic vector field can be approximated by a real-analytic vector field whose induced flow sends A onto B after time t=1. Topological and Cp smooth counterparts of these results are also obtained.     

Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a König-Egerváry graph provided α(G)+μ(G)=|V(G)| [R.W. Deming, Independence numbers of graphs—an extension of the König-Egerváry theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G,Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Ψ(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S∈Ψ(G), the subgraph spanned by S∪N(S) is a König-Egerváry graph.     

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

Newtonian and Schinzel sequences in a domain

A Schinzel or F sequence in a domain is such that, for every ideal I with norm q, its first q terms form a system of representatives modulo I, and a Newton or N sequence such that the first q terms serve as a test set for integer-valued polynomials of degree less than q. Strong F and strong N sequences are such that one can use any set of q consecutive terms, not only the first ones, finally a very well F ordered sequence, for short, a V.W.F sequence, is such that, for each ideal I with norm q, and each integer s,{u_sq,…,u_(s+1)q−1} is a complete set of representatives modulo I. In a quasilocal domain, V.W.F sequences and N sequences are the same, so are strong F and strong N sequences. Our main result is that a strong N sequence is a sequence which is locally a strong F sequence, and an N sequence a sequence which is locally a V.W.F. sequence. We show that, for F sequences there is a bound on the number of ideals of a given norm. In particular, a sequence is a strong F sequence if and only if it is a strong N sequence and for each prime p, there is at most one prime ideal with finite residue field of characteristic p. All results are refined to sequences of finite length.     

Connected domination of regular graphs

A dominating setD of a graph G is a subset of V(G) such that for every vertex v∈V(G), either v∈D or there exists a vertex u∈D that is adjacent to v in G. Dominating sets of small cardinality are of interest. A connected dominating setC of a graph G is a dominating set of G such that the subgraph induced by the vertices of C in G is connected. A weakly-connected dominating setW of a graph G is a dominating set of G such that the subgraph consisting of V(G) and all edges incident with vertices in W is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs.     

Topological-algebraic properties of function spaces with set-open topologies

For a Tychonoff space X, we denote by Cλ(X) the space of all real-valued continuous functions on X with set-open topology. In this paper, we study the topological-algebraic properties of Cλ(X). Our main results state that (1) Cλ(X) is a topological vector space (a topological group) iff λ is a family of C-compact sets and Cλ(X)=Cλ^′(X), where λ^′ consists of all C-compact subsets of every set of λ. In particular, if Cλ(X) is a topological group, then the set-open topology coincides with the topology of uniform convergence on a family λ; (2) a topological group Cλ(X) is ω-narrow iff λ is a family of metrizable compact subsets of X.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

Unital and multiplicatively spectrum-preserving surjections between semi-simple commutative Banach algebras are linear and multiplicative

Let T be a surjective map from a unital semi-simple commutative Banach algebra A onto a unital commutative Banach algebra B. Suppose that T preserves the unit element and the spectrum σ(fg) of the product of any two elements f and g in A coincides with the spectrum σ(TfTg). Then B is semi-simple and T is an isomorphism. The condition that T is surjective is essential: An example of a non-linear and non-multiplicative unital map from a commutative C*-algebra into itself such that σ(TfTg)=σ(fg) holds for every f,g are given. We also show an example of a surjective unital map from a commutative C*-algebra onto itself which is neither linear nor multiplicative such that σ(TfTg)⊂σ(fg) holds for every f,g.