Shifting : one-inclusion mistake bounds and sample compression

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy. The key step in their proof is a d = VC(F) bound on the graph density of a subgraph of the hypercube—oneinclusion graph. The first main result of this paper is a density bound of n [n−1 <=d-1]/[n <=d] < d, which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension d as being d contractible simplicial complexes, extending the well-known characterization that d = 1 maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth—the second part to a conjectured proof of correctness for Peeling—that every class has one-inclusion minimum degree at most its VCdimension. Our final main result is a k-class analogue of the d/n mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of O(logn) and is shown to be optimal up to an O(logk) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout.

Shifting : one-inclusion mistake bounds and sample compression

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy. The key step in their proof is a d=VC(F) bound on the graph density of a subgraph of the hypercube—one-inclusion graph. The first main result of this report is a density bound of n∙choose(n-1,≤d-1)/choose(n,≤d) < d, which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension d as being d-contractible simplicial complexes, extending the well-known characterization that d=1 maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth—the second part to a conjectured proof of correctness for Peeling—that every class has one-inclusion minimum degree at most its VC-dimension. Our final main result is a k-class analogue of the d/n mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of O(log n) and is shown to be optimal up to a O(log k) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout

On Walkup's class K (d) and a minimal triangulation of (S-3 (sic) S-1)(#3)

For d >= 2, Walkup's class K (d) consists of the d-dimensional simplicial complexes all whose vertex-links are stacked (d - 1)-spheres. Kalai showed that for d >= 4, all connected members of K (d) are obtained from stacked d-spheres by finitely many elementary handle additions. According to a result of Walkup, the face vector of any triangulated 4-manifold X with Euler characteristic chi satisfies f(1) >= 5f(0) - 15/2 chi, with equality only for X is an element of K(4). Kuhnel observed that this implies f(0)(f(0) - 11) >= -15 chi, with equality only for 2-neighborly members of K(4). Kuhnel also asked if there is a triangulated 4-manifold with f(0) = 15, chi = -4 (attaining equality in his lower bound). In this paper, guided by Kalai's theorem, we show that indeed there is such a triangulation. It triangulates the connected sum of three copies of the twisted sphere product S-3 (sic) S-1. Because of Kuhnel's inequality, the given triangulation of this manifold is a vertex-minimal triangulation. By a recent result of Effenberger, the triangulation constructed here is tight. Apart from the neighborly 2-manifolds and the infinite family of (2d + 3)-vertex sphere products Sd-1 X S-1 (twisted for d odd), only fourteen tight triangulated manifolds were known so far. The present construction yields a new member of this sporadic family. We also present a self-contained proof of Kalai's result. (C) 2011 Elsevier B.V. All rights reserved.

On k-stellated and k-stacked spheres

We introduce the class Sigma(k)(d) of k-stellated (combinatorial) spheres of dimension d (0 <= k <= d + 1) and compare and contrast it with the class S-k(d) (0 <= k <= d) of k-stacked homology d-spheres. We have E-1(d) = S-1(d), and Sigma(k)(d) subset of S-k(d) ford >= 2k-1. However, for each k >= 2 there are k-stacked spheres which are not k-stellated. For d <= 2k - 2, the existence of k-stellated spheres which are not k-stacked remains an open question. We also consider the class W-k(d) (and K-k(d)) of simplicial complexes all whose vertex-links belong to Sigma(k)(d - 1) (respectively, S-k(d - 1)). Thus, W-k(d) subset of K-k(d) for d >= 2k, while W-1(d) = K-1(d). Let (K) over bar (k)(d) denote the class of d-dimensional complexes all whose vertex-links are k-stacked balls. We show that for d >= 2k + 2, there is a natural bijection M -> (M) over bar from K-k(d) onto (K) over bar (k)(d + 1) which is the inverse to the boundary map partial derivative: (K) over bar (k)(d + 1) -> (K) over bar (k)(d). Finally, we complement the tightness results of our recent paper, Bagchi and Datta (2013) 5], by showing that, for any field F, an F-orientable (k + 1)-neighbourly member of W-k(2k + 1) is F-tight if and only if it is k-stacked.

On stellated spheres and a tightness criterion for combinatorial manifolds

