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 Pawel Pralat‡
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 different 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 different 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 Pralat [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 Pralat [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.
1
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 defined 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
ksets 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 define 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 finite 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.
2
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
first 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 first 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.
q1
q2
ρ
C
b
C
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).
3
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 fits the bipartite configuration 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 finite matroid Mis a pair (E, I), where Eis a finite
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).
4
摘要：
展开>>
收起<<
RainbowspanningtreesinrandomlycolouredGk−outDeepakBal∗,AlanFrieze†,andPawelPralat‡November2,2023AbstractGivenagraphG=(V,E)onnverticesandanassignmentofcolourstoitsedges,asetofedgesS⊆EissaidtoberainbowifedgesfromShavepairwisedifferentcoloursassignedtothem.Inthispaper,weinvestigaterainbowspanningtree...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：图书资源
价格：10玖币
属性：18 页
大小：418.73KB
格式：PDF
时间：2025-04-29
渝公网安备50010702506394
