The neighborhood complex of a random graph

DOI10.1016/J.JCTA.2006.05.004MaRDI QIDQ868889zbMATH OpenOpenAlexFDO

Authors Matthew Kahle

Publication date 26 February 2007

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0512077

zbMATH Keywords

coloringmorphism complexes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Abstract: For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well known result of Lovasz that if N[G] is k-connected, then the chromatic number of G is at least k + 3. We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(log d), compared to the expected dimension d of the complex itself.

Recommendations

• Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
• The concentration of the chromatic number of random graphs
• On the chromatic number of random graphs
• Topology of random clique complexes
• The chromatic number of random graphs for most average degrees

Cites work

• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• Box complexes, neighborhood complexes, and the chromatic number
• Complexes of graph homomorphisms
• Hom complexes and homotopy theory in the category of graphs
• Homological connectivity of random 2-complexes
• Kneser's conjecture, chromatic number, and homotopy
• Paths in graphs
• Topological obstructions to graph colorings
• Topology of random clique complexes

Cited in

(22)

• A social communication model based on simplicial complexes
• The threshold function for vanishing of the top homology group of random \(d\)-complexes
• Hierarchical sequencing of online social graphs
• scientific article; zbMATH DE number 1555260 (Why is no real title available?)
• Hajós-type constructions and neighborhood complexes
• The fundamental group of random 2-complexes.
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Dold's theorem from viewpoint of strong compatibility graphs
• Neighborhood hypergraph model for topological data analysis
• Topology of random clique complexes
• Warmth and edge spaces of graphs
• Homotopy types of box complexes of chordal graphs
• Homomorphism complexes and \(k\)-cores
• Generalized Borsuk graphs
• Homotopy groups of Hom complexes of graphs
• Random geometric complexes
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Spectral gap bounds for the simplicial Laplacian and an application to random complexes
• scientific article; zbMATH DE number 1369838 (Why is no real title available?)
• Persistent homology of complex networks
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs

This page was built for publication: The neighborhood complex of a random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868889)