We introduce k-stellated spheres and consider the class W-k(d) of triangulated d-manifolds, all of whose vertex links are k-stellated, and its subclass W-k*; (d), consisting of the (k + 1)-neighbourly members of W-k(d). We introduce the mu-vector of any simplicial complex and show that, in the case of 2-neighbourly simplicial complexes, the mu-vector dominates the vector of Betti numbers componentwise; the two vectors are equal precisely for tight simplicial complexes. We are able to estimate/compute certain alternating sums of the components of the mu-vector of any 2-neighbourly member of W-k(d) for d >= 2k. As a consequence of this theory, we prove a lower bound theorem for such triangulated manifolds, and we determine the integral homology type of members of W-k*(d) for d >= 2k + 2. As another application, we prove that, when d not equal 2k + 1, all members of W-k*(d) are tight. We also characterize the tight members of W-k*(2k + 1) in terms of their kth Betti numbers. These results more or less answer a recent question of Effenberger, and also provide a uniform and conceptual tightness proof for all except two of the known tight triangulated manifolds. We also prove a lower bound theorem for homology manifolds in which the members of W-1(d) provide the equality case. This generalizes a result (the d = 4 case) due to Walkup and Kuhnel. As a consequence, it is shown that every tight member of W-1 (d) is strongly minimal, thus providing substantial evidence in favour of a conjecture of Kuhnel and Lutz asserting that tight homology manifolds should be strongly minimal. (C) 2013 Elsevier Ltd. All rights reserved.

On f-vectors of polytopes and matroids

Thesis (Ph.D.)--University of Washington, 2016-08

Electrochemistry of Heteroleptic Tris(phthalocyaninato) Rare Earth(III) Complexes

The electrochemical characteristics of a series of heteroleptic tris(phthalocyaninato) complexes with identical rare earths or mixed rare earths (Pc)M(OOPc)M(OOPc) [M = Eu...Lu, Y; H2Pc = unsubstituted phthalocyanine, H2(OOPc) = 3,4,12,13,21,22,30,31-octakis(octyloxy)phthalocyanine] and (Pc)Eu(OOPc)Er(OOPc) have been recorded and studied comparatively by cyclic voltammetry (CV) and differential pulse voltammetry (DPV) in CH2Cl2 containing 0.1 M tetrabutylammonium perchlorate (TBAP). Up to five quasi-reversible one-electron oxidations and four one-electron reductions have been revealed. The half-wave potentials of the first, second and fifth oxidations depend on the size of the metal center, but the fifth changes in the opposite direction to that of the first two. Moreover, the difference in redox potentials of the first oxidation and first reduction for (Pc)M(OOPc)M(OOPc), 0.85−0.98 V, also decreases linearly along with decreasing rare earth ion radius, clearly showing the rare earth ion size effect and indicating enhanced π−π interactions in the triple-deckers connected by smaller lanthanides. This order follows the red-shift seen in the lowest energy band of triple-decker compounds. The electronic differences between the lanthanides and yttrium are more apparent for triple-decker sandwich complexes than for the analogous double-deckers. By comparing triple-decker, double-decker and mononuclear [ZnII] complexes containing the OOPc ligand, the HOMO−LUMO gap has been shown to contract approximately linearly with the number of stacked phthalocyanine ligands.

Sandwich complexes of naphthalocyanine with the rare earth metals

Over the past two decades and in particular the past five years, numerous sandwich-type rare earth complexes containing naphthalocyanine ligands have been synthesized. The more extended delocalized π-electron system of naphthalocyanine in comparison with phthalocyanine generates unique physical, spectroscopic, electrochemical and photoelectrochemical properties which have aroused significant research interest in these compounds. This review summarizes recent progress in research on this important class of molecular materials and overviews the current status of the field.

Comparative Electrochemical Study of Unsubstituted and Substituted Bis(phthalocyaninato) Rare Earth(III) Complexes

The electrochemistry of homoleptic substituted phthalocyaninato rare earth double-decker complexes M(TBPc)2 and M(OOPc)2 [M = Y, La...Lu except Pm; H2TBPc = 3(4),12(13),21(22),30(31)-tetra-tert-butylphthalocyanine, H2OOPc = 3,4,12,13,21,22,30,31-octakis(octyloxy)phthalocyanine] has been comparatively studied by cyclic voltammetry (CV) and differential pulse voltammetry (DPV) in CH2Cl2 containing 0.1 M tetra-n-butylammonium perchlorate (TBAP). Two quasi-reversible one-electron oxidations and three or four quasi-reversible one-electron reductions have been revealed for these neutral double-deckers of two series of substituted complexes, respectively. For comparison, unsubstituted bis(phthalocyaninato) rare earth analogues M(Pc)2 (M = Y, La...Lu except Pm; H2Pc = phthalocyanine) have also been electrochemically investigated. Two quasi-reversible one-electron oxidations and up to five quasi-reversible one-electron reductions have been revealed for these neutral double-decker compounds. The three bis(phthalocyaninato)cerium compounds display one cerium-centered redox wave between the first ligand-based oxidation and reduction. The half-wave potentials of the first and second oxidations and first reduction for double-deckers of the tervalent rare earths depend on the size of the metal center. The difference between the redox potentials of the second and third reductions for MIII(Pc)2, which represents the potential difference between the first oxidation and first reduction of [MIII(Pc)2]−, lies in the range 1.08−1.37 V and also gradually diminishes along with the lanthanide contraction, indicating enhanced π−π interactions in the double-deckers connected by the smaller, lanthanides. This corresponds well with the red-shift of the lowest energy band observed in the electronic absorption spectra of reduced double-decker [MIII(Pc′)2]− (Pc′ = Pc, TBPc, OOPc).

Vibrational spectroscopy of phthalocyanine and naphthalocyanine in sandwich-type (na)phthalocyaninato and porphyrinato rare earth complexes : (Part 10) The infrared and Raman characteristics of phthalocyanine in heteroleptic bis(phthalocyaninato) rare earth complexes with decreased molecular symmetry

The infrared (IR) spectroscopic data for a series of eleven heteroleptic bis(phthalocyaninato) rare earth complexes MIII(Pc)[Pc(α-OC5H11)4] (M = Sm–Lu, Y) [H2Pc = unsubstituted phthalocyanine, H2Pc(α-OC5H11)4 = 1,8,15,22-tetrakis(3-pentyloxy)phthalocyanine] have been collected with 2 cm−1 resolution. Raman spectroscopic properties in the range of 500–1800 cm−1 for these double-decker molecules have also been comparatively studied using laser excitation sources emitting at 632.8 and 785 nm. Both the IR and Raman spectra for M(Pc)[Pc(α-OC5H11)4] are more complicated than those of homoleptic bis(phthalocyaninato) rare earth analogues due to the decreased molecular symmetry of these double-decker compounds, namely C4. For this series, the IR Pc√− marker band appears as an intense absorption at 1309–1317 cm−1, attributed to the pyrrole stretching. With laser excitation at 632.8 nm, Raman vibrations derived from isoindole ring and aza stretchings in the range of 1300–1600 cm−1 are selectively intensified. In contrast, when excited with laser radiation of 785 nm, the ring radial vibrations of isoindole moieties and dihedral plane deformations between 500 and 1000 cm−1 for M(Pc)[Pc(α-OC5H11)4] intensify to become the strongest scatterings. Both techniques reveal that the frequencies of pyrrole stretching, isoindole breathing, isoindole stretchings, aza stretchings and coupling of pyrrole and aza stretchings depend on the rare earth ionic size, shifting to higher energy along with the lanthanide contraction due to the increased ring-ring interaction across the series. The assignments of the vibrational bands for these compounds have been made and discussed in relation to other unsubstituted and substituted bis(phthalocyaninato) rare earth analogues, such as M(Pc)2 and M(OOPc)2 [H2OOPc = 2,3,9,10,16,17,23,24-octakis(octyloxy)phthalocyanine].

Vibrational spectroscopy of phthalocyanine and naphthalocyanine in sandwich-type (na)phthalocyaninato and porphyrinato rare earth complexes: Part 14. The infrared and Raman characteristics of phthalocyanine in “pinwheel-like” homoleptic bis[1,8,15,22-tetrakis(3-pentyloxy)phthalocyaninato] rare earth(III) double-decker complexes

The infrared (IR) spectroscopic data and Raman spectroscopic properties for a series of 13 “pinwheel-like” homoleptic bis(phthalocyaninato) rare earth complexes M[Pc(α-OC5H11)4]2 [M = Y and Pr–Lu except Pm; H2Pc(α-OC5H11)4 = 1,8,15,22-tetrakis(3-pentyloxy)phthalocyanine] have been collected and comparatively studied. Both the IR and Raman spectra for M[Pc(α-OC5H11)4]2 are more complicated than those of homoleptic bis(phthalocyaninato) rare earth analogues, namely M(Pc)2 and M[Pc(OC8H17)8]2, but resemble (for IR) or are a bit more complicated (for Raman) than those of heteroleptic counterparts M(Pc)[Pc(α-OC5H11)4], revealing the decreased molecular symmetry of these double-decker compounds, namely S8. Except for the obvious splitting of the isoindole breathing band at 1110–1123 cm−1, the IR spectra of M[Pc(α-OC5H11)4]2 are quite similar to those of corresponding M(Pc)[Pc(α-OC5H11)4] and therefore are similarly assigned. With laser excitation at 633 nm, Raman bands derived from isoindole ring and aza stretchings in the range of 1300–1600 cm−1 are selectively intensified. The IR spectra reveal that the frequencies of pyrrole stretching and pyrrole stretching coupled with the symmetrical CH bending of –CH3 groups are sensitive to the rare earth ionic size, while the Raman technique shows that the bands due to the isoindole stretchings and the coupled pyrrole and aza stretchings are similarly affected. Nevertheless, the phthalocyanine monoanion radical Pc′− IR marker band of bis(phthalocyaninato) complexes involving the same rare earth ion is found to shift to lower energy in the order M(Pc)2 > M(Pc)[Pc(α-OC5H11)4] > M[Pc(α-OC5H11)4]2, revealing the weakened π–π interaction between the two phthalocyanine rings in the same order.

Raman spectroscopic characteristics of phthalocyanine and naphthalocyanine in sandwich-type phthalocyaninato and porphyrinato rare earth complexes Part 5. – Raman spectroscopic characteristics of naphthalocyanine in mixed [tetrakis(4-tert-butylphenyl)porphyrinato]-(naphthalocyaninato) rare earth double-deckers

Raman spectra were recorded in the range 400–1800 cm−1 for a series of 15 mixed \[tetrakis(4-tert-butylphenyl)porphyrinato](2,3-naphthalocyaninato) rare earth double-deckers M(TBPP)(Nc) (M = Y; La–Lu except Pm) using laser excitation at 632.8 and 785 nm. Comparisons with bis(naphthalocyaninato) rare earth counterparts reveal that the vibrations of the metallonaphthalocyanine M(Nc) fragment dominate the Raman features of M(TBPP)(Nc). When excited with radiation of 632.8 nm, the most intense vibration appears at about 1595 cm−1, due to the naphthalene stretching. These complexes exhibit the marker Raman band for Nc•− as a medium-intense band in the range 1496–1507 cm−1, attributed to the coupling of pyrrole and aza stretching, while the marker Raman band of Nc2− in intermediate-valence Ce(TBPP)(Nc) appears as a strong band at 1493 cm−1 and is due to the isoindole stretchings. By contrast, when excited with radiation of 785 nm that is in close resonance with the main Q absorption band of the naphthalocyanine ligand, the ring radial vibrations at ca 680 and 735 cm−1 for MIII(TBPP)(Nc) are selectively intensified and are the most intense bands. For the cerium double-decker, the most intense vibration also acting as the marker Raman band of Nc2− appears at 1497 cm−1 with contributions from both pyrrole CC and aza CN stretches. The same vibrational modes show weak to medium intensity scattering at 1506–1509 cm−1 for MIII(TBPP)(Nc) and this is the marker Raman band of Nc•− when thus excited. The scatterings due to the Nc breathings, ring radial vibration, aza group stretchings, naphthalene stretchings, benzoisoindole stretchings and the coupling of pyrrole CC and aza CN stretchings in MIII(TBPP)(Nc) are all slightly blue shifted along with the decrease in rare earth ionic radius, confirming the effects of increased ring–ring interactions on the Raman characteristics of naphthalocyanine in the mixed ring double-deckers.