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.     

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.

     

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     

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.     

The Local Limit of the Uniform Spanning Tree on Dense Graphs

Let G be a connected graph in which almost all vertices have linear degrees and let \(\mathcal {T}\) be a uniform spanning tree of G. For any fixed rooted tree F of height r we compute the asymptotic density of vertices v for which the r-ball around v in \(\mathcal {T}\) is isomorphic to F. We deduce from this that if \(\{G_n\}\) is a sequence of such graphs converging to a graphon W, then the uniform spanning tree of \(G_n\) locally converges to a multi-type branching process defined in terms of W. As an application, we prove that in a graph with linear minimum degree, with high probability, the density of leaves in a uniform spanning tree is at least \(e^{-1}-\mathsf {o}(1)\), the density of vertices of degree 2 is at most \(e^{-1}+\mathsf {o}(1)\) and the density of vertices of degree \(k\geqslant 3\) is at most \({(k-2)^{k-2} \over (k-1)! e^{k-2}} + \mathsf {o}(1)\). These bounds are sharp.     

Experimental studies on the ring opening polymerization of p-dioxanone using an Al(OPr)3-monosaccharide initiator system

The ring opening polymerization (ROP) of p-dioxanone using a protected monosaccharide (1,2;3,4-di-O-isopropylidene-α-d-galactopyranose)/Al(OⁱPr)₃ initiator system to yield polydioxanone with a protected monosaccharide end-group is described. The products were synthesized at 60-100 °C and characterized by ¹H and ¹³C NMR, and MALDI-TOF mass spectrometry. Besides the desired polydioxanone functionalised with a monosaccharide end-group, also polydioxanone with an OⁱPr end-group was formed (20-30%). Systematic studies showed that the polymer yield is a function of the reaction temperature and the reaction time, with higher temperatures (100 °C) leading to lower yields. The average chain length of the polymers is between 7 and 58 repeating units and may be tuned by the monomer to monosaccharide ratio (at constant Al(OⁱPr)₃ intake). A statistical model has been developed that successfully describes the experimentally observed relation between the average chain length of the functionalized polymer and reaction parameters.     

Radiative lifetimes of the NaRb C(3)1Σ+ state: experiment and theory

Radiative lifetimes for 2≤v^′≤44 rovibronic C¹Σ⁺ state levels of NaRb and quenching collision cross-sections with Rb atoms have been directly measured in a thermal cell by detecting time resolved laser induced fluorescence after pulsed excitation. Many body multipartitioning theory was applied to calculate C¹Σ⁺-X¹Σ⁺ and C¹Σ⁺-A¹Σ⁺ transition dipole moments. The relevant ab initio matrix elements were converted to the C¹Σ⁺ state radiative lifetimes. The strong spin-orbit A¹Σ⁺∼ b³Π coupling effect on the total C → A transition probabilities and lifetimes of the C¹Σ⁺ state is discussed. The measured radiative lifetimes show a decrease from 61 to 34 ns as the v^′ values increase, the results being in good agreement with calculations. The averaged collisional quenching cross-section value σ=(3±1)×10^-14 cm² was determined for NaRb (C¹Σ⁺) + Rb collisions from the Stern-Volmer plots.     

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.     

Positive pion photoproduction from hydrogen at photon energies between 500 MeV and 1,400 MeV in forward direction

The differential cross section of the reactionγ+p→π ⁺ was measured at pion CM-angles of 20° and 30° for photon energies between 500 MeV and 1,400 MeV. The pions were detected in a magnetic spectrometer. By measuring each pion trajectory and by offline calculation of the initial pion parameters an energy resolution of about 2.5% FWHM was achieved. The results complete a set of data which were measured in recent years at the Bonn 2.5 GeV synchrotron. In comparison to photoproduction analyses two effects were revealed: The η cusp appears in the energy dependence of the cross section as a sharp drop atK _γ=710 MeV. In the region of the third resonance the data show a greater enhancement than predicted by most of the analyses.