Derivations into duals of ideals of Banach algebras

We introduce two notions of amenability for a Banach algebra A. LetI be a closed two-sided ideal inA, we sayA is I-weakly amenable if the first cohomology group ofA with coefficients in the dual space I* is zero; i.e.,H ¹(A, I*) = {0}, and,A is ideally amenable ifA isI-weakly amenable for every closed two-sided idealI inA. We relate these concepts to weak amenability of Banach algebras. We also show that ideal amenability is different from amenability and weak amenability. We study theI-weak amenability of a Banach algebraA for some special closed two-sided idealI.     

Minimum Degree Conditions for Cycles Including Specified Sets of Vertices

This paper generalises the concept of vertex pancyclic graphs. We define a graph as set-pancyclic if for every set S of vertices there is a cycle of every possible length containing S. We show that if the minimum degree of a graph exceeds half its order then the graph is set-pancyclic. We define a graph as k-ordered-pancyclic if, for every set S of cardinality k and every cyclic ordering of S, there is for every possible length a cycle of that length containing S and encountering S in the specified order. We determine the best possible minimum-degree condition which guarantees that a graph is k-ordered-pancyclic.     

Weak subintegral closure of ideals

We describe some basic facts about the weak subintegral closure of ideals in both the algebraic and complex-analytic settings. We focus on the analogy between results on the integral closure of ideals and modules and the weak subintegral closure of an ideal. We start by giving a new geometric interpretation of the Reid–Roberts–Singh criterion for when an element is weakly subintegral over a subring. We give new characterizations of the weak subintegral closure of an ideal. We associate with an ideal I of a ring A an ideal I_>, which consists of all elements of A such that v(a)>v(I), for all Rees valuations v of I. The ideal I_> plays an important role in conditions from stratification theory such as Whitney's condition A and Thom's condition Af and is contained in every reduction of I. We close with a valuative criterion for when an element is in the weak subintegral closure of an ideal. For this, we introduce a new closure operation for a pair of modules, which we call relative weak closure. We illustrate the usefulness of our valuative criterion.     

Interpolation properties in the extensions of the logic of inequality

We consider the modal logics wK4 and DL as well as the corresponding weakly transitive modal algebras and DL-algebras. We prove that there exist precisely 16 amalgamable varieties of DL-algebras. We find a criterion for the weak amalgamation property of varieties of weakly transitive modal algebras, solve the deductive interpolation problem for extensions of the logic of inequality DL, and obtain a weak interpolation criterion over wK4.     

Controllability properties of constrained linear systems

In this paper, we present results on constrained controllability for linear control systems. The controls are constrained to take values in a compact set containing the origin. We use the results on reachability properties discussed in Ref. 1.We prove that controllability of an arbitrary pointp inR ⁿ is equivalent to an inclusion property of the reachable sets at certain positive times. We also develop geometric properties ofG, the set of all nonnegative times at whichp is controllable, and ofC, the set of all controllable points. We characterize the setC for the given system and provide additional spectrum-dependent structure.We show that, for the given linear system, several notions of constrained controllability of the pointp are the same, and thus the setC is open. We also provide a necessary condition for small-time (differential or local) constrained controllability ofp.This work was supported in part by NSF Grant ECS-86-09586.     

Existence and uniqueness of an invariant probability for a class of Feller Markov chains

We consider the class of Feller Markov chains on a phase spaceX whose kernels mapC ₀ (X), the space of bounded continuous functions that vanish at infinity, into itself. We provide a necessaryand sufficient condition for the existence of an invariant probability measure using a generalized Farkas Lemma. This condition is a Lyapunov type criterion that can be checked in practice. We also provide a necessaryand sufficient condition for existence of aunique invariant probability measure. When the spaceX is compact, the conditions simplify.     

On properties of <Emphasis Type="Italic">G</Emphasis>-expansive homeomorphisms

We show that LUB of the set of G-expansive constants for a G-expansive homeomorphism h on a compact metric G-space, G compact, is not a G-expansive constant for h. We obtain a result regarding projecting and lifting of G-expansive homeomorphisms having interesting applications. We also prove that the G-expansiveness is a dynamical property for homeomorphisms on compact metric G-spaces and study G-periodic points.     

Semicharacters of Groups

We define the notion of a semicharacter of a group G: A function from the group to ?*, whose restriction to any abelian subgroup is a homomorphism. We conjecture that for any finite group, the order of the group of semicharacters is divisible by the order of the group. We prove that the conjecture holds for some important families of groups, including the Symmetric groups and the groups GL(2, q).     

Growth of Rank 1 Valuation Semigroups

We consider semigroup S of a rank 1 valuation ? centered on a local ring R. We show that the Hilbert polynomial of R gives a bound on the growth of the valuation semigroup S. This allows us to give a very simple example of a well ordered subsemigroup of Q+, which is not a value semigroup of a local domain. We also consider the rates of growth which are possible for S. We show that quite exotic behavior can occur. In the final section, we consider the general question of characterizing rank 1 value semigroups.     

Bounds on Pairs of Families with Restricted Intersections

such that for any , . We are interested in the maximum product , given r and L. We give asymptotically optimal bounds for L containing only elements of s<q residue classes modulo q, where q is arbitrary (even non-prime) and s is a constant. As a consequence, we obtain a version of the Frankl–R?dl result about forbidden intersections for the case of two forbidden intersections. We also give tight bounds for L={0,...,k}. Received: August 5, 1998     

An introduction to presentations of monoid acts: quotients and subacts

