Colouring random geometric graphs

EuroComb 2005 DMTCS proc.AE, 2005, 1–4

Colouring random geometric graphs

C. J. H. McDiarmid

and T. M¨uller

1University of Oxford, Department of Statistics, 1 South Parks Road, Oxford OX1 3TG, United Kingdom

A random geometric graphGnis obtained as follows. We takeX1, X2, . . . , Xn∈R^dat random (i.i.d. according to some probability distributionνonR^d). Fori6=jwe joinXiandXjby an edge ifkXi−Xjk< r(n). We study the properties of the chromatic numberχnand clique numberωnof this graph asnbecomes large, where we assume that r(n)→0. We allow any choiceνthat has a bounded density function andk.kmay be any norm onR^d. Depending on the choice ofr(n), qualitatively different types of behaviour can be observed. We distinguish three main cases, in terms of the key quantitynr^d(which is a measure of the average degree). Ifr(n)is such that ^nr_lnn^d →0asn→ ∞ then^χ_ωⁿ_n →1almost surely. If^nr_lnn^d → ∞then ^χ_ωⁿ_n →¹_δ almost surely, whereδis the (translational)packing density of the unit ballB:={x∈R^d:kxk<1}(i.e.δis the proportion ofd-space that can be filled with disjoint translates ofB). If^nr_lnn^d→t∈(0,∞)then^χ_ωⁿ

ntends almost surely to a constant that can be bounded in terms ofδandt. These results extend earlier work of McDiarmid and Penrose. The proofs in fact yield separate expressions forχnandωn. We are also able to prove a conjecture by Penrose. This states that when^nr_lnn^d →0then the clique number becomes focussed on two adjacent integers, meaning that there exists a sequencek(n)such thatP(ωn∈ {k(n), k(n) + 1})→ 1asn → ∞. The analogous result holds for the chromatic number (and for the maximum degree, as was already shown by Penrose in the uniform case).

Keywords:random geometric graphs, graph colouring

1 Introduction

A random geometric graphGn is obtained as follows. We pick verticesX1, . . . , Xn ∈ R^d at random (iid according to some probability distribution ν on R^d) and we join Xi, Xj (i 6= j) by an edge if kXi−Xjk< r(n), where we assume thatr(n) → 0asn → ∞. We will allow any choice ofν that has a bounded density andk.kmay be any norm onR^d. In this paper we are interested in the behaviour of the clique number,ωn, and the chromatic number,χn, ofGnasngrows large. The distancer(n)plays a role similar to that ofp(n)in the Erd¨os-Renyi random graphsG(n, p). Depending on the choice ofr(n) qualitatively different types of behaviour can be observed. We describe the various cases in terms of the quantitynr^d, which is a measure of the average degree of the graph. Intuitively it should be clear that theexpecteddegree scales withnr^d. More formally it can be shown that the ratio of the average degree divided bynr^d tends to a constant (which depends onν) in probability as long asn²r^d → ∞(this last condition is needed to ensure that the probability that the graph consists of isolated vertices tends to 0).

†This author is partially supported by EPSRC, the Department of Statistics, Bekker-la-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds

1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

2 Colin J. H. McDiarmid and Tobias M¨uller

2 Statement and discussion of results

Perhaps rather suprisingly at first glance the only feature of the probability measureν that plays any role in our results (and proofs) is themaximum densityνmaxdefined as:sup_C ^ν(C)_λ(C), whereλdenotes the Lebesgue measure onR^dand the supremum is over all measurable setsCwith positive Lebesgue measure.

We will always assume thatνmax<∞, which can be seen to be equivalent toνhaving a bounded density functionf wrt. the Lebesgue measure.

Theorem 1 The following statements hold, asn→ ∞ (i) If^nr_lnn^d →0then^χ_ωⁿ

n →1a.s.

(ii) If^nr_lnn^d → ∞then_ω^χn

n → ¹_δ a.s.

(iii) If ^nr_lnn^d →t∈(0,∞)then^χ_ωⁿ

n →x(t)a.s. Here1≤x(t)≤^c(t)_δ , wherec(t) := ^G((

θ

2d δν_maxt)⁻¹) G((^θ

2dνmaxt)⁻¹), and for eachy≥0,G(y)is the uniquex≥1that satisfies xlnx−x+ 1 =y.

The constantθis the Lebesgue measureλ(B)of the unit ballB :={x:kxk<1}wrt.k.kandδis the the (translational)packing densityofB, meaning thatδis the maximal proportion ofd-space that can be filled with disjoint translates ofB. One of several equivalent definitions ofδis the following. LetN(K) denote the maximum cardinality of mutually disjoint translates ofBwith centers in[0, K]^dthen

δ:= lim

K→∞

θN(K) K^d .

It can be shown that this limit exists. For an overview of results on packing see for instance (Rog64) or (PA95). InR²with the Euclidean normδ= ^π

2√

3, so that ¹_δ ≈1.103. Assuming thatδ6= 1the function c(t)in Theorem 1 is strictly increasing,c(t) → δast → 0 andc(t) → 1as t → ∞. Ifδ = 1then c(t)≡1and in that caselim^χ_ω = 1a.s. for all choices ofr(n)withr(n)→0.

