# Graphs Generated by Measures

Authors: A. Assari; M. Rahimi
Journal: Journal of Mathematics
 (2016)

---

## Abstract

In this paper, a graph is assigned to any probability measure on theσ-algebra of Borel sets of a topological space. Using this construction, it is proved that given any number n (finite or infinite) there exists a nonregular graph such that its clique, chromatic, and dominating number equals n.


---

## Body

## 1. Introduction

The distance between two vertices in a graph is the number of edges in a shortest path connecting them. Diameter of a graph is the longest path between two vertices of the graph.A clique is a subset of vertices of an undirected graph, such that its induced subgraph is complete; that is, every two distinct vertices in the clique are adjacent. Clique number of a graphΓ is the number of vertices of maximum clique in the graph and denoted by ω(Γ). The chromatic polynomial counts the number of ways a graph can be colored using no more than a given number of colors and denoted by χ(Γ).A setD⊆V of vertices in a graph Γ=(V,E) is a dominating set if every vertex v∈V is an element of D or adjacent to an element of D. The domination number γ(Γ) of a graph Γ is the minimum cardinality of a dominating set of Γ.An independent set or stable set is a set of vertices in a graph, with no two of which being adjacent. A maximum independent set is an independent set of largest possible size for a given graphΓ. This size is called the independence number of Γ and denoted α(Γ).Lots of graphs are constructed from algebraic objects such as semigroups ([1]), groups ([2, 3]), and rings ([4, 5]). Recently some graphs have been constructed from Hilbert and topological spaces ([6, 7]) which have nice graph theoretical properties. This motivates us to construct a bigger category of graphs which has more properties. In this paper, we introduce a class of graphs generated by measures. Using this construction, we conclude that, given any number n (finite or infinite), there exists a nonregular graph such that its clique, chromatic, and dominating number coincides and is equal to n.Given a measure space(X,Ω,μ), a set E∈Ω is called an atom for μ, if E has a positive measure and for every F∈Ω, either μ(E∩F) or μ(E∖F) is zero. It is easily obtained by definition that if E is an atom for μ and μ(E∩F)>0, then E∩F is also an atom for μ. μ is an atomic measure iff every measurable set of positive measure contains an atom. We may say that μ is nonatomic if there are no atoms for μ. Therefore, in a nonatomic measure μ, every nonatomic measurable set of positive measure can split into two disjoint measurable sets, where both of them have positive measure. One can easily see that the zero measure is the only measure which is atomic as well as nonatomic measure.Let(X,Ω) be a measurable space and μ and ν be two measures on it. We say that ν is absolutely continuous with respect to μ, denoted by ν≪μ iff, for every measurable set F, ν(F)=0 whenever μ(F)=0.We say thatμ is singular with respect to ν and denoted by μ⊥ν if, given any E∈Ω, there exists some F⊆E, such that ν(E)=ν(F) and μ(F)=0. One can easily see that in this case ν(E)=sup⁡{ν(E∩F):μ(F)=0}. It is easily seen that the following lemma holds.Lemma 1.
Two atomic measures are mutually singular if and only if the corresponding sets of atoms do not have a common element.Johnson in [8] proved the following useful results about atomic and nonatomic measures.Result 1.
IfE is an atom for μ and ν≪μ, then either ν(E)=0 or E is an atom for ν.Result 2.
For a given measureμ on a σ algebra S, there are unique measures μ1 and μ2, such that μ=μ1+μ2, μ1⊥μ2, μ1 is atomic, and μ2 is nonatomic.


## 2. Definitions and Examples

