On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Proton conductivity and luminiscence properties of lanthanide aminotriphosphonates

Metal phosphonates are multifunctional solids with tunable properties, such as internal H-bond networks, and high chemical and thermal stability [1]. In the present work, we describe the synthesis, structural characterization, luminescent properties and proton conduction performance of a new family of isostructural cationic compounds with general formula [Ln(H4NMP)(H2O)2]Cl·2H2O [Ln = La3+, Pr3+, Sm3+, Gd3+, Tb3+, Dy3+, Ho3+, H6NMP = nitrilotris(methylphosphonic acid)]. These solids are formed by positively charge layers, which consist of isolated LnO8 polyhedra and bridge chelating NMP2- ligands, held apart by chloride ions and water molecules. This arrangement result in extended interlayer hydrogen networks with possible proton transfer pathways. The proton conductivity of Gd3+ sample, selected as prototype of the series, was measured. In the range between range 25º and 80 ºC, the conductivity increase with the temperature up to a maximum value of 3.10-4 S·cm-1, at relative humidity of 95 %. The activation energy obtained from the Arrhenius plot (Figure 1) is in the range corresponding to a Grotthuss transfer mechanism.