Homomorphism complexes and \(k\)-cores. (English) Zbl 1392.05056
Summary: For any fixed graph \(G\), we prove that the topological connectivity of the graph homomorphism complex \(\mathrm{Hom}(G, K_m)\) is at least \(m - D(G) - 2\), where \(D(G) = \max_{H \subseteq G} \delta(H)\), for \(\delta(H)\) the minimum degree of a vertex in a subgraph \(H\). This generalizes a theorem of S. L. Čukić and D. N. Kozlov [Discrete Comput. Geom. 36, No. 2, 313–329 (2006; Zbl 1103.55003)], in which the maximum degree \(\varDelta(G)\) was used in place of \(D(G)\), and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, \(\chi(G) \leq D(G) + 1\), as \(\chi(G) = \min \{m : \mathrm{Hom}(G, K_m) \neq \emptyset \}\). Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom\((G(n, p), K_m)\) when \(p = c/n\) for a fixed constant \(c > 0\).
MSC:
| 05C30 | Enumeration in graph theory |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 55P10 | Homotopy equivalences in algebraic topology |
| 57M15 | Relations of low-dimensional topology with graph theory |
Citations:
Zbl 1103.55003References:
| [1] | Achlioptas, Dimitris; Friedgut, Ehud, A sharp threshold for \(k\)-colorability, Random Structures Algorithms, 14, 1, 63-70, (1999) · Zbl 0962.05055 |
| [2] | Babson, Eric; Kozlov, Dmitry N., Complexes of graph homomorphisms, Israel J. Math., 152, 285-312, (2006) · Zbl 1205.52009 |
| [3] | Cereceda, Luis; Heuvel, Jan van den; Johnson, Matthew, Mixing 3-colourings in bipartite graphs, European J. Combin., 30, 7, 1593-1606, (2009) · Zbl 1198.05040 |
| [4] | Coja-Oghlan, Amin; Vilenchik, Dan, Chasing the \(k\)-colorability threshold, (2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, (2013), IEEE Computer Soc. Los Alamitos, CA), 380-389 |
| [5] | Csorba, Peter, Non-tidy spaces and graph colorings, (2005), ETH Zürich, (Ph.D. thesis) |
| [6] | Čukić, Sonja Lj; Kozlov, Dmitry N., Higher connectivity of graph coloring complexes, Int. Math. Res. Not. IMRN, 25, 1543-1562, (2005) · Zbl 1077.05038 |
| [7] | Čukić, Sonja Lj; Kozlov, Dmitry N., The homotopy type of complexes of graph homomorphisms between cycles, Discrete Comput. Geom., 36, 2, 313-329, (2006) · Zbl 1103.55003 |
| [8] | Engström, Alexander, A short proof of a conjecture on the connectivity of graph coloring complexes, Proc. Amer. Math. Soc., 134, 12, 3703-3705, (2006), (electronic) · Zbl 1140.57004 |
| [9] | Erdős, P.; Rényi, A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutat Int. Kzl., 5, 17-61, (1960) · Zbl 0103.16301 |
| [10] | Frieze, Alan; Pegden, Wesley, Between 2- and 3-colorability, Electron. J. Combin., 22, 1, 15, (2015), Paper 1.34 · Zbl 1307.05203 |
| [11] | Grimmett, G. R.; McDiarmid, C. J.H., On colouring random graphs, Math. Proc. Cambridge Philos. Soc., 77, 313-324, (1975) · Zbl 0297.05112 |
| [12] | Janson, Svante, Poisson convergence and Poisson processes with applications to random graphs, Stochastic Process. Appl., 26, 1, 1-30, (1987) · Zbl 0633.60070 |
| [13] | Kahle, Matthew, The neighborhood complex of a random graph, J. Combin. Theory Ser. A, 114, 2, 380-387, (2007) · Zbl 1110.05090 |
| [14] | Kozlov, Dmitry N., Cohomology of colorings of cycles, Amer. J. Math., 130, 3, 829-857, (2008) · Zbl 1198.05062 |
| [15] | Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 3, 319-324, (1978) · Zbl 0418.05028 |
| [16] | Molloy, Michael, A gap between the appearances of a \(k\)-core and a \((k + 1)\)-chromatic graph, Random Structures Algorithms, 8, 2, 159-160, (1996) · Zbl 0838.05091 |
| [17] | Pittel, Boris; Spencer, Joel; Wormald, Nicholas, Sudden emergence of a giant \(k\)-core in a random graph, J. Combin. Theory Ser. B, 67, 1, 111-151, (1996) · Zbl 0860.05065 |
| [18] | Schultz, Carsten, Small models of graph colouring manifolds and the Stiefel manifolds Hom\((C_5, K_n)\), J. Combin. Theory Ser. A, 115, 1, 84-104, (2008) · Zbl 1142.05030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
