Rainbow spanning trees in randomly coloured Gkout Deepak Bal Alan Frieze and Pawe l Pra lat November 2 2023

2025-04-29 0 0 418.73KB 18 页 10玖币

侵权投诉

Rainbow spanning trees in randomly coloured Gk−out

Deepak Bal∗

, Alan Frieze†

, and Pawel Pralat‡

November 2, 2023

Abstract

Given a graph G= (V, E) on nvertices and an assignment of colours to its edges, a

set of edges S⊆Eis said to be rainbow if edges from Shave pairwise diﬀerent colours

assigned to them. In this paper, we investigate rainbow spanning trees in randomly

coloured random Gk−out graphs.

1 Introduction

Let G= (V, E) be a graph in which the edges are coloured. A set S⊆Eis said to be rainbow

coloured if each edge of Sis in a diﬀerent colour. There is by now a large body of research on

the existence of rainbow structures in randomly coloured random graphs. Let us highlight a

few selected results. Frieze and McKay [14] and Bal, Bennett, Frieze and Pralat [1] studied the

existence of rainbow spanning trees in Gn,m, the classical Erd˝os–R´enyi random graph process.

Cooper and Frieze [6], Frieze and Loh [13] and Ferber and Krivelevich [10] studied the existence

of rainbow Hamilton cycles in Gn,m. Janson and Wormald [15] studied the existence of rainbow

Hamilton cycles in random regular graphs. Finally, Bal, Bennett, P´erez-Gim´enez and Pralat [2],

investigated rainbow perfect matchings and Hamilton cycles in random geometric graphs. Of

the most popular random graph models, what is missing here is the random multigraph Gk−out.

The aim of this paper is to initiate the study of these problems in the context of a randomly

coloured Gk−out graphs.

All asymptotics throughout are as n→ ∞ (we emphasize that the notations o(·) and O(·) refer

to functions of n, not necessarily positive, whose growth is bounded). We say that an event in

∗Department of Mathematics, Montclair State University, Montclair NJ 07043, USA; e-mail:

deepak.bal@montclair.edu

†Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA; e-mail:

frieze@cmu.edu; research supported in part by NSF grant DMS1952285.

‡Department of Mathematics, Toronto Metropolitan University, Toronto, ON, Canada; e-mail:

pralat@torontomu.ca; research supported in part by NSERC grant; part of this work was done while the

author was visiting the Simons Institute for the Theory of Computing.

arXiv:2210.01327v2 [math.CO] 31 Oct 2023

a probability space holds with high probability (or w.h.p.) if the probability that it holds tends

to one as n→ ∞. We often write Gk−out when we mean a graph drawn from the distribution

Gk−out.

The random graph Gk−out =Gk−out(n) is deﬁned as follows. It has vertex set [n] := {1, . . . , n}

and each vertex i∈[n] independently chooses krandom distinct neighbours from [n]\ {i}, so

that each of the n−1

ksets is equally likely to be chosen. It was shown by Fenner and Frieze [8]

that Gk−out is k-connected w.h.p. for k≥2. It was shown by Frieze [11] that G2−out has a

perfect matching w.h.p., and by Bohman and Frieze [3] that G3−out is Hamiltonian w.h.p. All

of the above results are sharp. For more details we direct the reader to Chapter 18 in [12].

We deﬁne the randomly coloured graph Gk,q =Gk,q(n) (not to be confused with Gn,m) as

follows: the underlying graph on nvertices is Gk−out and (i) there is a set Qof qcolours, (ii)

each colour appears ρ:= ⌊kn/q⌋or ρ+ 1 times (there are kn −qρ popular colours that appear

ρ+ 1 times, the remaining colours are unpopular and appear ρtimes; note that if qdivides kn,

then all colours are unpopular), (iii) kn colours, including repetitions, are randomly assigned

to the kn edges of Gk−out. Finally, let us note that, without loss of generality, we may assume

that q≤kn. Indeed, if the number of colours is more than kn, then some colours are not used

at all and the problem is equivalent to the one with q=kn.