Following the interpretation ofnr^das a measure of the average degree, we will refer to the case^nr_lnn^d → 0as thesparse case, the case^nr_lnn^d → ∞as thedense caseand the case when ^nr_lnn^d →t∈ (0,∞)as the intermediate case(s). We remark that although the theorem has been phrased in terms of the ratio ^χ_ω, the proofs of the results actually describe the behaviour ofχandωseparately.

Results similar to Theorem 1 already appeared in (McD03; Pen03). Part (i) of Theorem 1, concerning the sparse case, is in fact a strengthening of a result that appears in both (McD03) and (Pen03), because there the extra conditionnr^d=n^o(1)was assumed, which amounts to discarding the case when the aver- age degree is very small (a negative power ofn), and furthermore both showed convergence in probability as opposed to almost sure convergence. As part of the proof we show that when the average degree is very small then something much stronger than convergence of the ratio to 1 holds, namely: ifnr^d =o(n^−α) for someα >0then with probability oneχn=ωnfor all but finitely manyn.

In the dense case (Pen03) effectively gave an upper bound forlim sup^χ_ωof _δ¹

L and a lower bound for lim inf ^χ_ω of ¹_δ, whereδLis the so-calledlattice packing densityofB(ie. the proportion ofd-space that can be filled with disjoint translates ofBwhose centers are the integer linear combinations of some basis

Colouring random geometric graphs 3 for R^d). The paper (McD03) only considers the Euclidean norm in the plane in which case δandδ_L coincide. In general dimension the question of whetherδ=δ_L is open for the Euclidean norm and it is conjectured thatδ > δ_Lfor large dimensionsd(see (Rog64)).

In the intermediate case our contribution consists of giving an upper bound which is an improvement over the one given in section 6.6 of (Pen03), which in particular shows that ¹_δ is always an upper bound;

and showing that the (almost sure) limit of ^χ_ωⁿ

n exists.

A rough sketch of the proof of the upper bound is as follows. In (Pen03) it was already shown that lim_nr^ωnd =^aθν₂^maxd a.s. wherea=G((₂^θdνmaxt)⁻¹)in the intermediate case anda= 1in the dense case.

Thus it remains to show that _nr^χn_d ≤ (1 +)^bθν_2d^max_δ (for all but finitely manyn, with probability one), whereb = 1in the dense case andb =G((₂^θ_dδνmaxt)⁻¹)in the intermediate case. To do this we dissect R^d into a collectionC of ‘small’ cubes of sideηr(withη = η()small but fixed) and partitionCinto subcollectionsC1, . . . ,CN such thatkp−qk≥rwheneverp, qare in different small cubes belonging to the sameCi. Using the definition ofδ, theCican be constructed in such a way that for any fixedK >0 the union of anyN small cubes inC contained in a large cube of side rK will contain no more than (1 +)^bθν_2d^max_δ nr^dpoints (for all but finitely manyn, with probability one). Since points in different small cubes belonging to the sameC_imay receive the same colours, it follows that we can colour any subgraph ofG_n induced by the points in a large cube of siderK with no more than(1 +)^bθν_2d^max_δ nr^d colours.

These colourings of induced subgraphs can be adapted to yield a colouring of the entire graph with the same number of colours whenKis sufficiently large.

To prove the existence result we again consider the chromatic number of subgraphs induced by the points in a cube of siderK forK fixed. When Kis large the maximum over all such subgraphs will be a good approximation of the chromatic number of the entire graph and the chromatic number of such a subgraph can in turn be approximated well by a linear program with fixed dimensions (dependent on Kandif we wish to approximate to within a factor1 +). Each of the feasible pointspof this linear program corresponds to a sumPn

i=1fp(Xi)wherefpis a particular type of function with range[0,1].

The result now follows by considering the probability distribution of such a sum.

In the course of the proof of part (i) we find that whennr^dis bounded above by a negative power ofn then the probability mass of the clique number becomes concentrated on two consecutive integers in the sense thatP(ω_n∈ {m(n), m(n) + 1})→1for some sequencem(n)which depends onr(n). The same holds for the maximum degree and chromatic number. For sparse Erd¨os-Renyi random graphs a similar phenomenon is well known to occur for several graph parameters including the chromatic number. In (Pen03) it was shown that this phenomenon, dubbed focusing, holds for the maximum degree ifnr^d = o(lnn)and it was conjectured to hold for the clique number as well whennr^d=o(lnn). We are able to prove the conjecture and extend the result to the chromatic number:

Theorem 2 Ifnr^d =o(lnn)then there exist sequencesm(n), k(n)such that asn→ ∞ (i) P(ω_n∈ {m(n), m(n) + 1})→1;

(ii) P(χn∈ {k(n), k(n) + 1})→1.

References

[McD03] C. McDiarmid. Random channel assignment in the plane. Random Structures Algorithms, 22(2):187–212, 2003.

4 Colin J. H. McDiarmid and Tobias M¨uller [PA95] J. Pach and P. K. Agarwal. Combinatorial geometry. Wiley-Interscience Series in Dis- crete Mathematics and Optimization. John Wiley & Sons Inc., New York, 1995. A Wiley- Interscience Publication.

[Pen03] M. D. Penrose.Random Geometric Graphs. Oxford University Press, Oxford, 2003.

[Rog64] C. A. Rogers. Packing and covering. Cambridge Tracts in Mathematics and Mathematical Physics, No. 54. Cambridge University Press, New York, 1964.