Search

One of the most simple facts of combinatorial topology is that the subposet P n , k m = { A ⊆ [ m ] : 1 ≤ k ≤ card (A) ≤ n < m } of B m is homotopy equivalent to a wedge of spheres. In this paper, we determine the homotopy type of an other subposet C m , n of B m induced by 'tight' n-subset of [m]. As we will see, this complex is precisely the neighborhood complex of the circular complete graphs K p q for the right choice of parameters. Finally, we investigate the power of Lovász's lower bound for the chromatic number of the graph K p q using this result. [ABSTRACT FROM AUTHOR]

Hypergraph, as a generalization of the notions of graph and simplicial complex, has gained a lot of attention in many fields. It is a relatively new mathematical model to describe the high-dimensional structure and geometric shapes of data sets. In this paper,we introduce the neighborhood hypergraph model for graphs and combine the neighborhood hypergraph model with the persistent (embedded) homology of hypergraphs. Given a graph,we can obtain a neighborhood complex introduced by L. Lovász and a filtration of hypergraphs parameterized by aweight function on the power set of the vertex set of the graph. Theweight function can be obtained by the construction fromthe geometric structure of graphs or theweights on the vertices of the graph. We show the persistent theory of such filtrations of hypergraphs. One typical application of the persistent neighborhood hypergraph is to distinguish the planar square structure of cisplatin and transplatin. Another application of persistent neighborhood hypergraph is to describe the structure of small fullerenes such as C20. The bond length and the number of adjacent carbon atoms of a carbon atom can be derived from the persistence diagram. Moreover, our method gives a highly matched stability prediction (with a correlation coefficient 0.9976) of small fullerene molecules.

We show that the dominance complex D (G) of a graph G coincides with the combinatorial Alexander dual of the neighborhood complex N (G ‾) of the complement of G. Using this, we obtain a relation between the chromatic number χ (G) of G and the homology group of D (G). We also obtain several known results related to dominance complexes from well-known facts of neighborhood complexes. After that, we suggest a new method for computing the homology groups of the dominance complexes, using independence complexes of simple graphs. We show that several known computations of homology groups of dominance complexes can be reduced to known computations of independence complexes. Finally, we determine the homology group of D (P n × P 3) by determining the homotopy types of the independence complex of P n × P 3 × P 2. [ABSTRACT FROM AUTHOR]

The neighborhood polynomial of graph G is the generating function for the number of vertex subsets of G of which the vertices have a common neighbor in G. In this paper, we investigate the behavior of this polynomial under several graph operations. Specifically, we provide an explicit formula for the neighborhood polynomial of the graph obtained from a given graph G by vertex attachment. We use this result to propose a recursive algorithm for the calculation of the neighborhood polynomial. Finally, we prove that the neighborhood polynomial can be found in polynomial-time in the class of k-degenerate graphs.

In this article, we consider the bipartite graphs K 2 × K n. We prove that the connectedness of the complex Hom (K 2 × K n , K m) is m − n − 1 if m ≥ n and m − 3 in all the other cases. Therefore, we show that for this class of graphs, Hom (G , K m) is exactly (m − d − 2) -connected, m ≥ n , where d is the maximal degree of the graph G. [ABSTRACT FROM AUTHOR]

Any graph G with chromatic number k can be obtained using a Haj'os-type construction, i.e., by iteratively performing the Haj'os merge and vertex identification operations on a sequence of graphs starting with Kk. Finding such constructions for a given graph or family of graphs is a challenging task. In this paper, we show that for a large class of Haj'os merges and for any identification of a pair of vertices having distance at least five from each other, the resulting graph has an S1-wedge summand in its neighborhood complex. Our results imply that for a bridgeless graph G with a highly connected neighborhood complex, the final step in a Haj'os construction must be a vertex identification with vertices at short distance from each other. We investigate this restriction in detail. We also introduce two graph construction algorithms using Hajos-type operations. We discuss the results of computational experiments in which we investigate the rank of the first homology group of the neighborhood complexes of graphs generated using these algorithms. [ABSTRACT FROM AUTHOR]

The neighborhood complex of a graph is the family of subsets of open neighborhoods of its vertices. The neighborhood polynomial is the ordinary generating function for the number of sets of the neighborhood complex with respect to their cardinality. This paper provides a new representation of the neighborhood polynomial as a sum over complete bipartite subgraphs of a graph. Using the close relation between the domination polynomial and the neighborhood polynomial of a graph, we can also give a new presentation of the domination polynomial. Finally we show that finding the number of certain double cliques of a graph is sufficient to determine the number of dominating sets of a graph. [ABSTRACT FROM AUTHOR]

We introduce a model structure on the category of graphs, which is Quillen equivalent to the category of Z2-spaces. A weak equivalence is a graph homomorphism which induces a Z2- homotopy equivalence between their box complexes. The box complex is a Z2-space associated to a graph, considered in the context of the graph coloring problem. In the proof, we discuss the universality problem of the Hom complex. [ABSTRACT FROM AUTHOR]

In 2003, A. Björner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SGn,k is homotopy equivalent to a k-sphere. Further, for n = 2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the neighborhood complex of SGn,k contains as a deformation retract the boundary complex of a simplicial polytope. Our purpose is to give a positive answer to this question in the case k = 2. We also find in this case that, after partially subdividing the neighborhood complex, the resulting complex deformation retracts onto a subcomplex arising as a polyhedral boundary sphere that is invariant under the action induced by the automorphism group of SGn,2. [ABSTRACT FROM AUTHOR]

Abstract: We consider a variety of connections between threshold graphs, shifted complexes, and simplicial complexes naturally formed from a graph. These graphical complexes include the independent set, neighborhood, and dominance complexes. We present a number of structural results and relations among them including new characterizations of the class of threshold graphs. [Copyright &y& Elsevier]

Abstract: In this paper we provide concrete combinatorial formal deformation algorithms, namely sequences of elementary collapses and expansions, which relate various previously extensively studied families of combinatorially defined polyhedral complexes. To start with, we give a sequence of elementary collapses leading from the barycentric subdivision of the neighborhood complex to the Lovász complex of a graph. Then, for an arbitrary lattice we describe a formal deformation of the barycentric subdivision of the atom crosscut complex to its order complex . We proceed by proving that the complex of sets bounded from below can also be collapsed to . Finally, as a pinnacle of our project, we apply all these results to certain graph complexes. Namely, by describing an explicit formal deformation, we prove that, for any graph G, the neighborhood complex and the polyhedral complex have the same simple homotopy type in the sense of Whitehead. [Copyright &y& Elsevier]

In 2002, Björner and de Longueville showed the neighborhood complex of the 2-stable Kneser graph K G (n , k) 2 − s t a b has the same homotopy type as the (n − 2 k) -sphere. A short time ago, an analogous result about the homotopy type of the neighborhood complex of almost s -stable Kneser graph has been announced by the second author. Combining this result with the famous Lovász's topological lower bound on the chromatic number of graphs yielded a new way for determining the chromatic number of these graphs which was determined a bit earlier by Chen. In this paper we present a common generalization of the mentioned results. For given an integer vector s → = (s 1 , ... , s k) , first we define s → -stable Kneser graph K G (n , k) s → − s t a b as an induced subgraph of the Kneser graph K G (n , k). Then, we show that the neighborhood complex of K G (n , k) s → − s t a b has the same homotopy type as the n − ∑ i = 1 k − 1 s i − 2 -sphere for some specific values of the parameter s →. In particular, this implies that χ K G (n , k) s → − s t a b = n − ∑ i = 1 k − 1 s i for those parameters. Moreover, as a simple corollary of this result, we give a lower bound on the chromatic number of 3-stable Kneser graphs which is just one less than the number conjectured in this regard. [ABSTRACT FROM AUTHOR]

In this article, we derive two spectral gap bounds for the reduced Laplacian of a general simplicial complex. Our two bounds are proven by comparing a simplicial complex in two different ways with a larger complex and with the corresponding clique complex respectively. Both of these bounds generalize the result of Aharoni et al. (2005) [1] which is valid only for clique complexes. As an application, we investigate the thresholds for vanishing of cohomology of the neighborhood complex of the Erdös-Rényi random graph. We improve the upper bound derived in Kahle (2007) [12] by a logarithmic factor using our spectral gap bounds and we also improve the lower bound via finer probabilistic estimates than those in Kahle (2007) [12]. [ABSTRACT FROM AUTHOR]