The chromatic number and rank of the complements of the Kasami graphs

We determine the rank and chromatic number of the complements of all Kasami graphs, some of which form an infinite family of counterexamples to the now disproven rank-coloring conjecture.     

Computational complexity of some scheduling problems with multiprocessor tasks

The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees.     

Local Fractal Connections to Characterize the Spatial Processes of Deforestation in the Ecuadorian Amazon

Deforestation by human activities is a common issue in Amazonian countries. This occurs at different spatial and temporal scales causing primary forest loss and land fragmentation issues. During the deforestation process as the forest loses connectivity, the deforested patches create new intricate connections, which in turn create complex networks. In this study, we analyzed the local connected fractal dimension (LCFD) of the deforestation process in the Sumaco Biosphere Reserve (SBR) with two segmentation methods, —CA-wavelet and K-means—to categorize the complexity of deforested patches’ connections and then relate these with the spatial processes. The results showed an agreement with both methods, in which LCFD values below 1 corresponded to isolated patches with simple shapes and those above 1 signified more complex and connected patches. From CA-wavelet a threshold of 1.57 was detected allowing us to identify and discern low and high land transformation, while the threshold for K-means was 1.61. Both values represent the region from which deforestation performs local aggressive expansion networks. The thresholds were used to map the LCFD in which all spatial processes were visually detected. However, the threshold of 1.6 ± 0.03 was more effective in discerning high land transformation. such as shrinkage and attrition, in the deforestation process in the SBR.     

Suboptimality and complexity in evolution

A scalable model of biological evolution is presented which includes energy cost for building new elements and multiple paths for obtaining new functions. The model allows a population with a continual increase of complexity, but as time passes, detrimental mutations accumulate. This model shows the crucial importance of accounting for the energy cost of new structures in models of biological evolution. © 2014 Wiley Periodicals, Inc. Complexity 21: 322–327, 2015     

Degeneracy: Demystifying and destigmatizing a core concept in systems biology

Often relegated to the methods section of genetic research articles, the term “degeneracy” is regularly misunderstood and its theoretical significance widely understated. Degeneracy describes the ability of different structures to be conditionally interchangeable in their contribution to system functions. Frequently mislabeled redundancy, degeneracy refers to structural variation whereas redundancy refers to structural duplication. Sources of degeneracy include, but are not limited to, (1) duplicate structures that differentiate yet remain isofunctional, (2) unrelated isofunctional structures that are dispersed endogenously or exogenously, (3) variable arrangements of interacting structures that achieve the same output through multiple pathways, and (4) parcellation of a structure into subunits that can still variably perform the same initial function. The ability to perform the same function by drawing upon an array of dissimilar structures contributes advantageously to the integrity of a system. Drawing attention to the heterogeneous construction of living systems by highlighting the concept of degeneracy valuably enhances the ways scientists think about self‐organization, robustness, and complexity. Labels in science, however, can sometimes be misleading. In scientific nomenclature, the word “degeneracy” has calamitous proximity to the word “degeneration” used by pathologists and the shunned theory of degeneration once promoted by eugenicists. This article disentangles the concept of degeneracy from its close etymological siblings and offers a brief overview of the historical and contemporary understandings of degeneracy in science. Distinguishing the importance of degeneracy will hopefully allow systems theorists to more strategically operationally conceptualize the distributed intersecting networks that comprise complex living systems. © 2014 Wiley Periodicals, Inc. Complexity 20: 12–21, 2015     

Refined quicksort asymptotics

The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of n data, permuted uniformly at random, the appropriately normalized complexity Y_n is known to converge almost surely to a non‐degenerate random limit Y. This assumes a natural embedding of all Y_n on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown: where denotes a standard normal random variable. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 346–361, 2015     

Orthogonal Complement Based Divide-and-Conquer Algorithm for constrained multibody systems

A new algorithm, Orthogonal Complement based Divide-and-Conquer Algorithm (O-DCA), is presented in this paper for calculating the forward dynamics of constrained multi-rigid bodies including topologies involving single or coupled closed kinematic loops. The algorithm is exact and noniterative. The constraints are imposed at the acceleration level by utilizing a kinematic relation between the joint motion subspace (or partial velocities) and its orthogonal complement. Sample test cases indicate excellent constraint satisfaction and robust handling of singular configurations. Since the present algorithm does not use either a reduction or augmentation approach in the traditional sense for imposing the constraints, it does not suffer from the associated problems for systems passing through singular configurations. The computational complexity of the algorithm is expected to be O(n+m) and O(log(n+m)) for serial and parallel implementation, respectively, where n is the number of generalized coordinates and m is the number of independent algebraic constraints.     

Extended formulations for radial cones

This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.     

N-Annulated Perylene Bisimides to Bias the Differentiation of Metastable Supramolecular Assemblies into J- and H-Aggregates

The unique self-assembling features of N-annulated perylene bisimides (PBIs) 1 and 2 are reported. The stability of the aggregates of diester 1 , in which no H-bonding interactions are operative, corroborates the significance of long-range van der Waals and dipole–dipole electrostatic interactions in the construction of stable supramolecular assemblies. The incorporation of amide functional groups within the N-annulated PBI in 2 stimulates pathway differentiation to achieve up to three J-type aggregates and a fourth H-type aggregate depending on the experimental conditions. The results presented demonstrate unprecedented levels of control over synthetic supramolecular self-assembly and the rich differentiation that N-annulated PBIs exhibit, opening the door to new, complex, functional supramolecular materials.