Multicomponent Metal-Organic Frameworks

Metal-organic frameworks (MOFs) are constructed from metal ions or clusters and organic linkers. Typical MOFs are rather simple, comprising just one type of joint and linker. An additional degree of structural complexity can be introduced by using multiple different components that are assembled into the same framework In the early days of MOF chemistry, conventional wisdom held that attempting to prepare frameworks starting from such a broad set of components would lead to multiple different phases. However, this review highlights how this view was mistaken and frameworks comprising multiple different components can be deliberately designed and synthesized. When coupled to structural order and periodicity, the presence of multiple components leads to exceptional functional properties that can be understood at the atomic level.     

Duality respecting representations and compatible complexity measures for gammoids

We show that every gammoid has special digraph representations, such that a representation of the dual of the gammoid may be easily obtained by reversing all arcs. In an informal sense, the duality notion of a poset applied to the digraph of a special representation of a gammoid commutes with the operation of forming the dual of that gammoid. We use these special representations in order to define a complexity measure for gammoids, such that the classes of gammoids with bounded complexity are closed under duality, minors, and direct sums.     

Minimizing the number of machines for minimum length schedules

In this paper, we present a new objective function for scheduling on parallel machines: minimizing the number of machines for schedules of minimum length. We study its complexity and we prove the NP-completeness of this problem, even if there is no precedences or for unitary execution times. We propose several polynomial algorithms for various particular cases.     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

An unfeasibility view of neural network learning

We define the notion of a continuously differentiable perfect learning algorithm for multilayer neural network architectures and show that such algorithms do not exist provided that the length of the data set exceeds the number of involved parameters and the activation functions are logistic, tanh or sin.     

Complexification phenomenon in an example of sensitive singular perturbationPhénomène de complexification dans un exemple de perturbation singulière sensitive

We consider singular perturbation problems depending on a parameter ε?0 such that for ε>0 the solution u^ε belongs to a Sobolev space on a domain $\text{Ω}$, but the limit u⁰ is not a distribution on $\text{Ω}$. A very simple model problem, solvable by Fourier transform allows us to study the complexification process of u^ε as $\text{ε↘0}$. The limit holds in the topology of a space of analytical functionals. To cite this article: C.A. De Souza, É. Sanchez-Palencia, C. R. Mecanique 332 (2004).     

Maximal admissible faces and asymptotic bounds for the normal surface solution space

The enumeration of normal surfaces is a key bottleneck in computational three-dimensional topology. The underlying procedure is the enumeration of admissible vertices of a high-dimensional polytope, where admissibility is a powerful but non-linear and non-convex constraint. The main results of this paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices, using polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system.To achieve these results we examine the layout of admissible points within these polytopes. We show that these points correspond to well-behaved substructures of the face lattice, and we study properties of the corresponding “admissible faces”. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.     

Complexity issues for the sandwich homogeneous set problem

Graph sandwich problems were introduced by Golumbic et al. (1994) in [12] for DNA physical mapping problems and can be described as follows. Given a property Π of graphs and two disjoint sets of edges E₁, E₂ with E₁⊆E₂ on a vertex set V, the problem is to find a graph G on V with edge set E_s having property Π and such that E₁⊆E_s⊆E₂.In this paper, we exhibit a quasi-linear reduction between the problem of finding an independent set of size k≥2 in a graph and the problem of finding a sandwich homogeneous set of the same size k. Using this reduction, we prove that a number of natural (decision and counting) problems related to sandwich homogeneous sets are hard in general. We then exploit a little further the reduction and show that finding efficient algorithms to compute small sandwich homogeneous sets would imply substantial improvement for computing triangles in graphs.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.