LetX be a topological space and B(X) be the σ-algebra of Borel subsets of X. Let also μ be a probability measure on B(X). Set (1)Cμ≔ν:BX⟶0,1,νis  a  measure,ν≪μ.In other words, C(μ) is the collection of all absolutely continuous Borel measures with respect to μ. Define the following relation on C(μ): (2)ν1~ν2if  and  only  ifν1≪ν2,ν2≪ν1;in other words, ν1~ν2 if and only if for any measurable set E we have (3)ν1E=0⟺ν2E=0.Clearly, ~ is an equivalence relation on C(μ). Denoting the equivalence class of ν by [ν], let (4)Vμ=Cμ~∖μ=ν:ν∈Cμ∖μ.For simplicity, we write ν for [ν].We define a graphΓ(μ) with the set of vertices V(μ), and two vertices ν1 and ν2 are adjacent if and only if ν1 and ν2 are mutually singular. Clearly, the adjacency defined above is well-defined. The collection of all edges of Γ(μ) is denoted by E(μ). Therefore, we may assign a graph Γ(μ)=(V(μ),E(μ)) to any probability Borel measure μ on X.Example 2.
Leta∈X. If μ=δa is the dirac measure concentrated on a, then V(μ)={δa} and E(μ)=∅; so Γ(μ) consists of a vertex with no edges.Example 3.
Leta,b∈X, a≠b, and λ∈(0,1). Let μ=λδa+(1-λ)δb. Then V(μ)={δa,δb} where δa and δb are adjacent.(5)Example 4.
Letλi∈(0,1)(i=1,2,3) be such that ∑i=13λi=1 and ai(i=1,2,3) be three distinct elements of X. If μ=λ1δa1+λ2δa2+λ3δa3 then (6)Vμ=δa1,δa2,δa3,δa1a2,δa1a3,δa2a3,where (7)δaiaj=λiδai+λjδaji,j=1,2,3,i≠j.Also, each δai is adjacent to δaj for i≠j. δaiaj is adjacent to δak if i,j≠k. No other vertices are adjacent.(8)The following example is indeed the generalization of the previous examples and presents the graph corresponding to a finitely atomic measure.Example 5.
Letμ=∑i=1nλiδai be a finitely atomic measure with finite number of atoms where ai’s are distinct points in X and λi∈(0,1) is such that ∑i=1nλi=1. Then (9)Vμ=δai1ai2⋯aik:1≤k≤n-1,is≠ilfor1≤s,l≤k,where(10)δai1ai2⋯aik=∑j=1kλijδaij.By Lemma 1, two vertices ν1=δai1ai2⋯aik and ν2=δaj1aj2⋯ajl are adjacent if and only if ais≠ajt for all 1≤s≤k and 1≤t≤l.


## 3. The Graphs of Finitely Atomic Measures

In the rest of the paper, by an atomic measure, we mean a finitely atomic measure with finite number of atoms. In this section, we study the graph corresponding to atomic measures and state some of its properties. The case of atomic measures is of special interest since the corresponding graph is finite and may be visualized and enumerated.The following theorem satisfies for atomic measures.Theorem 6.
For an atomic measureμ=∑i=1nλiδai one has the following.(1)
V(μ)=∪k=1nVk, where Vk={δai1ai2⋯aik:1≤ij≤n} and Vk’s are disjoint.(2)
deg⁡(v)=2n-k-1 for any v∈Vk.Proof.
Part (1) holds, since the support of each element ofV(μ) should be contained in {a1,a2,…,an}.
To prove part (2), letv∈Vk and then v=∑j=1kλaijδaij. As mentioned in Example 5, a vertex w is adjacent to v if and only if ai1,ai2,…,aik∩supp⁡(w)=∅. Hence w should be of the form w=∑il≠i1,…,ikλilδil.
The number of such vertices is(11)n-k1+n-k2+⋯+n-kn-k=2n-k-1which completes the proof.Theorem 7.
For an atomic measureμ=∑i=1nλiδai, (n>3) one has the following: (1)
ω(Γ(μ))=χ(Γ(μ))=γ(Γ(μ))=n.(2)
diam⁡(Γ(μ))=3.Proof.
(1) Since {δa1,δa2,…,δan} is a clique set for Γ(μ), it follows that ω(Γ(μ))=n.
Since all elements of{δa1,δa2,…,δan} are pairwise adjacent then χ(Γ(μ))≥n. To prove the equality, we present a coloring of Γ(μ) with exactly n colors. For i∈{1,2,3,…,n}, let ci be a color assigned to the vertex δai. Now, for ν=δai1ai2⋯aik=∑j=1kλijδaij, assign the color ciν, where (12)iν≔min⁡ij:j=1,2,…,k.Clearly, there are exactly n colors used for the previous coloring. Also, no adjacent vertices have the same colors, since the two vertices ν1=δai1ai2⋯aik and ν2=δaj1aj2⋯ajl are adjacent if and only if {i1,i2,…,ik}∩{j1,j2,…,jl}=∅; therefore (13)min⁡i1,i2,…,ik≠min⁡j1,j2,…,jl;so ciν1≠ciν2. It completes the proof of χ(Γ(μ))=n.
Finally, since{δa1,δa2,…,δan} is a dominating set for Γ(μ) then γ(Γ(μ))≤n.
Now supposeD={μ0,…,μn-l},1<l<n+1, is a dominating set for Γ(μ). Set Di the set of atoms in which their coefficients in μi are nonzero. D′={D0,…,Dn-l} is a poset with the inclusion relation. By changing the indices we can write D′={D0,…,Dr-1,Dr,…,Dn-l}, where any Di is a minimal set for every 0⩽i<r and is not minimal set for other indices. By the axiom of choice, for every 0⩽i<r, one can choose an atom αi∈Di¯∖Di+1¯, where i≡i¯ (module r) and for every r⩽i⩽n-l one can choose αi∉Di.
Now defineμ∗=∑i=0n-l1/n-l+1δαi. It is easy to verify that μ∗ is neither adjacent nor equal to any element of D, which is contradiction to the assumption that D is a dominating set.
(2) Since each vertex of Γ(μ) is adjacent to at least an element of the set V1={δa1,δa2,…,δan} and all vertices in V1 are adjacent, then d(u,v)≤3 for all u,v∈V(μ). On the other hand, set μ1≔δa1a2⋯an-1 and μ2≔δa2a3⋯an. Clearly, the path (14)μ1⟼δan⟼δa1⟼μ2is of minimum length; therefore d(μ1,μ2)=3; consequently (15)diam⁡Γμ=max⁡du,v:u,v∈Γμ=3.The following theorem determines the automorphism group ofΓ(μ), where μ is an atomic measure.Theorem 8.
For any atomic measureμ=∑i=1nλiδai one has(16)AutΓμ≅Sn,where Sn is the group of permutations on n.Proof.
Letσ∈Sn. Define the mapping (17)σ∗:Vμ⟶Vμby (18)σ∗δai1⋯aik≔δaσi1⋯aσik.Clearly σ∗ is a bijection; so σ∗∈Aut(Γ(μ)). Now, define (19)Φ:Sn⟶Aut⁡Γμby (20)Φσ≔σ∗.It is easily seen that Φ is an injective group homomorphism. To complete the proof, it is enough to show that Φ is surjective.
To do this, letβ∈Aut(Γ(μ)). For any given i∈{1,2,…,n}, in light of Theorem 6, since the number of adjacent measures should remain the same by β we have (21)βδi=δjfor some j∈{1,2,…,n}.
Letσ∈Sn be defined by σ(i)=j. So (22)βδai=δaσi.We show that β=σ∗. Let δai1⋯aik be any given element of V(μ). Let also (23)βδai1⋯aik=δaj1⋯ajk.We should show that (24)δaj1⋯ajk=δaσi1⋯aσikor equivalently (25)j1,j2,…,jk=σi1,σi2,…,σik.Let j∉{σ(i1),σ(i2),…,σ(ik)}. Since σ is surjective, there exists a natural number i∉{i1,i2,…,ik} such that σ(i)=j. Note that, since i∉{i1,i2,…,ik} then the vertices δai and δai1⋯aik are adjacent. Since β∈Aut(Γ(μ)), the vertices β(δai) and β(δai1⋯aik) are adjacent which means that the vertices δaσ(i) and δaj1⋯ajk are adjacent; therefore j=σ(i)∉{j1,j2,…,jk}.
The previous discussion results in(26)j1,j2,…,jk⊆σi1,σi2,…,σik,but the two sets have the same cardinality, namely, k; therefore (27)j1,j2,…,jk=σi1,σi2,…,σikwhich completes the proof.Theorem 9.
Letμ=∑i=1nλiδai be an atomic measure; then α(Γ(μ))=2n-1-1.Proof.
For0⩽k,s⩽n-2 and 2⩽ia,jb≤n, two vertices x=δ1ai1⋯aik and y=δ1aj1⋯ajs are not adjacent, since 1 is a common index for both x and y. Therefore, the set (28)I=δ1ai1⋯aik∣0≤k≤n-2,2≤i1,…,ik≤nis an independent set. By elementary combinatorial principles of counting we have (29)I=n-10+n-11+⋯+n-1n-2=2n-1-1.Thus we have an independent set with cardinality 2n-1-1.
Observe thatV=2n-2, since any vertex can be written as δai1⋯aik, where {ai1,…,aik} is a nonempty proper subset of {a1,…,an}.
Now suppose thatA is an independent set of Γ(μ). For every δai1⋯aik, define δai1⋯aik′=δaj1⋯ajs, where {i1,…,ik}c={j1,…,js}. Obviously for every δai1⋯aik∈A, δai1⋯aik′ is adjacent to δai1⋯aik; hence δai1⋯aik′∉A.
For distinctδ’s, relative δ′’s are distinct; thus we will have A≤Ac. Finally, we can say (30)A≤V2=2n-22=2n-1-1.


## 4. General Measures

In the previous section, we discussed the graph assigned to atomic measures. In this section we study the general case.Theorem 10.
For a given measureμ, if α and β are two vertices of Γ(μ), one has the following. (1)
d(α,β)=1 iff α and β are mutually singular.(2)
d(α,β)=2 iff α and β are not mutually singular, but for some measurable set E with positive measure, one has α(E)=β(E)=0.(3)
d(α,β)=3 iff α and β are not mutually singular, but for no measurable set E with positive measure, one has α(E)=β(E)=0.Proof.
(1) It is done by definition.
(2) If the conditions hold, then by first part d(α,β)>1. Define the measure γ by γ(A)=μ(E∩A) for every A in B(X). Obviously γ≪μ. Since μ(E)>0, then γ≠0. By the definition of E, one can obtain μ≠γ. We also have (31)αE=βE=0,γEc=0.That is, γ⊥α and γ⊥β. Thus α~γ~β is a path and d(α,β)⩽2; therefore we have d(α,β)=2.
Now suppose thatd(α,β)=2; thus for some γ≪μ, we may have γ⊥α and γ⊥β. Therefore, for some nonzero μ-measurable sets G and F, we will have (32)αG=βF=0,γGc=γFc=0;thus we have (33)γGc∪Fc=0.If γ(G∩F)=0 then γ((Gc∪Fc)c)=γ(G∩F)=0; thus γ=0, a contradiction. Thus γ(G∩F)≠0; hence μ(G∩F)≠0. It is enough to take E=G∩F.
(3) If d(α,β)=3, none of the conditions of part (1) and (2) hold; thus the condition mentioned in this part will occur.
Now if the conditions of part (3) hold, by definition ofα and β, since V(μ) does not contain μ (indeed [μ]), for some nonzero μ-measurable sets E and F, we have (34)αE=βF=0,αF>0,βE>0,where μ(E∩F)=0. Now we can define two measures γ and δ by (35)γA=μA∩E,∀A∈BX,δA=μA∩F,∀A∈BX.Thus we will have α~γ~δ~β, which shows d(α,β)⩽3.
By parts (1) and (2), we can deduce thatd(α,β)=3.By Result2, every measure μ can be decomposed into two mutually singular measures: one is atomic and the other is nonatomic. We call the nonatomic measure the nonatomic part of μ and the other one the atomic part.Theorem 11.
If the nonatomic part ofμ is nonzero, then ω(Γ)=∞.Proof.
In light of Result2, suppose that μ=μ1+μ2, where μ1 is the atomic and μ2 is the nonatomic part of μ.
Sinceμ1⊥μ2, for some E∈B(X), we will have μ1(E)=0 and μ2(Ec)=0. So, μ(F)=μ2(F)∀F⊆E. Set F1=E. Since μ2 is nonatomic, we can split F1 into two disjoint measurable sets with positive μ2-measure. Let F2 be one of them. By continuing the previous process, there exists a sequence E=F1⊃F2⊃⋯ of nonzero μ2-measurable sets, and consequently a sequence Ei=Fi-Fi-1 with positive μ2-measure and therefore positive μ-measure.
Now defineνi(A)=μ(A∩Ei) for all i∈N. It is easily seen that νi’s are mutually singular and νi≪μ for all i∈N, that is, {νi∣i∈N} is a clique of Γ.Corollary 12.
If the nonatomic part ofμ is nonzero then ω(Γ)=χ(Γ)=∞.In the next theorem, we consider the domination number as well.Theorem 13.
If the nonatomic part ofμ is nonzero then the domination number of Γ=Γ(μ) cannot be finite.Proof.
Letμ=μ1+μ2, where μ1 is the atomic and μ2 is the nonatomic part of μ. Suppose that D={v1,…,vn} is a dominating set of Γ.
LetA={A∈B(X):∃vi∈D,vi(A)≠0, and μ2(A)≠0}. A is a poset with inclusion relation. Set B as the minimal element of A. Suppose that C and D are two subsets of B such that μ2(C)<μ2(D)<μ(B) and consequently, μ(C)<μ(D)<μ(B).
For every1⩽i⩽n, we can choose a nonzero measurable set Bi with vi(Bi)=0 and Bi∩D=∅. Let E=(∪i=1nBi)∪C.
Now define the measureη by η(A)=μ(E∩A) which is a measure different from all of vi’s and adjacent to none of them. A contradiction with the hypothesis is that D is a dominating set. Therefore, every dominating set is infinite.Theorem 14.
If the nonatomic part ofμ is nonzero, then α(Γ)=∞.Proof.
By the hypothesis of the theorem, there is some measurable setA of positive measure which does not contain any atom and hence there is a sequence of measurable sets (36)A=A1⊃A2⊃A3⊃⋯such that (37)μA=μA1>μA2>μA3>⋯>0.Now define the sequence of measures νi by νi(E)=μ(Ai∩E) for i∈N. By definition of νi’s we have νi≪μ,(i∈N). Now suppose that for some i<j we have νi⊥νj. Thus for Aj, there is some F⊆Aj, where νj(Aj)=νj(F) and νi(F)=0. But by definition νj≪νi which is a contradiction. Therefore, we conclude that the set {νi:i∈N} is an independent set of Γ, which is not finite and the theorem is proved.Applying the material presented in this paper, we will have the following corollary.Corollary 15.
Given any numbern (finite or infinite), there exists a nonregular graph Γ such that (38)ωΓ=χΓ=γΓ=n,αΓ=2n-1-1.



---

*Source: 1706812-2016-12-19.xml*