Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

A Structural Entropy Measurement Principle of Propositional Formulas in Conjunctive Normal Form

The satisfiability (SAT) problem is a core problem in computer science. Existing studies have shown that most industrial SAT instances can be effectively solved by modern SAT solvers while random SAT instances cannot. It is believed that the structural characteristics of different SAT formula classes are the reasons behind this difference. In this paper, we study the structural properties of propositional formulas in conjunctive normal form (CNF) by the principle of structural entropy of formulas. First, we used structural entropy to measure the complex structure of a formula and found that the difficulty solving the formula is related to the structural entropy of the formula. The smaller the compressing information of a formula, the more difficult it is to solve the formula. Secondly, we proposed a λ-approximation strategy to approximate the structural entropy of large formulas. The experimental results showed that the proposed strategy can effectively approximate the structural entropy of the original formula and that the approximation ratio is more than 92%. Finally, we analyzed the structural properties of a formula in the solution process and found that a local search solver tends to select variables in different communities to perform the next round of searches during a search and that the structural entropy of a variable affects the probability of the variable being flipped. By using these conclusions, we also proposed an initial candidate solution generation strategy for a local search for SAT, and the experimental results showed that this strategy effectively improves the performance of the solvers CCAsat and Sparrow2011 when incorporated into these two solvers.     

Synthesis of diisocyanides with phenolic groups and their polymerization to helically chiral poly(quinoxaline‐2,3‐diyl)s

The development of synthetic routes which lead to five new diisocyanide monomers with one or two phenolic groups is described. Their polymerization behavior is studied with Pd‐ and Ni‐based initiators, as well as under microwave irradiation. The polymerizability is mainly dominated by steric effects as is concluded from experiments using different protecting groups. Chiroptical properties of these new polymers are studied by CD‐spectroscopy. After deprotection, helically chiral poly(quinoxalin‐2,3‐diyl)s are obtained which display a Brønsted function attached to a stereolabile biaryl axis whose configuration should be influenced by the chiral polymer backbone. © 2015 Wiley Periodicals, Inc. J. Polym. Sci., Part A: Polym. Chem. 2015 , 53, 1320–1329     

Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

The deformation and fracture of balloons

Inflation of balloons provides a straightforward way of achieving large biaxial deformations. Previous studies have shown that when a balloon bursts, crack propagation occurs at very high speed – much higher than would be expected from the low strain modulus and elastic wave velocity of the rubber. The present paper is concerned with studies of the deformation and fracture of cylindrical balloons. On inflation, the deformations of such a balloon pass through an unstable region but subsequently increase monotonically with pressure. In this relatively high pressure region, the ratio of the longitudinal and circumferential extension ratios is broadly in accord with expectations from high-strain elasticity theory when the ratio of the corresponding stresses is taken into account. On bursting, crack speeds up to around 300 m/s in this region. It is shown that these speeds are in accord with large increase in incremental moduli for the highly-strained rubber. Marked changes in crack tip profile observed at very high crack speeds are consistent with control of the rate of growth by inertia rather than by the viscoelastic properties of the rubber (as is believed to be the case at lower speeds). Consistent with this, various elastomers having different glass transition temperatures show similar crack growth behaviour in the very high speed region.