# A Note on the Warmth of Random Graphs with Given Expected Degrees

Authors: Yilun Shang
Journal: International Journal of Mathematics and Mathematical Sciences
 (2014)

---

## Abstract

We consider the random graph modelG
(
w
) for a given expected degree sequence w
=
(
w
1
,
w
2
,
…
,
w
n
). 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 G
(
w
). 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 m
=
O
(
n
α
) with 0
<
α
<
1
/
2.


---

## Body

## 1. Introduction

LetG
=
(
V
(
G
)
,
E
(
G
)
) be a graph with vertex set V
(
G
) and edge set E
(
G
). For graphs H and G, a function ϕ
:
V
(
H
)
→
V
(
G
) is said to be a graph homomorphism [1] if it induces a map between edges E
(
H
)
→
E
(
G
). Denote by Hom
(
H
,
G
) the set of all homomorphisms of a graph H to a graph G. Let T
d denote the d-branching rooted tree (with the root having degree d); see Figure 1 for an illustration. A map ϕ in Hom
(
T
d
,
G
) is said to be cold if there is a vertex v of G such that for any k no ψ
∈
Hom
(
T
d
,
G
) agrees with ϕ on the vertices at distance k from the root r but has ψ
(
r
)
=
v. We say that G is d-warm if Hom
(
T
d
-
2
,
G
) does not contain any cold maps. Moreover, the warmth, warmth
(
G
), of G  is defined to be the largest d for which G is d-warm. By definition, for any finite and connected graph G, warmth
(
G
)
≥
2 and warmth
(
G
)
=
2 if and only if G  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 G  the warmth of G 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 G
(
w
). For a given sequence w
=
(
w
1
,
w
2
,
…
,
w
n
), G
(
w
) is defined as follows. Each potential edge between vertices v
i and v
j is chosen with probability p
i
j and is independent of other edges, where
(1)
p
i
j
=
w
i
w
j
∑
k
=
1
n
w
k
.
Here, we assume that w
max
⁡
2
=
max
⁡
i
w
i
2
<
∑
k
=
1
n
‍
w
k and define n
d
=
∑
k
=
1
n
‍
w
k. An immediate consequence of (1) is that the expected degree at a vertex v
i is exactly w
i  [7]. Hence, d  is the expected average degree.This model, known as the Chung-Lu model, was first proposed in [8]. The classical Erdös-Rényi random graph G
(
n
,
p
) can be viewed as a special case of G
(
w
) by taking expected degree sequence w
=
(
p
n
,
p
n
,
…
,
p
n
). Many graph properties, such as component structure [8, 9], average distance [10], hyperbolicity [11], and spectral gap [12–14], have been explored for this model. We refer the reader to monograph [7] for detailed backgrounds and varied related results.The rest of the note is organized as follows. We state and discuss the upper and lower bounds for warmth in Section2. Section 3 contains the proofs. A brief conclusion is drawn in Section 4.


## 2. Main Results

In this section we establish our main results for upper and lower bounds. We say an event holds asymptotically almost surely (a.a.s.), if it holds with probability tending to 1 asn
→
∞. The asymptotics o, O, Ω, and Θ are used in their standard sense [15]. For example, let f
(
n
) and g
(
n
) be two sequences of positive real numbers. Consider f
(
n
)
=
o
(
g
(
n
)
) means lim
⁡
n
→
∞
f
(
n
)
/
g
(
n
)
=
0; consider f
(
n
)
=
O
(
g
(
n
)
) means that there exists some constant C
>
0 such that f
(
n
)
≤
C
g
(
n
) for all large enough n; consider f
(
n
)
=
Ω
(
g
(
n
)
) means that there exists some constant C
>
0 such that f
(
n
)
≥
C
g
(
n
) for all large enough n; consider f
(
n
)
=
Θ
(
g
(
n
)
) means that there exists some constant C
>
0 such that C
-
1
≤
f
(
n
)
/
g
(
n
)
≤
C for all large enough n.For a sparse random graphG
(
w
), we may upper bound its warmth using minimum expected degree.Theorem 1 (upper bound).
For a random graphG
∈
G
(
w
), suppose the maximum expected degree w
max
⁡
=
m
=
O
(
n
α
) with 0
<
α
<
1
/
2 and the minimum expected degree w
min
⁡
=
ω
(
n
)
→
∞ as n
→
∞. Then, for 0
<
δ
<
1, one has
(2)
w
a
r
m
t
h

