The structure of invertible substitutions on a three-letter alphabet

We study the structure of invertible substitutions on three-letter alphabet. We show that there exists a finite set of invertible substitutions such that any invertible substitution can be written as I_wσ₁σ₂σ_k, where I_w is the inner automorphism associated with w, and for 1jk. As a consequence, M is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices.     

The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

Some results on quasipolyhedral convexity

The objective of this paper is to analyze under what well-known operations the class of quasipolyhedral convex functions, which can be regarded as an extension of that of polyhedral convex functions, is closed. The operations that will be considered are those that preserve polyhedral convexity, such that the image and the inverse image under linear transformations, right scalar multiplication (including the case where λ=0⁺) and pointwise addition.      

Lot-sizing with fixed charges on stocks: the convex hull

In this paper, we examine a variant of the uncapacitated lot-sizing model of Wagner–Whitin that includes fixed charges on the stocks. Such a model is natural in a production environment where stocking is a complex operation, and appears as a subproblem in more general network design problems.

Linear-programming formulations, a dynamic program, the convex hull of integer solutions and a separation algorithm are presented. All these turn out to be very natural extensions of the corresponding results of Barany et al. (Math. Programming Stud. 22 (1984) 32) for the uncapacitated lot-sizing problem. The convex hull proof is based on showing that an extended facility location formulation is tight and by projecting it onto the original space of variables.     

Generalised 2-circulant inequalities for the max-cut problem

The max-cut problem is a fundamental combinatorial optimisation problem, with many applications. Poljak and Turzik found some facet-defining inequalities for the associated polytope, which we call 2-circulant inequalities. We present a more general family of facet-defining inequalities, an exact separation algorithm that runs in polynomial time, and some computational results.     

Optimizing constrained subtrees of trees

Given a treeG = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the rooted subtree problem, is to find a maximum weight subtree, with a specified root, from a given set of subtrees.The second problem, called the subtree packing problem, is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root.We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial. In addition we show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing problem is given by pasting together the convex hulls of the rooted subtree problems.We examine in detail the case where the set of feasible subtrees rooted at nodei consists of all subtrees with at mostk nodes. For this case we derive valid inequalities, and specify the convex hull whenk 4.Research supported in part by Nato Collaborative Research Grant CRG 900281, Science Program SC1-CT91-620 of the EEC, and contract No 26 of the programme Pôle d'attraction interuniversitaire of the Belgian government.     

Metal complexes with an aminosubstituted tricarbollide ligand

The reaction of the tricarbollide salt Tl[7-tBuNH-7,8,9-C₃B₈H₁₀] (Tl1) with [(cod)Rh(THF)_x]⁺ gives the rhodium complex [1-(cod)-12-tBuNH-1,2,4,12-RhC₃B₈H₁₀] in almost quantitative yield. Analogous reactions of Tl1 with [(ring)M(THF)_x]²⁺ ((ring)M = Cp*Rh and (1,3,5-C₆H₃Me₃)Ru) afford the corresponding metallatricarbollides [1-(ring)-12-tBuNH-1,2,4,12-MC₃B₈H₁₀] in ca. 50% yield. Refluxing Tl1 with [Mn(CO)₃(MeCN)₃]⁺ in THF give the tricarbollide analogue of cymantrene, [1,1,1-(CO)₃-12-tBuNH-1,2,4,12-MnC₃B₈H₁₀], the structure of which was determined by single-crystal X-ray diffraction analysis. In all cases, the formation of the metallatricarbollide complexes is accompanied by polyhedral rearrangement leading to the maximum separation of the cage carbon atoms.     

Low-temperature single crystal X-ray diffraction and high-pressure Raman studies on [(CH3)2NH2]2[SbCl5]

The structure of bis(dimethylammonium) pentachloroantimonate(III), [(CH₃)₂NH₂]₂[SbCl₅], BDP, was studied at 15 K and ambient pressure by single-crystal X-ray diffraction as well as at ambient temperature and high pressures up to 4.87(5) GPa by Raman spectroscopy. BDP crystallizes in the orthorhombic Pnma space group with a=8.4069(4), b=11.7973(7), c=14.8496(7) Å, and Z=4; R₁=0.0381, wR₂=0.0764. The structure consists of distorted [SbCl₆]³⁻ octahedra forming zig-zag [{SbCl₅}_n]²ⁿ⁻ chains that are cross-linked by dimethylammonium [(CH₃)₂NH₂]⁺ cations. The organic and inorganic substructures are bound together by the N-H…Cl hydrogen bonds. The distortions of [SbCl₆]³⁻ units increase, partly due to the influence of the hydrogen bonds which became stronger, with decreasing temperature. The preliminary room temperature, high-pressure X-ray diffraction experiments suggest that BDP undergoes a first-order phase transition below ca. 0.44(5) GPa that destroys single-crystal samples. The transition is accompanied by changes in the intensities and positions of the Raman lines below 400 cm⁻¹.     

Synthesis of macrocyclic tris-cis-tris-trans- dodeca[(phenyl)(hydroxy)]cyclododecasiloxane in carbonic acid solution

The possibility to synthesize stereoregular tris-cis-tris-trans- dodeca[(phenyl)(hydroxy)]cyclododecasiloxane (tris-cis-tris-trans-[PhSi(O)OH]12) in an inorganic liquid medium – aqueous carbonic acid solution – was shown. The interaction of polyhedral phenylcoppersodiumsiloxane, {[(C₆H₅Si(O)O^?]₁₂(Cu₂⁺)₄(Na⁺)₄}*(L)_m (L?=?Buⁿ OH, H₂O), with carbonic acid can be considered as a new ‘green’ method to obtain functional organosiloxane macrocycles. In contrast to the known methods, no organic solvents were used during the reaction. The identification of the structure of the end compound was performed by means of NMR and Infrared spectroscopy as well as X-ray crystallography.     

Synthesis of peptide dendrimers with polyhedral oligomeric silsesquioxane cores via click chemistry

Inorganic polyhedral oligomeric silsesquioxane (POSS) was used as the core for the synthesis of poly(Llysine) peptide dendrimer via copper-catalyzed azide-alkyne click chemistry. The inorganic/organic composite dendrimer was characterized by MS, 1H NMR, FTIR, GPC and DLS.