Neighborhood complex

At the low end of the hierarchy are the TS descriptors. This is the simplest of the four classes molecular structure is viewed only in terms of atom connectivity, not as a chemical entity, and thus no chemical information is encoded. Examples include path length descriptors [13], path or cluster connectivity indices [13,14], and number of circuits. The TC descriptors are more complex in that they encode chemical information, such as atom and bond type, in addition to encoding information about how the atoms are connected within the molecule. Examples of TC descriptors include neighborhood complexity indices [23], valence path connectivity indices [13], and electrotopological state indices [17]. The TS and TC are two-dimensional descriptors which are collectively referred to as TIs (Section 31.2.1). They are straightforward in their derivation, uncomplicated by conformational assumptions, and can be calculated very quickly and inexpensively. The 3-D descriptors encode 3-D aspects of molecular structure. At the upper end of the hierarchy are the QC descriptors, which encode electronic aspects of chemical structure. As was mentioned previously, QC descriptors may be obtained using either semiempirical or ab initio calculation methods. The latter can be prohibitive in terms of the time required for calculation, especially for large molecules. 

Basak, S.C. (2000). Information Theoretic Indices of Neighborhood Complexity and Their Applications. In Topological Indices and Related Descriptors in QSAR and QSPR (Devillers, J. and Balaban, A.T., eds.), Gordon Breach, Amsterdam (The Netherlands), pp. 563-593. 

Basak, S.C. (1999) Information theoretic indices of neighborhood complexity and their applications, in... 

Roy, A.B., Basak, S.C., Harriss, D.K. and Magnuson, V.R. (1984) Neighborhood complexities and symmetry of chemical graphs and their biological applications, in Mathematical Modelling in Science and Technology (eds X.J.R. Avula, R.E. Kalman, A.l. Liapis and E.Y. Rodin), Pergamon Press, New York, pp. 745-750. 

S. Basak. Information theoretic indices of neighborhood complexity and their applications. In J. Devillers and A. Balaban, editors. Topological Indices and Related Descripors in QSAR and QSPR, chapter 12. Gordon and Breach, Amsterdam, 1999. 

The neighborhood complex of a graph is an example in which this dual description is not useful. On the other hand, the matroid complex is an example in which both descriptions are frequently used, depending on the circumstances. The dual presentation in this case uses the term circuits, which play the role of the minimal nonsimplices, and goes as follows. 

Proposition 13.16 was proved by the author in [Ko06c], though the fact that the neighborhood complex is homotopy equivalent to the Lovasz complex was well known before that. Theorem 13.18 was also proved by the author in [Ko06cj. 

Recall that in Subsection 9.1.4, more precisely in Definition 9.9, to an arbitrary graph G we have associated an abstract simplicial complex, called the neighborhood complex, which we denoted by J f G). Note that when A C V G) is a simplex of A/"(G), then so is N A). However, mapping A to N A) would not give a simplicial map from N G) to itself. Instead, we need to proceed to the face poset of Af G), which in our notation is called F Af G)). 

Lovasz has introduced the neighborhood complex N G) as a part of his topological approach to the resolution of the Kneser conjecture. The hard part of the proof is to show the inequality x En,k) > n — 2k + 2, and Lovasz s idea was to use the connectivity information of the topological space Af G) to find obstructions to the vertex-colorability of G. More precisely, he proved the following statement. 

To finish the proof of the Kneser conjecture (Theorem 17.21), we still need to see that the neighborhood complex of Kneser graphs is sufficiently connected. In fact, it turns out that the homotopy type of these complexes can be determined precisely. 

By Theorem 18.3 we can replace the neighborhood complexes M KGnk) by the Horn complexes Bip KG k) as far as the homotopy type is concerned. Again, we define an order-preserving map... 

Proof. We shall satisfy ourselves here with proving a weaker statement, finding G such that Bip(G) is homotopy equivalent to X. To start with, since Bip (G) is homotopy equivalent to M G), we can deal with the neighborhood complex instead. 

Let us now consider the graph associated to the barycentric subdivision of X. In our notation, this graph is called Gbux- We claim that the neighborhood complex of this graph Af GBdx) is homotopy equivalent to BdX, and... 

Consider the so-called closed star covering of Bd X, that is, its covering by all closed stars of its vertices. A subset of these stars has a nonempty intersection if and only if it contains a vertex, which means that there is a vertex that is connected with the centers of all these stars, and possibly coincides with one of them. Therefore, we see that the nerve of this covering coincides with the neighborhood complex Af G-Bdx)- To prove the homotopy equivalence we will show that whenever a set of these stars has a nonempty intersection, then it must be contractible, and then invoke Theorem 15.21. 

As mentioned above, Horn complexes were introduced as a one parameter expansion of the family of neighborhood complexes. The next theorem makes this statement precise. 

Theorem 18.3. For an arbitrary graph G, the neighborhood complex M G) and the polyhedral complex Bip (G) have the same simple homotopy type. 

The discussion in Section 6.5 implies now that the polyhedral complex of all bipartite subgraphs of G, Bip(G), and the neighborhood complex Af G), have the same simple homotopy type, and yields an explicit formal deformation between these two complexes. ... 

Theorem 18.3 was proved in [Ko06c]. That the neighborhood complex N G) is homotopy equivalent to Bip (G) was known earlier see, e.g., [BK06] for an argument. 

We have seen in Theorem 18.3 that the complex Bip (G) has the same simple homotopy type as the neighborhood complex of G. In particular, the complex Bip (Kn) is homotopy equivalent to the sphere S . The following proposition summarizes more complete information. 

Ko06c] D.N. Kozlov, Simple homotopy types of Horn-complexes, neighborhood complexes, Lovdsz complexes, and atom crosscut complexes. Topology and its Appl. 153 (2006), no. 14, 2445-2454. 

---