We consider the random graph model for a given expected degree sequence . Warmth, introduced by Brightwell and Winkler in the context of combinatorial statistical mechanics, is a graph parameter related to lower bounds of chromatic number. We present new upper and lower bounds on warmth of . In particular, the minimum expected degree turns out to be an upper bound of warmth when it tends to infinity and the maximum expected degree with . 1. Introduction Let be a graph with vertex set and edge set . For graphs and , a function is said to be a graph homomorphism [1] if it induces a map between edges . Denote by the set of all homomorphisms of a graph to a graph . Let denote the -branching rooted tree (with the root having degree ); see Figure 1 for an illustration. A map in is said to be cold if there is a vertex of such that for any no agrees with on the vertices at distance from the root but has . We say that is -warm if does not contain any cold maps. Moreover, the warmth, , of ？is defined to be the largest for which is -warm. By definition, for any finite and connected graph , and if and only if ？is bipartite. Figure 1: The labeling of vertices for the 3-branching rooted tree. Warmth is a graph parameter introduced by Brightwell and Winkler [2] in the context of combinatorial statistical physics. It is closely related to the chromatic number of a graph, which is the smallest positive integer that is not a root of the chromatic polynomial (see, e.g., [3]). It was shown that [2, Theorem 5.1] for any unlooped graph ？the warmth of is at most its chromatic number. A natural question to ask would be what the warmth of a graph looks like in a typical graph or random graphs ？[4]. Recently, Fadnavis and Kahle ？[5] established some upper and lower bounds for Erd？s-Rényi random graphs as well as random regular graphs. The main finding is that warmth is often much smaller than chromatic number for random graphs. We mention that most of the parameters examined in random graph theory are monotone with respect to the addition (or deletion) of edges [4, 6]. However, warmth is not such a parameter, which makes it difficult to study in random graph settings. In this paper, motivated by the work of [5], we study the upper and lower bounds of warmth in a general random graph model . For a given sequence , is defined as follows. Each potential edge between vertices and is chosen with probability and is independent of other edges, where Here, we assume that and define . An immediate consequence of (1) is that the expected degree at a vertex is exactly ？[7]. Hence, ？is the
References
[1]
P. Hell and J. Ne？et？il, Graphs and Homomorphisms, vol. 28, Oxford University Press, Oxford, UK, 2004.
[2]
G. R. Brightwell and P. Winkler, “Graph homomorphisms and long range action,” in Graphs, Morphisms and Statistical Physics, pp. 29–48, American Mathematical Society, Providence, RI, USA, 2004.
[3]
Y. Shang, “A remark on the chromatic polynomials of incomparability graphs of posets,” International Journal of Pure and Applied Mathematics, vol. 67, no. 2, pp. 159–164, 2011.
[4]
B. Bollobas, Random Graphs, Cambridge University Press, Cambridge, UK, 2001.
[5]
S. Fadnavis and M. Kahle, “Warmth and mobility of random graphs,” http://arxiv.org/abs/1009.0792.
[6]
E. Friedgut and G. Kalai, “Every monotone graph property has a sharp threshold,” Proceedings of the American Mathematical Society, vol. 124, no. 10, pp. 2993–3002, 1996.
[7]
F. Chung and L. Lu, Complex Graphs and Networks, American Mathematical Society, Boston, Mass, USA, 2006.
[8]
F. Chung and L. Lu, “Connected components in random graphs with given expected degree sequences,” Annals of Combinatorics, vol. 6, no. 2, pp. 125–145, 2002.
[9]
F. Chung and L. Lu, “The volume of the giant component of a random graph with given expected degrees,” SIAM Journal on Discrete Mathematics, vol. 20, no. 2, pp. 395–411, 2006.
[10]
F. Chung and L. Lu, “The average distance in a random graph with given expected degrees,” Internet Mathematics, vol. 1, no. 1, pp. 91–113, 2003.
[11]
Y. Shang, “Non- hyperbolicity of random grap hs with given expected degrees,” Stochastic Models, vol. 29, no. 4, pp. 451–462, 2013.
[12]
F. Chung, L. Lu, and V. Vu, “Eigenvalues of random power law graphs,” Annals of Combinatorics, vol. 7, no. 1, pp. 21–33, 2003.
[13]
A. Coja-Oghlan and A. Lanka, “The spectral gap of random graphs with given expected degrees,” The Electronic Journal of Combinatorics, vol. 16, article R138, 2009.
[14]
Y. Shang, “A remark on the spectra of random graphs with given expected degrees,” Journal of Discrete Mathematical Sciences & Cryptography, vol. 15, no. 6, pp. 317–321, 2012.
[15]
N. Alon and J. H. Spencer, The Probabilistic Method, John Wiley and Sons, Hoboken, NJ, USA, 2008.
[16]
N. Alon and M. Krivelevich, “The concentration of the chromatic number of random graphs,” Combinatorica, vol. 17, no. 3, pp. 303–313, 1997.
[17]
A. Frieze, M. Krivelevich, and C. Smyth, “On the chromatic number of random graphs with a fixed degree sequence,” Combinatorics, Probability and Computing, vol. 16, no. 5, pp. 733–746, 2007.
[18]
Y. Shang, “Multi-type directed scale-free percolation,” Communications in Theoretical Physics, vol. 57, no. 4, pp. 701–716, 2012.
[19]
Y. Shang, “Large dicliques in a directed inhomogeneous random graph,” International Journal of Computer Mathematics, vol. 90, no. 3, pp. 445–456, 2013.
[20]
Y. Shang, “The natural connectivity of colored random graphs,” Creative Mathematics and Informatics, vol. 20, no. 2, pp. 197–202, 2011.