(
G
)
≤
(
1
-
δ
)
ω
(
n
)
+
1
a
.
a
.
s
.The authors in [5, Theorem 3.1] showed that, for sparse Erdös-Rényi random graph G
(
n
,
p
) with p
=
O
(
n
-
α
) for some α
>
0, warmth
(
G
(
n
,
p
)
)
≤
⌊
1
/
α
+
2
⌋ a.a.s. On the other hand, it is well known that [4, 16] the chromatic number χ
(
G
(
n
,
p
)
) in this regime tends to infinity a.a.s. Therefore, the warmth of G
(
n
,
p
) is much smaller than its chromatic number.Our Theorem1, nevertheless, provides an example where warmth may be close to chromatic number. To see this, we choose w
min
⁡
=
n
α
/
ln
⁡
n, d
=
Θ
(
n
α
), and α
<
1
/
4. The main result in [17] then concludes that (in a slightly different formulation, where precise degrees rather than expected degrees are specified) the chromatic number χ
(
G
(
w
)
)
=
Θ
(
d
/
ln
⁡
d
)
=
Θ
(
n
α
/
ln
⁡
n
) a.a.s. On the other hand, Theorem 1 yields a comparable upper bound warmth
(
G
)
≤
(
1
-
δ
)
(
n
α
/
ln
⁡
n
)
+
1.For dense random graphs, we have the following lower bound.Theorem 2 (lower bound).
For a random graphG
∈
G
(
w
), suppose w
i
2
/
n
d
=
Θ
(
1
) for any 1
≤
i
≤
n. Then, for 0
<
δ
<
1 and c
≥
2, one has
(3)
w
a
r
m
t
h

(
G
)
≥
(
1
-
δ
)
ln
⁡
c
n
a
.
a
.
s
.We remark that the above result implies Theorem 3.4 in [5] when c
=
2 and w
1
=
⋯
=
w
n
=
n
/
2. In view of [2, Theorem 5.1] (as mentioned in Section 1), Theorem 2 provides an alternative approach to obtaining lower bounds for χ
(
G
(
w
)
).


## 3. Proofs

For a graphH, let δ
(
H
) denote the minimum degree of H. For a vertex v
∈
V
(
H
), the neighborhood of v is denoted by N
(
v
), and, for a subset A
⊂
V
(
H
), the neighborhood of A is defined as N
(
A
)
=
∪
v
∈
A
N
(
v
). A collection {
A
i
}
i
=
1
k of subsets of H is called a d-stable family if for any 1
≤
i
≤
k there are A
i
1
,
…
,
A
i
d
⊂
V
(
H
) such that ∩
j
=
1
d
N
(
A
i
j
)
=
A
i.We will need the following lemma to prove Theorem1.Lemma 3 (see [2]).
Given a graphH and a natural number d
≥
1, H is not (
d
+
2
)-warm if and only if there is a d-stable family of subsets of H.Proof of Theorem1.
Sinceω
(
n
)
→
∞, for 0
<
δ
<
1, we have P
(
δ
(
G
)
≥
(
1
-
δ
/
2
)
ω
(
n
)
)
→
1 as n
→
∞ using a concentration inequality [7]. Set s
=
(
1
-
δ
)
ω
(
n
). We will prove that warmth
(
G
)
≤
s
+
1.
Now considerV
(
G
) consisting of all singleton vertices of G. A vertex set {
v
1
,
…
,
v
s
} is called an s-representative [5] of v
∈
V
(
G
) if v
1
,
…
,
v
s
∈
N
(
v
) such that all of them are not in the neighborhood N
(
u
) for any vertex u
≠
v. Therefore, by Lemma 3, it suffices to prove that every vertex v has an s-representative.
Supposev
1
,
…
,
v
s
∈
N
(
v
). Let A
(
v
)
(
v
1
,
…
,
v
s
) denote the event that v
1
,
…
,
v
s are in the neighborhood N
(
v
) of v. Hence,
(4)
P
(
A
(
v
i
)
(
v
1
,
…
,
v
s
)
for
some
v
i
∈
V
(
G
)
)
≤
∑
v
i
∈
V
(
G
)
‍
P
(
A
(
v
i
)
(
v
1
,
…
,
v
s
)
)
=
∑
v
i
∈
V
(
G
)
‍
∏
j
=
1
s
‍
p
i
j
=
∑
v
i
∈
V
(
G
)
‍
w
i
s
∏
j
=
1
s
w
j
(
n
d
)
s
=
∑
i
=
1
n
w
i
s
∏
j
=
1
s
w
j
(
n
d
)
s
≤
∑
i
=
1
n
w
i
s
m
s
(
n
d
)
s
.
Recall that|
N
(
v
)
|
≥
(
1
-
δ
/
2
)
ω
(
n
) as shown in the beginning of the proof. Let γ
=
⌊
(
1
-
δ
/
2
)
/
(
1
-
δ
)
⌋ and N
1
,
…
,
N
γ be some disjoint subsets of the neighbors of v  with |
N
i
|
=
s for 1
≤
i
≤
γ. For M
⊂
N
(
v
) and |
M
|
=
s, denote by A
(
M
) the event that M
⊂
N
(
u
) for some u
≠
v. Therefore, the disjointness and inequality (4) imply
(5)
P
(
⋂
|
M
|
=
s
,
M
⊂
N
(
v
)
A
(
M
)
)
≤
P
(
⋂
i
=
1
γ
A
(
N
i
)
)
≤
(
∑
i
=
1
n
w
i
s
)
γ
m
s
γ
(
n
d
)
s
γ
.
Thus, the probability that some vertex does not have an s-representative is bounded from above by
(6)
∑
v
∈
V
‍
(
(
∑
i
=
1
n
w
i
s
)
γ
m
s
γ
(
n
d
)
s
γ
)
=
n
(
∑
i
=
1
n
w
i
s
)
γ
m
s
γ
(
n
d
)
s
γ
=
O
(
m
2
γ
s
n
1
+
γ
-
γ
s
)
,
which tends to zero since m
=
O
(
n
α
) with 0
<
α
<
1
/
2 and s
→
∞. This completes the proof of Theorem 1.Proof of Theorem2.
Sets
=
(
1
-
δ
)
ln
⁡
a
n
-
2. By definition, we need to prove that Hom
(
T
s
,
G
) contains no cold maps.
In what follows, we proceed with the similar lines of reasoning of Section 5 in [5]. We label the vertices of s-branching rooted tree T
s according to Figure 1 with the root labeled 0 and its children 1,2
,
…, sequently.
LetT
v
s denote the truncated version of s-branching rooted tree T
s with v vertices, labeled 0 to v
-
1. We suppose v
≡
1
(
mod
⁡
s
) and T
v
s has m  vertices up to level k  and v
-
m vertices from level k
+
1 of  T
s, where m
=
1
+
s
+
⋯
+
s
k
-
1
=
(
s
k
-
1
)
/
(
s
-
1
). Hence, we have m
<
v
≤
s
m
+
1 and v
≡
m
≡
1
(
mod
⁡
s
). The number of leaves of T
v
s can be calculated as
(7)
l
=
v
-
m
+
s
k
-
1
-
v
-
m
s
=
(
s
-
1
)
v
+
1
s
.
The leaves are labeled as (
v
-
1
)
/
s
,
(
v
-
1
)
/
s
+
1
,
…
,
v
-
1. Denote by S
=
S
(
T
v
s
) the set of roots and leaves; that is, S
=
{
0
,
(
v
-
1
)
/
s
,
(
v
-
1
)
/
s
+
1
,
…
,
v
-
1
}.
For a graphH and a function f
:
S
→
V
(
H
), f is said to be H-extendable if there is a homomorphism ϕ
:
T
v
s
→
H such that ϕ
|
S
=
f. Hence, if every function f
:
S
→
V
(
G
) is G-extendable, then Hom
(
T
s
,
G
) contains no cold maps, and thus the proof will be complete.
Now let(8)
ϵ
=
1
-
(
1
-
δ
)
ln
⁡
c
n
-
2
ln
⁡
c
n
,
which is bounded away from 0 for large enough n. We claim the following.
Claim1.For i
∈
S
(
T
v
s
) and a
,
b
i
∈
G, the probability that a function f with f
(
0
)
=
a and f
(
i
)
=
b
i is not G-extendable is at most exp
⁡
(
-
C
n
β
) for some constants C
,
β
>
0.
Proof of Claim1.We use Janson’s inequality [15] to prove Claim 1. Note that by definition (8) the assumptions w
i
2
/
n
d
=
Θ
(
1
) for any 1
≤
i
≤
n are equivalent to
(9)
w
min
⁡
2
n
d
=
Ω
(
n
-
1
/
ln
⁡
c
n
)
=
Ω
(
n
-
(
1
-
ϵ
)
/
s
)
,
(10)
w
max
⁡
2
n
d
=
O
(
n
-
1
/
ln
⁡
c
n
)
=
O
(
n
-
(
1
-
ϵ
)
/
s
)
.
Let{
c
j
}
=
f
(
S
∖
{
a
,
b
i
}
)
⊂
V
(
G
). Then, from (9) and (10), the probability that there does not exist such a ϕ for a particular choice of {
a
,
b
i
,
c
j
} is at most 1
-
Ω
(
n
-
(
1
-
ϵ
)
(
v
-
1
)
/
s
) and at least 1
-
O
(
n
-
(
1
-
ϵ
)
(
v
-
1
)
/
s
).
Let(11)
A
=
{
A
is
an
induced
subgraph
of
G
∣
|
V
(
A
)
|
=
v
-
l
-
1
,
V
(
A
)
∩
{
a
,
b
i
}
=
∅
}
.
We have |
A
|
=
(
n
-
l
-
1
v
-
l
-
1
). For A
i
∈
A, denote by {
c
1
i
,
…
,
c
v
-
l
-
1
i
} the set of vertices of A
i ordered according to its labeling. Denote by B
i the event that ϕ governed by c
j
=
c
j
i is a homomorphism. Hence, the above discussion implies
(12)
P
(
B
-
i
)
=
1
-
Θ
(
n
-
(
1
-
ϵ
)
(
v
-
1
)
/
s
)
,
where B
-
i denotes the complement of the event B
i.
LetA
′ be a subgraph of G induced by V
(
A
)
∪
{
a
,
b
i
}. Let i
~
j mean that the edges of A
i
′ and A
j
′ have a nontrivial intersection. We apply Janson’s inequality [15] and (12) to get
(13)
P
(
⋂
i
B
-
i
)
≤
exp
⁡
(
-
μ
+
Δ
min
⁡
i
P
(
B
-
i
)
)
≤
exp
⁡
(
-
μ
+
Δ
1
-
Θ
(
n
-
(
1
-
ϵ
)
(
v
-
1
)
/
s
)
)
,
where μ
=
∑
i
‍
P
(
B
i
) and Δ
=
∑
i
~
j
‍
P
(
B
i
∩
B
j
).
From (9) and (12) we have
(14)
μ
=
Θ
(
n
v
-
l
-
1
n
(
1
-
ϵ
)
(
v
-
1
)
/
s
)
=
Θ
(
n
-
1
+
(
ϵ
(
v
-
1
)
/
s
)
)
.
To estimate Δ, we denote by g
k
=
max
⁡
i
,
j
{
|
E
(
A
i
′
∩
A
j
′
)
|
∣
|
V
(
A
i
∩
A
j
)
|
=
k
} the maximum over all pairs i
,
j of the number of edges that A
i and A
j intersect in k vertices. Since the edge sets of A
i
′ and A
j
′ have a nontrivial intersection, we get k
≥
1. Hence by (10)
(15)
P
(
B
i
∩
B
j
)
≤
(
w
max
⁡
2
n
d
)
2
(
v
-
1
)
-
g
k
=
O
(
n
-
(
1
-
ϵ
)
(
2
(
v
-
1
)
-
s
k
)
/
s
)
,
since g
k
≤
s
k. Noting that there are (
n
-
l
-
1
k
)
(
n
-
l
-
1
-
k
v
-
l
-
1
-
k
)
(
n
-
l
-
1
-
v
+
l
+
1
v
-
l
-
1
-
k
)
=
O
(
n
2
v
-
2
l
-
2
-
k
) such pairs of A
i and A
j, we obtain
(16)
Δ
=
∑
k
=
1
v
-
l
-
1
‍
O
(
n
2
v
-
2
l
-
2
-
k
n
-
(
1
-
ϵ
)
(
2
(
v
-
1
)
-
s
k
)
/
s
)
=
O
(
n
-
2
+
(
ϵ
/
s
)
(
2
v
-
s
-
2
)
)
.
We choosev such that v
≡
m
≡
1
(
mod
⁡
s
) and s
/
ϵ
+
1
<
v
<
s
/
ϵ
+
s
+
1. Hence, estimates (14) and (16) readily yield
(17)
Δ
1
-
Θ
(
n
-
(
1
-
ϵ
)
(
v
-
1
)
/
s
)
=
O
(
n
-
2
+
(
ϵ
/
s
)
(
2
v
-
s
-
2
)
)
=
o
(
μ
)
.
Note thatβ
=
liminf
⁡
n
→
∞
(
-
1
+
ϵ
(
v
-
1
)
/
s
)
>
0 by our choice of v. Thus, inequality (13) in conjunction with estimates (14) and (17) means that
(18)
P
(
⋂
i
B
-
i
)
≤
e
-
C
n
β
for some constant C
>
0, which then concludes the proof of the claim.
Since there are at mostn
l
+
1 choices for {
a
,
b
i
}, the probability that a homomorphism ϕ (with ϕ
|
S
=
f) does not exist for at least one choice is at most n
l
+
1
exp
⁡
(
-
C
n
β
), which tends to zero as n
→
∞. Consequently, with probability one, every map f
:
S
(
T
v
s
)
→
V
(
G
) is G-extendable for some v. The proof of Theorem 2 is then complete.


## 4. Conclusion

In this paper we presented upper and lower bounds for the warmth of random graphs with given expected degrees. Our results indicate that the warmth of a typical dense graph is smaller than (but can be rather close to) its chromatic number, shedding some insight on the universal upper boundwarmth
(
G
)
≤
χ
(
G
). It is worth noting that Fadnavis and Kahle [5] showed that a typical sparse graph has much smaller warmth than chromatic number.We mention that the degree distributions of the random graph models studied in this paper and [5] are more or less homogeneous (namely, Poisson-like). It would be interesting to know the behavior of warmth for heterogeneously connected graphs or digraphs [18–20], which are ubiquitous in real-world systems and investigate further the influence of maximum/minimum degrees on the warmth as hinted in Theorem 1.



---

*Source: 749856-2014-06-30.xml*