McMullen's conditions and some lower bounds for general convex polytopes

We give a lower bound for the number of vertices of a generald-dimensional polytope with a given numberm ofi-faces for eachi = 0,..., d/2 – 1. The tightness of those bounds is proved using McMullen's conditions. Form greater than a small constant, those lower bounds are attained by simpliciali-neighbourly polytopes.     

A theorem on the average number of subfaces in arrangements and oriented matroids

It is known that for simple arrangements in thed-dimensional Euclidean spaceR ^d The average number ofj-dimensional subfaces of ak-dimensional face is less than . In this paper, we show that this is also true for all arrangements inR ^d and for all oriented matroids, and we give combinatorial proofs.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Complete Enumeration of Small Realizable Oriented Matroids

Enumeration of all combinatorial types of point configurations and polytopes is a fundamental problem in combinatorial geometry. Although many studies have been done, most of them are for 2-dimensional and non-degenerate cases. Finschi and Fukuda (Discrete Comput Geom 27:117–136, 2002) published the first database of oriented matroids including degenerate (i.e., non-uniform) ones and of higher ranks. In this paper, we investigate algorithmic ways to classify them in terms of realizability, although the underlying decision problem of realizability checking is NP-hard. As an application, we determine all possible combinatorial types (including degenerate ones) of 3-dimensional configurations of 8 points, 2-dimensional configurations of 9 points, and 5-dimensional configurations of 9 points. We also determine all possible combinatorial types of 5-polytopes with nine vertices.     

Pivoting in Linear Complementarity: Two Polynomial-Time Cases

We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty’s least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris’s highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP.     

Criss-cross methods: A fresh view on pivot algorithms

Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution. The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms. The origins and the history of criss-cross methods are also touched upon.     

Characterization and activity analysis of catalytic water oxidation induced by hybridization of [(OH(2))(terpy)Mn(mu-O)(2)Mn(terpy)(OH(2))](3+) and clay compounds

Hybridization of [(OH(2))(terpy)Mn(mu-O)(2)Mn(terpy)(OH(2))](3+) (terpy= 2,2':6',2' '-terpyridine) (1) and mica clay yielded catalytic dioxygen (O(2)) evolution from water using a CeIV oxidant. The reaction was characterized by various spectroscopic measurements and a kinetic analysis of O(2) evolution. X-ray diffraction (XRD) data indicates the interlayer separation of mica changes upon intercalation of 1. The UV-vis diffuse reflectance (RD) and Mn K-edge X-ray absorption near-edge structure (XANES) data suggest that the oxidation state of the di-mu-oxo Mn(2) core is Mn(III)-Mn(IV), but it is not intact. In aqueous solution, the reaction of 1 with a large excess Ce(IV) oxidant led to decomposition of 1 to form MnO(4-) ion without O(2) evolution, most possibly by its disproportionation. However, MnO(4-) formation is suppressed by adsorption of 1 on clay. The maximum turnover number for O(2) evolution catalyzed by 1 adsorbed on mica and kaolin was 15 and 17, respectively, under the optimum conditions. The catalysis occurs in the interlayer space of mica or on the surface of kaolin, whereas MnO(4-) formation occurs in the liquid phase, involving local adsorption equilibria of adsorbed 1 at the interface between the clay surface and the liquid phase. The analysis of O(2) evolution activity showed that the catalysis requires cooperation of two equivalents of 1 adsorbed on clay. The second-order rate constant based on the concentration (mol g(-1)) of 1 per unit weight of clay was 2.7 +/- 0.1 mol(-1) s(-1) g for mica, which is appreciably lower than that for kaolin (23.9 +/- 0.4 mol(-1) s(-1) g). This difference can be explained by the localized adsorption of 1 on the surface for kaolin. However, the apparent turnover frequency ((kO(2))app/s(-1)) of 1 on mica was 2.2 times greater than on kaolin when the same fractional loading is compared. The higher cation exchange capacity (CEC) of mica statistically affords a shorter distance between the anionic sites to which 1 is attracted electrostatically, making the cooperative interaction between adsorbed molecules of 1 easier than that on kaolin. The higher CEC is important not only for attaining a higher loading but also for the higher catalytic activity of adsorbed 1.     

Structures of two alkaline autoxidation products of BHA, a widely used antioxidant

In order to confirm the structures of the autoxidation products of 2-tert-butyl-4-methoxyphenol (BHA), X-ray crystallographic analyses have been undertaken. One of the products was converted to a dibenzoate, which was subjected to the analysis to establish the structure as the O ⁶,O ⁷-dibenzoyl derivative of (1R*,2R*,6S*,7S*,9R*)-4,9-di-tert-butyl-6,7-dihydroxytricyclo[5.2.2.0^{2, 6}]undec-4-ene-3,8,10-trione. Crystallographic analysis of the major isomer of the two isomeric products gave its structure as (E)-4-tert-butyl-2-(3-tert-butyl-4-oxocyclopent-2-en-1-ylidene)cyclopent-4-ene-1,3-dione, which also established the structure of the minor isomer as the corresponding (Z)-isomer.     

Spectroscopic study on interaction of nucleic acid base with tryptophan-containing tripeptides: acetyl-Trp-X-Trp-NHCH3 (X = Gly, Asn, Asp, Gln and Glu).

As part of a series of peptides designed to have binding ability selective for each of the nucleic acid bases, five tripeptides consisting of N-acetyl-Trp-X-Trp-NHCH3 (X = Gly, Asn, Asp, Gln and Glu) were synthesized, and their abilities to form complexes with four different nucleotides were examined by the fluorescence and phase distribution methods. The association constants obtained indicated that, depending on the sort of X residue, the peptides showed a variation in their interaction with guanosine monophosphate (GMP), while no noticeable selectivity was observed for other nucleotides adenosine monophosphate (AMP), uridine monophosphate (UMP) and cytidine monophosphate (CMP). The binding mode of N-acetyl-Trp-Asp-Trp-NHCH3 for the guanine base was further investigated using the proton nuclear magnetic resonance (1H-NMR) method. The mode was suggested to involve intimate cooperation of (1) the hydrogen bond formation between the carboxyl group of the Asp side chain and the guanine C2-amino group, and (2) the stacking interaction of the base with two terminal Trp residues of the peptide. Such interaction was strengthened by the protonation of the guanine base. A tentative binding mode is proposed based on these results.