Additive preservers of non-zero decomposable tensors

Let T be an additive mapping from a tensor product of vector spaces over a field into itself. We describe T for the following two cases: (i) T is surjective and sends non-zero decomposable elements to non-zero decomposable elements, and (ii) T(A) is a non-zero decomposable element if and only if A is a non-zero decomposable element.     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

Roots of almost decomposable operators

The author shows that, for an injective analytic function f, f(T) is almost decomposable iff T is almost decomposable, where T is a bounded linear operator on a Banach space and f(T) is defined by the functional calculus.     

On the shape of decomposable trees

A n-vertex graph is said to be decomposable if, for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. The aim of the paper is to study the homeomorphism classes of decomposable trees. More precisely, we show that homeomorphism classes containing decomposable trees with an arbitrarily large minimal distance between all pairs of distinct vertices of degree different from 2, is exactly the set of combs.     

Lagrangian decomposability of some two-generator subgroups of PU(2,1)

We describe isometry groups of the complex hyperbolic plane generated by two loxodromic motions. We give then a condition for such a group to be decomposable as a group generated by 3 antiholomorphic involutions, and use this decomposition to describe a 3-dimensional ball in the $\mathrm{PU}(2,1)$ Teichmüller space of the once punctured torus. To cite this article: P. Will, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Tournois infinis et critiques

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for every a,b∈X and x∈V?X, (a,x)∈A if and only if (b,x)∈A. For example, ?, {x} (x∈V) and V are intervals of T, called trivial intervals. A tournament all the intervals of which are trivial is called indecomposable; otherwise, it is decomposable. An indecomposable tournament T=(V,A) is then said to be critical if for each x∈V, T(V?{x}) is decomposable and if there are x≠y∈V such that T(V?{x,y}) is indecomposable. We introduce the operation of expansion which allows us to describe a process of construction of critical and infinite tournaments. It follows that, for every critical and infinite tournament T=(V,A), there are x≠y∈V such that T and T(V?{x,y}) are isomorphic. To cite this article: I. Boudabbous, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

On-line arbitrarily vertex decomposable trees

A tree T is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to the order of T there is a sequence of vertex-disjoint subtrees of T whose orders are given by τ. An on-line version of the problem of characterizing arbitrarily vertex decomposable trees is completely solved here.     

On arbitrarily vertex decomposable trees

A tree T is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to the order of T there is a sequence of vertex-disjoint subtrees of T whose orders are given by τ; from a result by Barth and Fournier it follows that Δ(T)?4. A necessary and a sufficient condition for being an arbitrarily vertex decomposable star-like tree have been exhibited. The conditions seem to be very close to each other.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

From decomposable to residual theories

Over the last decade, first-order constraints have been efficiently used in the artificial intelligence world to model many kinds of complex problems such as: scheduling, resource allocation, computer graphics and bio-informatics. Recently, a new property called decomposability has been introduced and many first-order theories have been proved to be decomposable: finite or infinite trees, rational and real numbers, linear dense order, etc. A decision procedure in the form of five rewriting rules has also been developed. This latter can decide if a first-order formula without free variables is true or not in any decomposable theory. Unfortunately, the definition of decomposable theories is too much complex: theoretical and definitively not intuitive. As a consequence, checking whether a given theory T is decomposable is almost impossible for a non expert in decomposability. We introduce in this paper residual theories: a new class of first-order theories whose definition is very intuitive, easy to check and much more adapted to the needs of the artificial intelligence community. We show that decomposable theories is a sub-class of residual theories and present, not only a decision procedure, but a full first-order constraint solver for residual theories. It transforms any first-order constraint φ (which can possibly contain free variables) into an equivalent formula ? which is either the formula true, or the formula false or a simple solved formula having at least one free variable and being equivalent neither to true nor to false. We show the efficiency of our solver by solving complex first-order constraints containing long nested alternations of quantifiers over different residual theories.     

Reconstruction of Discrete Sets from Four Projections: Strong Decomposability

In this paper we introduce the class of strongly decomposable discrete sets and give an efficient algorithm for reconstructing discrete sets of this class from four projections. It is also shown that every Q-convex set (along the set of directions {x, y}) consisting of several components is strongly decomposable. As a consequence of strong decomposability we get that in a subclass of hv-convex discrete sets the reconstruction from four projections can be solved in polynomial time.     

Functional calculus and duality for closed operators

In this paper, we continue our spectral-theoretic study [8] of unbounded closed operators in the framework of the spectral decomposition property and decomposable operators. Given a closed operator T with nonempty resolvent set, let f → f(T) be the homomorphism of the functional calculus. We show that if T has the spectral decomposition property, then f(T) is decomposable. Conversely, if f is nonconstant on every component of its domain which intersects the spectrum of T, then f(T) decomposable implies that T has the spectral decomposition property. A spectral duality theorems follows as a corollary. Furthermore, we obtain an analytic-type property for the canonical embedding J of the underlying Banach space X into its second dual $\text{X}{}^7$.     

Hamiltonian decompositions of products of cycles

A graph is said to be decomposable into hamiltonian cycles if its edge set can be partitioned into hamiltonian cycles. We show that the cartesian product of any three cycles can be decomposed into three hamiltonian cycles, thus settling a conjecture by Kotzig. We also show that, more generally, the cartesian product of 2^a3^b graphs, each decomposable into m hamiltonian cycles, can be decomposed into 2^a3^bm hamiltonian cycles.     

Arbitrarily vertex decomposable suns with few rays

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,…,n_k) of positive integers with n₁+?+n_k=n, there exists a partition (V₁,…,V_k) of the vertex set of G such that V_i induces a connected subgraph of order n_i, for all i=1,…,k. A sun with r rays is a unicyclic graph obtained by adding r hanging edges to r distinct vertices of a cycle. We characterize all arbitrarily vertex decomposable suns with at most three rays. We also provide a list of all on-line arbitrarily vertex decomposable suns with any number of rays.     

Measurable vectors for von Neumann algebras

Let A be a semifinite von Neumann algebra, with countably decomposable center, on the Hilbert space H. A measurable vector is a linear functional on H whose domain contains a strongly dense domain and which satisfies certain continuity conditions. H can be embedded as a dense subspace of the topological vector space of measurable vectors. The measurable vectors are a module over the measurable operators, and the action of measurable operators on measurable vectors is jointly continuous with respect to suitable topologies. If A is standard, then the measurable operators and measurable vectors are isomorphic as topological vector spaces. If the center of A is not countably decomposable, the results hold with minor changes.     

Dense Arbitrarily Vertex Decomposable Graphs

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n ₁, . . . , n _k ) of positive integers such that n ₁ + · · · + n _k = n there exists a partition (V ₁, . . . , V _k ) of the vertex set of G such that for each ${i \in \{1,\ldots,k\}}$ , V _i induces a connected subgraph of G on n _i vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n ≥ 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n ? 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.     

Absolute decomposability of the group of rational numbers

We prove that the group of rational numbersQ is absolutely decomposable.     

On local spectral properties of complex symmetric operators

In this paper we study properties of complex symmetric operators. In particular, we prove that every complex symmetric operator having property (β) or (δ) is decomposable. Moreover, we show that complex symmetric operator T has Dunford?s property (C) and it satisfies Weyl?s theorem if and only if its adjoint does.