Search

We define the acyclic orientation polynomial of a graph to be the generating function for the sinks of its acyclic orientations. Stanley proved that the number of acyclic orientations is equal to the chromatic polynomial evaluated at $-1$ up to sign. Motivated by this link between acyclic orientations and the chromatic polynomial, we develop "acyclic orientation" analogues of theorems concerning the chromatic polynomial of Birkhoff, Whitney, and Greene-Zaslavsky. As an application, we provide a new proof for Stanley's sink theorem for chromatic symmetric functions $X_G$. This theorem gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of $X_G$ with respect to elementary symmetric functions., Comment: 21 pages, 4 figures

High-dimensional networks are a topological generalization of electrical networks. As combinatorial invariants of electrical networks often require enumeration of trees, their high-dimensional analogues are also based on torsion-weighted enumeration of acyclic subcomplexes over the reals. In this paper, for a high-dimensional network with a current generator, we express a current vector and a voltage vector in terms of high-dimensional forests. To this end, we introduce a new simple method, an acyclization in codimension 1, for computing forest-numbers.

We introduce the notion of effective resistance for a simplicial network ( X , R ) where X is a simplicial complex and R is a set of resistances for the top simplices, and prove two formulas generalizing previous results concerning effective resistance for resistor networks. Our approach, based on combinatorial Hodge theory, is to assign a unique harmonic class to a current generator σ, an extra top-dimensional simplex to be attached to X. We will show that the harmonic class gives rise to the current I σ and the voltage V σ for X ∪ σ , satisfying Thomson's energy-minimizing principle and Ohm's law for simplicial networks. The effective resistance R σ of a current generator σ shall be defined as a ratio of the σ-components of V σ and I σ . By introducing potential for voltage vectors, we present a formula for R σ via the inverse of the weighted combinatorial Laplacian of X in codimension one. We also derive a formula for R σ via weighted high-dimensional tree-numbers for X, providing a combinatorial interpretation for R σ . As an application, we generalize Foster's Theorem, and discuss various high-dimensional examples.

We present a version of the weighted cellular matrix-tree theorem that is suitable for calculating explicit generating functions for spanning trees of highly structured families of simplicial and cell complexes. We apply the result to give weighted generalizations of the tree enumeration formulas of Adin for complete colorful complexes, and of Duval, Klivans and Martin for skeleta of hypercubes. We investigate the latter further via a logarithmic generating function for weighted tree enumeration, and derive another tree-counting formula using the unsigned Euler characteristics of skeleta of a hypercube and the Crapo $\beta$-invariant of uniform matroids., Comment: 22 pages, 2 figures. Sections 6 and 7 of previous version simplified and condensed. Final version to appear in J. Combin. Theory Ser. A

The Mobius coinvariant μ ⊥ ( G ) of a graph G is defined to be the Mobius invariant of the dual of the cycle matroid of G . This invariant is known to equal the rank of the reduced homology of the cycle matroid complex of G . For a complete graph K m + 1 , W. Kook gave an interpretation of μ ⊥ ( K m + 1 ) as the number of edge-rooted forests in K m . In this paper, we obtain a new combinatorial interpretation of μ ⊥ ( K m + 1 , n + 1 ) as the number of B-edge-rooted forests in K m , n , which is a bipartite analogue of the previous result. Based on these interpretations, we will give new bijective proofs of the formulas for μ ⊥ ( K m + 1 ) and μ ⊥ ( K m + 1 , n + 1 ) given by I. Novik, A. Postnikov, and B. Sturmfels in terms of the Hermite polynomials. In addition, we will construct a homology basis for the cycle matroid complex of K m + 1 , n + 1 indexed by the B-edge-rooted forests. Also we will discuss the Mobius coinvariant of bi-coned graphs which generalize complete bipartite graphs.

For a network G, we introduce a non-singular symmetric matrix, called a path intersection matrix, that will provide a new method for computing the ratio k ( G ) / k ( G / a b ) where k ( G ) is the tree-number of G and G / a b is obtained from G ∪ a b by contracting the new edge ab between two distinct nodes a and b. The quantities k ( G ) / k ( G / a b ) appear as invariants for various networks such as effective conductance for an electrical network and an ingredient for information centrality for a social network. We will review several examples of networks where path intersection matrices can be applied.

We report the design and synthesis of a DNA-encoded one-bead one-compound library of cyclic peptoids composed of more than 11 million molecules. We show that affinity-based screening of this large library can identify cyclic peptoid ligands for a target protein. In this work, we developed a simple method for amplifying the PCR product from DNA tags on a single bead, thereby enabling determination of the structures of hit cyclic peptoids with no need for high-throughput sequencing and complicated data analysis. We also developed a sublibrary screening strategy to minimize false positives caused by the interference of coding DNA tags before starting laborious and impractical hit confirmation. Given the simplicity and robustness of the synthesis and screening, along with the desirable features of macrocyclic peptoids including improved conformational rigidity, our method will be highly useful for discovering biologically active molecules modulating challenging targets such as protein-protein interactions that are not easily targeted by typical peptidomimetics and small-molecules.

Peptoids, oligomers of N-substituted glycines, have been attracting increasing interest due to their advantageous properties as peptidomimetics. However, due to the lack of chiral centers and amide hydrogen atoms, peptoids, in general, do not form folding structures except that they have α-chiral side chains. We have recently developed "peptoids with backbone chirality" as a new class of peptoid foldamers called α-ABpeptoids and demonstrated that they could have folding conformations owing to the methyl groups on chiral α-carbons in the backbone structure. Here we report α-ABpeptoid/β3 -peptide oligomers as a unique peptidomimetic structure with a heterogeneous backbone. This hybrid structure contains a mixed α-ABpeptoid and β3 -peptide residues arranged in an alternate manner. These α-ABpeptoid/β3 -peptide oligomers could form intramolecular hydrogen bonding and have better cell permeability relative to pure peptide sequences. These oligomers were shown to adopt ordered folding structures based on circular dichroism studies. Overall, α-ABpeptoid/β3 -peptide oligomers may represent a novel class of peptidomimetic foldamers and will find a wide range of applications in biomedical and material sciences.

We give a formula for the simplicial tree-numbers of the independent set complex of a finite matroid M as a product of eigenvalues of the total combinatorial Laplacians on this complex. Two matroid invariants emerge naturally in describing the multiplicities of these eigenvalues in the formula: one is the unsigned reduced Euler characteristic of the independent set complex and the other is the β -invariant of a matroid. We will demonstrate various applications of this formula including a "matroid theoretic" derivation of Kalai's simplicial tree-numbers of a standard simplex.

The development of peptidomimetic foldamers that can form well-defined folded structures is highly desirable yet challenging. We previously reported on &alpha, ABpeptoids, oligomers of N-alkylated &beta, 2-homoalanines and found that due to the presence of chiral methyl groups at &alpha, positions, &alpha, ABpeptoids were shown to adopt folding conformations. Here, we report &beta, ABpeptoids having chiral methyl group at &beta, positions rather than &alpha, positions as a different class of peptoids with backbone chirality. We developed a facile solid-phase synthetic route that enables the synthesis of &beta, ABpeptoid oligomers ranging from 2-mer to 8-mer in excellent yields. These oligomers were shown to adopt ordered folding conformations based on circular dichroism (CD) and NMR studies. Overall, these results suggest that &beta, ABpeptoids represent a novel class of peptidomimetic foldamers that will find a wide range of applications in biomedical and material sciences.

A novel submonomer solid-phase synthetic method for α-ABpeptoid oligomers is reported. Iterative submonomer coupling and Fukuyama-Mitsunobu alkylation enable facile, divergent synthesis of α-ABpeptoid oligomers substituted with chemically diverse side chains in excellent yields.

A new class of peptoid-based peptidomimetics composed of oligomers of N-substituted β(2)-homoalanines is reported. Design, solid-phase synthesis, and preliminary circular dichroism studies of oligomers of N-alkylated β(2)-homoalanines consisting of up to 8-mers are described.