Short rainbow cycles for families of matchings and triangles He Guo November 20 2022 revised March 31 2024

2025-05-03 0 0 415.28KB 10 页 10玖币

侵权投诉

Short rainbow cycles for families of matchings and triangles

He Guo∗

November 20, 2022; revised March 31, 2024

Abstract

A generalization of the famous Caccetta–H¨aggkvist conjecture, suggested by Aharoni [2], is

that any family F= (F1,...,Fn) of sets of edges in Kn, each of size k, has a rainbow cycle of

length at most ⌈n

k⌉. In [3, 1] it was shown that asymptotically this can be improved to O(log n)

if all sets are matchings of size 2, or all are triangles. We show that the same is true in the

mixed case, i.e., if each Fiis either a matching of size 2 or a triangle. We also study the case

that each Fiis a matching of size 2 or a single edge, or each Fiis a triangle or a single edge,

and in each of these cases we determine the threshold proportion between the types, beyond

which the rainbow girth goes from linear to logarithmic.

Keywords: rainbow girth, generalized Caccetta–H¨aggkvist conjecture, short rainbow cycles

1 Introduction

The directed girth dgirth(G) of a digraph Gis the minimal length of a directed cycle in it (∞if

there is no directed cycle). A famous conjecture of Caccetta and H¨aggkvist [5] (below — CHC)

states that any digraph Gon nvertices satisﬁes dgirth(G)≤ ⌈ n

δ+(G)⌉, where δ+(G) is the minimum

out-degree of G. See [6, 8, 9, 11] for progress on this problem. In particular it has been shown that

(a) The CHC is true if n≥2δ+(G)2−3δ+(G) + 1 [12], and

(b) dgirth(G)≤n/δ+(G) + 73 for all G[13].

In [2] a possible generalization of CHC was suggested. Given a family F= (F1, . . . , Fm) of

sets of edges, a set Fof edges is said to be rainbow for Fif each of the edges in Fis taken from

a distinct Fi(if the sets Fiare disjoint, this means that |F∩Fi| ≤ 1 for each i). The rainbow

girth rgirth(F) of Fis the minimal length of a rainbow cycle with respect to F.

Conjecture 1. For any family F= (F1, . . . , Fn)of subsets of E(Kn)such that |Fi|=kfor

each 1≤i≤n, we have rgirth(F)≤ ⌈n/k⌉.

We may clearly assume that the sets Fiare disjoint, since otherwise there is a rainbow digon,

meaning that the rainbow girth is 2. Given F= (F1, . . . , Fm) with Fi̸=∅for each i∈[m] and

∪m

i=1Fi=E(G) for some graph G, we shall refer to Fas an edge coloring of G, the indices i∈[m]

as colors, the sets Fias color classes, and rgirth(F) as the rainbow girth of Gwith respect to the

edge coloring F.

∗Faculty of Mathematics, Technion, Haifa 32000, Israel. E-mail: hguo@campus.technion.ac.il.

arXiv:2210.12243v3 [math.CO] 24 Sep 2024

Devos et. al. [7] proved Conjecture 1 for k= 2. In [1] a stronger version of the conjecture was

proved, in which the sets Fiare of size 1 or 2. In [10] it was shown that the order of magnitude

is right: there exists a constant C > 0 such that for any k, n and Fsatisfying the assumption

of Conjecture 1, we have rgirth(F)≤Cn/k. An explanation why Conjecture 1 implies the CHC

can be found in [3] and [1].

All known extreme examples for Conjecture 1 are obtained from those of the CHC, taking the

color classes as stars. This suggests looking at the case when the sets of edges are not stars, and

trying to improve the upper bound on the girth. Indeed, in [3], it is proved that if an n-vertex

graph is edge-colored by ncolors such that each color class is a matching of size 2, then the rainbow

girth is O(log n), asymptotically improving the conclusion of the conjecture.

A set of edges not containing a matching of size 2 is either a star or a triangle, hence the next

interesting case is that of families of triangles. In [1], it is proved that a family of ntriangles in

Knhas rainbow girth O(log n). Furthermore, it was shown there that log nis the right order of

magnitude: an n-vertex graph is constructed, consisting of nedge-disjoint triangles whose rainbow

girth is Ω(log n).

In this note we ﬁne-tune the above results, by showing that the rainbow girth is O(log n) in the

mixed case that each Fiis either a matching of size 2 or a triangle. We also study the case that

each Fiis a matching of size 2 or a single edge, or each Fiis a triangle or a single edge, and in each

of these cases we determine the threshold proportion between the types, beyond which the rainbow

girth goes from linear to logarithmic.

2 Graph theoretical and probabilistic tools

As in [10, 3], a key ingredient in the proofs is a result by Bollob´as and Szemer´edi [4] on the girth

of sparse graphs.

Theorem 2. For N≥4and k≥2, every N-vertex graph with N+kedges has girth at most

2(N+k)

3k(log2k+ log2log2k+ 4).

We shall use two well-known concentration inequalities.

Theorem 3 (Chernoﬀ).Let Xbe a binomial random variable Bin(n, p). For any t≥0, we have

P(X≥EX+t)≤exp −t2

2(EX+t/3).

Theorem 4 (Chebyshev).Let Xbe a random variable. For any t > 0, we have

P(|X−EX| ≥ t)≤Var X

t2,

where Var Xis the variance of X.

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

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

10 玖币 0人已下载

立即下载

摘要：

ShortrainbowcyclesforfamiliesofmatchingsandtrianglesHeGuo∗November20,2022;revisedMarch31,2024AbstractAgeneralizationofthefamousCaccetta–H¨aggkvistconjecture,suggestedbyAharoni[2],isthatanyfamilyF=(F1,...,Fn)ofsetsofedgesinKn,eachofsizek,hasarainbowcycleoflengthatmost⌈nk⌉.In[3,1]itwasshownthatasympto...

展开>> 收起<<

Short rainbow cycles for families of matchings and triangles He Guo November 20 2022 revised March 31 2024.pdf

共10页,预览2页

还剩页未读，继续阅读

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

Short rainbow cycles for families of matchings and triangles He Guo November 20 2022 revised March 31 2024

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: