The neighborhood complex of a random graph

DOI10.1016/J.JCTA.2006.05.004zbMATH Open1110.05090arXivmath/0512077OpenAlexW2081808419MaRDI QIDQ868889FDOQ868889

Authors: Matthew Kahle 

Publication date: 26 February 2007

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

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.

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

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

zbMATH Keywords

coloringmorphism complexes

Mathematics Subject Classification ID

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

Cites Work

• Topology of random clique complexes
• Paths in graphs
• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• Homological connectivity of random 2-complexes
• Hom complexes and homotopy theory in the category of graphs
• Complexes of graph homomorphisms
• Box complexes, neighborhood complexes, and the chromatic number
• Topological obstructions to graph colorings

Cited In (22)

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