In this paper we investigate spanning trees. We will prove the following theorem.

Theorem 1. If k≥2and q≥n−1, then Gk,q has a Rainbow Spanning Tree (RST) w.h.p.

The result is best possible. Trivially, if q≤n−2, then there are not enough colours to create

a rainbow tree. If k= 1, then Gk,q is disconnected w.h.p. [8].

2 Preliminaries

2.1 Colour Monotonicity

In our problem, we randomly colour kn edges of Gk,q with qcolours and we aim to create a

rainbow structure. Recall that there are q2=kn −qρ popular colours that are present ρ+ 1

times and q1=q−q2unpopular colours that are present ρtimes.

It is natural to expect that the more colours are available, the easier it is to achieve our goal. We

prove this monotonicity property in the following, slightly broader, context. Suppose that we

are given a ﬁnite set Xand a set of colours Cwhere |C|=|X|. (In our application, Xis the set

of kn edges of Gk,q and Cis the set of kn colours: qcolours from set Q, including repetitions.)

We also have two distinct partitions of C:C={C1, . . . , Cq}and 

C={

C1,..., 

Cq+1}, for some

positive integer q≤ |X| − 1. (In our application, each part corresponds to a colour from set

Q. Partitions Cand 

Ccorrespond to colourings with qand q+ 1 colours respectively.) Let

ρ=⌊|X|/q⌋,ρ=⌊|X|/(q+ 1)⌋,q2=|X| − qρ, and q1=q−q2. Suppose that |Ci|=ρfor

1≤i≤q1and |Ci|=ρ+ 1 for q1+ 1 ≤i≤q, that is, there are q1parts in Cof size ρand q2

parts of size ρ+ 1.

We are given a collection of sets X1, X2, . . ., each set Xiis a subset of X. (In our application,

the Xiare the edges of spanning trees, perfect matchings, Hamilton cycles, etc.) Our goal is

to create at least one rainbow set from this collection. Let us consider a random colouring of

Xvia a random bijection from Cto X. In order to show that the probability that some Xi

is rainbow in a random colouring with q+ 1 colours is at least the corresponding probability

when elements of Xare coloured with qcolours, we need to couple the two partitions. In order

to do that we need to consider two cases.

Case 1:ρ=ρ. Partition 

Cis obtained from Cby choosing ρparts in Cof size ρ+ 1 and

replacing them with ρ+ 1 parts of size ρ(see Figure 1). We couple the two colourings by

ﬁrst randomly mapping the |C| − ρ(ρ+ 1) colours from the parts that are the same in both

partitions, and conditioning on the result. If some rainbow Xiis created, then it is clearly

present in both colourings. Otherwise, it is easy to see that partition 

Cis at least as likely

to complete a rainbow colouring. Indeed, suppose that some Xihas selements that are not

coloured yet; we may assume that 1 ≤s≤ρas, otherwise, such a set cannot be rainbow via

the ﬁrst partition (it could be rainbow via the second partition if s=ρ+ 1). The probability

that partition Ccompletes a rainbow colouring is equal to s−1

i=1

ρ(ρ+1)−i(ρ+1)

ρ(ρ+1)−ithat is at most the

corresponding probability for partition 

C, namely, s−1

i=1

ρ(ρ+1)−iρ

ρ(ρ+1)−i.

Figure 1: The coupling of the two colourings in Case 1.

Case 2:ρ=ρ−1. As before, we start with partition Cbut this time we take all q2parts of

size ρ+ 1 (possibly q2= 0 so we might not have any) and we choose ρ−1−q2parts of size ρ.

To create partition 

C, we replace them with q2parts of size ρand ρ−q2parts of size ρ−1.

As in the other case, either we create some rainbow Xior partition 

Cis at least as likely to

complete a rainbow colouring of some set Xi.

The above coupling allows us to concentrate on the minimum number of colours. In particular,

in the proof of Theorem 1, without loss of generality, we may assume that q=n−1.

2.2 Degree Monotonicity

Based on Section 2.1, in order to prove Theorem 1 we may assume that q=|Q|=n−1.

