Strongly polynomial-time approximation for a class of bicriteria problems

Consider the following problem: given a ground set and two minimization objectives of the same type find a subset from a given subset-class that minimizes the first objective subject to a budget constraint on the second objective. Using Megiddo's parametric method we improve an earlier weakly polynomial time algorithm.     

Separation of potential flavoring compounds by high-performance liquid chromatography

High-performance liquid chromatography separated successively and quantitatively the food flavoring agents pyrimidines, purines and nucleosides, followed by nucleotides, then by polyphenols and finally by pyrazines with a reversed-phase octadecylsilica (μBondapak C₁₈) column and various proportions of methanol, water, acetic acid and tetrabutylammonium phosphate (PIC A). The polar solvent (solvent A) was water—acetic acid—PIC A (97.5:1.5:1.0) and the relatively non-polar solvent (solvent B) was methanol—acetic acid—PIC A (97.5:1.5:1.0). Purines, pyrimidines, and nucleosides were eluted with solvent A. Nucleotides were eluted with a mixture of solvents A and B (9:1). Polyphenols were separated with a gradient starting at 10% solvent B and finishing at 25% solvent B, and finally the pyrazines were removed successively from the column with a gradient starting at 25% solvent B and finishing at 45% solvent B. The resolution and reproducibility were excellent for more than 50 compounds. By this method beverages could be analyzed directly, without solvent extraction, for flavoring compounds.     

Law of the iterated logarithm for random graphs

A milestone in probability theory is the law of the iterated logarithm (LIL), proved by Khinchin and independently by Kolmogorov in the 1920s, which asserts that for iid random variables with mean 0 and variance 1 In this paper we prove that LIL holds for various functionals of random graphs and hypergraphs models. We first prove LIL for the number of copies of a fixed subgraph H. Two harder results concern the number of global objects: perfect matchings and Hamiltonian cycles. The main new ingredient in these results is a large deviation bound, which may be of independent interest. For random k‐uniform hypergraphs, we obtain the Central Limit Theorem and LIL for the number of Hamilton cycles.     

Online variable-sized bin packing with conflicts

We study a new kind of online bin packing with conflicts, motivated by a problem arising when scheduling jobs on the Grid. In this bin packing problem, the set of items is given at the beginning, together with a set of conflicts on pairs of items. A conflict on a pair of items implies that they cannot be assigned to a common bin. The online scenario is realized as follows. Variable-sized bins arrive one by one, and items need to be assigned to each bin before the next bin arrives. We analyze the online problem as well as semi-online versions of it, which are the variant where the sizes of the arriving bins are monotonically non-increasing as well as the variant where they are monotonically non-decreasing.     

A Construction of Almost Steiner Systems

Let n, k, and t be integers satisfying . A Steiner system with parameters t, k, and n is a k‐uniform hypergraph on n vertices in which every set of t distinct vertices is contained in exactly one edge. An outstanding problem in Design Theory is to determine whether a nontrivial Steiner system exists for . In this note we prove that for every and sufficiently large n, there exists an almost Steiner system with parameters t, k, and n; that is, there exists a k‐uniform hypergraph on n vertices such that every set of t distinct vertices is covered by either one or two edges.     

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

Interactions of histatin-3 and histatin-5 with actin

Background

Histatins are histidine rich polypeptides produced in the parotid and submandibular gland and secreted into the saliva. Histatin-3 and ?5 are the most important polycationic histatins. They possess antimicrobial activity against fungi such as Candida albicans. Histatin-5 has a higher antifungal activity than histatin-3 while histatin-3 is mostly involved in wound healing in the oral cavity. We found that these histatins, like other polycationic peptides and proteins, such as LL-37, lysozyme and histones, interact with extracellular actin.

Results

Histatin-3 and ?5 polymerize globular actin (G-actin) to filamentous actin (F-actin) and bundle F-actin filaments. Both actin polymerization and bundling by histatins is pH sensitive due to the high histidine content of histatins. In spite of the equal number of net positive charges and histidine residues in histatin-3 and ?5, less histatin-3 is needed than histatin-5 for polymerization and bundling of actin. The efficiency of actin polymerization and bundling by histatins greatly increases with decreasing pH. Histatin-3 and ?5 induced actin bundles are dissociated by 100 and 50 mM NaCl, respectively. The relatively low NaCl concentration required to dissociate histatin-induced bundles implies that the actin-histatin filaments bind to each other mainly by electrostatic forces. The binding of histatin-3 to F-actin is stronger than that of histatin-5 showing that hydrophobic forces have also some role in histatin-3- actin interaction. Histatins affect the fluorescence of probes attached to the D-loop of G-actin indicating histatin induced changes in actin structure. Transglutaminase cross-links histatins to actin. Competition and limited proteolysis experiments indicate that the main histatin cross-linking site on actin is glutamine-49 on the D-loop of actin.

Conclusions

Both histatin-3 and ?5 interacts with actin, however, histatin 3 binds stronger to actin and affects actin structure at lower concentration than histatin-5 due to the extra 8 amino acid sequence at the C-terminus of histatin-3. Extracellular actin might regulate histatin activity in the oral cavity, which should be the subject of further investigation.

     

Optical purification of a mixture of chiral forms by dimer formation

We introduce a readily executable method for the optical purification of "scalemic" (non 50%-50%) mixtures of chiral molecules of opposite handedness ("enantiomers"). The method relies on the formation of two types of dimers, (R-R or S-S) "homodimers" and (R-S) "heterodimers." The selectivity is linked to the difference in sign recently discovered by us to exist between certain transition-dipole matrix elements of opposite enantiomers. This sign difference results in differences in spectral propensity rules: In homodimers, transitions from the ground state can only take place to inversion symmetric excited states, while in the heterodimer the transitions are much more likely to proceed to antisymmetric excited states (although for heterodimers weak transitions to symmetric states might exist). These opposing propensity rules fully explain the observed large differences in the spectra of homodimers vs. heterodimers, which exist despite the almost identical energy levels positions. We illustrate the general concepts by computationally demonstrating the optically induced enantio-purification of scalemic mixtures of the hydropropionic C(3)H(6)O(3) (lactic) acid.     

Color-critical graphs have logarithmic circumference

A graph G is k-critical if every proper subgraph of G is (k−1)-colorable, but the graph G itself is not. We prove that every k-critical graph on n vertices has a cycle of length at least , improving a bound of Alon, Krivelevich and Seymour from 2000. Examples of Gallai from 1963 show that the bound cannot be improved to exceed . We thus settle the problem of bounding the minimal circumference of k-critical graphs, raised by Dirac in 1952 and Kelly and Kelly in 1954.