The purpose of this article is to introduce the theory of presentations of monoids acts. We aim to construct “nice” general presentations for various act constructions pertaining to subacts and Rees quotients. More precisely, given an M-act A and a subact B of A, on the one hand, we construct presentations for B and the Rees quotient A/B using a presentation for A, and on the other hand, we derive a presentation for A from presentations for B and A/B. We also construct a general presentation for the union of two subacts. From our general presentations, we deduce a number of finite presentability results. Finally, we consider the case where a subact B has a finite complement in an M-act A. We show that if M is a finitely generated monoid and B is finitely presented, then A is finitely presented. We also show that if M belongs to a wide class of monoids, including all finitely presented monoids, then the converse also holds.     

Finding the Medial Axis of a Simple Polygon in Linear Time

We give a linear-time algorithm for computing the medial axis of a simple polygon P . This answers a long-standing open question—previously, the best deterministic algorithm ran in O(n log n) time. We decompose P into pseudonormal histograms, then influence histograms, then xy monotone histograms. We can compute the medial axes for xy monotone histograms and merge to obtain the medial axis for P . Received May 16, 1997, and in revised form October 30, 1997.     

On the Existence of a Noninner Automorphism of Order p for p-Groups

We obtain sufficient conditions for the existence of a noninner automorphism of order p for finite p-groups. We show that groups of order p ⁿ (n < 7, p is a prime number, p > 3) possess a noninner automorphism of order p.     

A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs

We combinatorially prove that the number R(n, k) of permutations of length n having k runs is a log-concave sequence in k, for all n. We also give a new combinatorial proof for the log-concavity of the Eulerian numbers.     

Extension of multilinear maps defined on subspaces

We study the problem of whether every multilinear form defined on the product of n closed subspaces has an extension defined on the product of the entire Banach spaces. We prove that the property derived from this condition (the Multilinear Extension Property) is local. We use this to prove that, for a wide variety of Banach spaces, there exist a product of closed subspaces and a multilinear form defined on it, which has no extension to the product of the entire spaces. We show that the ℓ _p spaces, with 1 ≤p ≤ ∞ and p ≠ 2, are among them and, more generally, every Banach space which fails to have type p for some p < 2 or cotype q for some q > 2.     

Sections of the Difference Body

Let K be an n -dimensional convex body. Define the difference body by K-K= { x-y | x,y ∈ K }. We estimate the volume of the section of K-K by a linear subspace F via the maximal volume of sections of K parallel to F . We prove that for any m -dimensional subspace F there exists x ∈ \bf R ⁿ , such that for some absolute constant C . We show that for small dimensions of F this estimate is exact up to a multiplicative constant. Received May 6, 1998, and in revised form July 23, 1998.     

Stability and localization of unbounded solutions of a nonlinear heat equation in a plane

The article investigates unbounded solutions of the equation u _t = div (u ^σgrad u) + u ^β in a plane. We numerically analyze the stability of two-dimensional self-similar solutions (structures) that increase with blowup. We confirm structural stability of the simple structure with a single maximum and metastability of complex structures. We prove structural stability of the radially symmetrical structure with a zero region at the center and investigate its attraction region. We study the effect of various perturbations of the initial function on the evolution of self-similar solutions. We further investigate how arbitrary compact-support initial distributions attain the self-similar mode, including distributions whose support is different from a disk. We show that the self-similar mode described by a simple radially symmetrical structure is achieved only in the central region, while the entire localization region does not have enough time to transform into a disk during blowup. We show for the first time that simple structures may merge into a complex structure, which evolves for a long time according to self-similar law.     

Characterization of semicontinuity of solutions to abstract optimization problems

Abstract

We develop a theory of best simultaneous approximations for closed downward sets in a conditionally complete lattice Banach space X with a strong unit. We study best simultaneous approximation in X by elements of downward and normal sets, and give necessary and sufficient conditions for any element of best simultaneous approximation by a closed subset of X. We prove that a downward subset of X is strictly downward if and only if each its boundary point is simultaneous Chebyshev.     

The images of Lie polynomials evaluated on matrices

Kaplansky asked about the possible images of a polynomial f in several noncommuting variables. In this paper, we consider the case of f a Lie polynomial. We describe all the possible images of f in M₂(K) and provide an example of f whose image is the set of non-nilpotent trace zero matrices, together with 0. We provide an arithmetic criterion for this case. We also show that the standard polynomial s_k is not a Lie polynomial, for k>2.     

Space complexity of random formulae in resolution

We study the space complexity of refuting unsatisfiable random k-CNFs in the Resolution proof system. We prove that for Δ ≥ 1 and any ϵ > 0, with high probability a random k-CNF over n variables and Δn clauses requires resolution clause space of Ω(n/Δ^1+ϵ). For constant Δ, this gives us linear, optimal, lower bounds on the clause space. One consequence of this lower bound is the first lower bound for size of treelike resolution refutations of random 3-CNFs with clause density Δ ≫ n. This bound is nearly tight. Specifically, we show that with high probability, a random 3-CNF with Δn clauses requires treelike refutation size of exp(Ω(n/Δ^1+ϵ)), for any ϵ > 0. Our space lower bound is the consequence of three main contributions: (1) We introduce a 2-player Matching Game on bipartite graphs G to prove that there are no perfect matchings in G. (2) We reduce lower bounds for the clause space of a formula F in Resolution to lower bounds for the complexity of the game played on the bipartite graph G(F) associated with F. (3) We prove that the complexity of the game is large whenever G is an expander graph. Finally, a simple probabilistic analysis shows that for a random formula F, with high probability G(F) is an expander. We also extend our result to the case of G-PHP, a generalization of the Pigeonhole principle based on bipartite graphs G. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 92–109, 2003