In this setup, there are kpopular colours present k+ 1 times in Gk,q and q−k=n−1−k

unpopular colours present ktimes in Gk,q. Exactly one out of k+ 1 copies of each popular

colour is called special. Similarly, there are k+ 1 popular colours present k+ 2 times in Gk+1,q,

q−(k+ 1) = n−2−kunpopular colours present k+ 1 times, and there are k+ 1 special copies

of popular colours (one special copy of each).

It seems reasonable to expect that if Gk,q has a particular rainbow structure w.h.p., then so

does Gk+1,q. Let Γk+1 be the bipartite graph with vertex sets [n] and Q′=Q∪ {q}, where q

is a “dummy” vertex that will be associated with special copies of popular colours. For each

of the (k+ 1) edges chosen by v∈[n] in Gk+1,q, we observe a colour cof that edge without

exposing its other endpoint. If a copy of colour cis non-special, then we add an edge between

vand c∈Qin Γk+1; otherwise, we add an edge between vand the “dummy” vertex q. Note

that we need the extra vertex qto make Γk+1 regular.

Recall that (k+ 1)ncolours, including repetitions, are randomly assigned to the (k+ 1)nedges

of Gk+1,q. Hence, Γk+1 is distributed as a random (k+ 1)-regular bipartite (multi)graph (where

multiple edges are allowed but not loops). Indeed, it ﬁts the bipartite conﬁguration model of

Bollob´as [4]. Each vertex could be replaced by a distinct set of (k+1) points, each colour c∈Q

naturally corresponds to (k+ 1) points associated with non-special copies of that colour, and

the “dummy” vertex qcorresponds to (k+ 1) points associated with special copies of popular

colours. Then, we randomly pair these points to get the colouring of the edges of Gk+1,q. Note

that Γk+1 contains no information about the actual vertex choices of edges in Gk+1,q, only their

colour. Informally, we can think of each edge of Γk+1 being associated with a box containing a

random vertex from [n]. We do not need to open these boxes for what is next.

We will use the fact that Γk+1 is contiguous to the sum of (k+ 1) independent random perfect

matchings—see the survey on random regular graphs by Wormald [18]. If we delete one of

these matchings, then we obtain a random k-regular bipartite graph contiguous to Γk. Arguing

as before, we observe that Γkmay be viewed as a random assignment of kn colours, including

repetitions, to the kn edges of Gk,q. “Opening” the boxes on each edge of Γkgives us Gk,q,

which by assumption has a required rainbow structure w.h.p. So, using the above coupling we

conclude that Gk+1,q also has a rainbow structure w.h.p.

3 Rainbow Spanning Trees

In view of the results in Sections 2.1 and 2.2, we will assume that k= 2 and q=n−1 for this

section.

To establish the existence of a RST to prove Theorem 1, we will use the result of Edmonds [7]

on the matroid intersection problem. A ﬁnite matroid Mis a pair (E, I), where Eis a ﬁnite

set (called the ground set) and Iis a family of subsets of E(called the independent sets) with

the following properties:

•∅∈I,

•for each A′⊆A⊆E, if A∈ I, then A′∈ I (hereditary property),

•if Aand Bare two independent sets of Iand Ahas more elements than B, then there

exists an element in Athat when added to Bgives a larger independent set than B

(augmentation property).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

RainbowspanningtreesinrandomlycolouredGk−outDeepakBal∗,AlanFrieze†,andPawelPralat‡November2,2023AbstractGivenagraphG=(V,E)onnverticesandanassignmentofcolourstoitsedges,asetofedgesS⊆EissaidtoberainbowifedgesfromShavepairwisedifferentcoloursassignedtothem.Inthispaper,weinvestigaterainbowspanningtree...

展开>> 收起<<

Rainbow spanning trees in randomly coloured Gkout Deepak Bal Alan Frieze and Pawe l Pra lat November 2 2023.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Rainbow spanning trees in randomly coloured Gkout Deepak Bal Alan Frieze and Pawe l Pra lat November 2 2023

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: