A NOTE ON NON-ISOMORPHIC EDGE-COLOR CLASSES IN RANDOM GRAPHS PATRICK BENNETT RYAN CUSHMAN ANDRZEJ DUDEK AND ELIZABETH SPRANGEL

2025-04-27 0 0 507.35KB 15 页 10玖币

侵权投诉

A NOTE ON NON-ISOMORPHIC EDGE-COLOR CLASSES IN

RANDOM GRAPHS

PATRICK BENNETT, RYAN CUSHMAN, ANDRZEJ DUDEK, AND ELIZABETH SPRANGEL

Abstract.

For a graph

, let

τpGq

be the maximum number of colors such that there

exists an edge-coloring of

with no two color classes being isomorphic. We investigate

the behavior of τpGqwhen G“Gpn, pqis the classical Erdős-Rényi random graph.

§1. Introduction

Recall that for graphs

H, G

we deﬁne an

H-factor of G

to be a covering of the vertices

|G|{|H|

vertex-disjoint copies of

. Equivalently, an

-factor of a graph

is a

partition of the vertices of

such that each part contains

as a spanning subgraph. For

example, for

-factors, we wish to partition the vertices of

such that each part is an

-clique. In this paper we consider what is in some sense an opposite problem: when can

we partition the edges of

into parts which are pairwise-non-isomorphic? Clearly, using

one part will be suﬃcient, but letting each edge be its own part would not. Therefore, we

are interested in the maximum number of parts where this property holds. More precisely,

we deﬁne the parameter

τpGq

to be the maximum number of colors such that there exists

a coloring of the edges of

such that any two color classes are non-isomorphic. Note that

τpGq

exists, since one color satisﬁes the condition. In this paper we focus on

τpGpn, pqq

where Gpn, pqis the Erdős-Rényi random graph.

Before we state our results we give some history for

-factors in

Gpn, pq

. In [5], Erdős

reported that the Shamir problem [17]—when do perfect matchings occur in the

-uniform

random hypergraph

Hrpn, pq

?—was one of the combinatorial problems he would most like

to see solved. A similar question was proposed and some initial work done by Rucínski [16]

and Alon and Yuster [1] for the case of

Gpn, pq

: what is the threshold for an

-factor?

After some partial results, both questions were answered by Johansson, Kahn and Vu in [10].

More precise answers have also recently been oﬀered by Kahn [11] and Riordan [15]. Kahn

determined a sharp threshold for a matching in

Hrpn, pq

and Riordan created a coupling

between

Hrpn, pq

and

Gpn, pq

in which hyperedges of

Hrpn, pq

correspond to cliques in

Gpn, pqfor rě4(the case of r“3was proved in [8] by Heckel).

We have several results about

τpGpn, pqq

, covering various edge densities. Our ﬁrst

theorem gives bounds for a large range of

. We say that a sequence of events

happens

The ﬁrst author was supported in part by Simons Foundation Grant #426894.

The third author was supported in part by Simons Foundation Grant #522400.

arXiv:2210.02301v2 [math.CO] 10 Jan 2023

2 PATRICK BENNETT, RYAN CUSHMAN, ANDRZEJ DUDEK, AND ELIZABETH SPRANGEL

asymptotically almost surely

(a.a.s.) if

PrpEnq Ñ

1as

nÑ 8

. All asymptotics in this

paper are as

nÑ 8

, and

p“ppnq

may depend on

. We sometimes write inequalities

that are valid only for suﬃciently large

. We use the standard big-

and little-

notation,

as well as the standard Ω

Θnotation. Our ﬁrst result covers the dense and not-too-sparse

regime.

Theorem 1.1.

There is an absolute constant

Cą

0such that if

Clog n

nďpď1

log n

and

G“Gpn, pq, then a.a.s.

Ωˆpn2

log n˙“τpGq “ Oˆpn2log log n

log n˙.

When we let

Gpn, pq

become slightly sparser, we can also determine bounds for

although the lower bound is slightly less precise.

Theorem 1.2.

There is an absolute constant

Cą

0such that if

pěC

and

G“Gpn, pq

then a.a.s.

Ωˆpn2

log2n˙“τpGq “ Oˆpn2log log n

log n˙.

Letting p“1yields the following result for complete graphs.

Corollary 1.3. Let Kndenotes the complete graph of order n. Then,

Ωˆn2

log2n˙“τpKnq “ Oˆn2log log n

log n˙.

Finally, we consider some very sparse regimes, in which we determine the order of

magnitude of τpGpn, pqq.

Theorem 1.4.

Let

G“Gpn, pq

be such that

n´k

k´1!p!n´k`1

for some positive

integer kě2. Let `“`pkq “ t?8k´7`1

2u. Then,

τpGq “ Θ´np``2qp`´1q

2`p`´1

2¯.

In the sparsest cases (Theorem 1.4), we are able to determine the order of magnitude

while in the other cases (Theorems 1.1 and 1.2), the upper and lower bounds are separated

by a logarithmic factors in the numerator or denominator. It would be an interesting future

direction to remove this ambiguity about the order of magnitude and have a more precise

result. In particular improving Corollary 1.3 may be easier than working with Gpn, pq.

We will be using the following forms of Chernoﬀ’s bound (see, e.g., [9]).

Lemma 1.5

(Chernoﬀ bound)

Let

X„Binpn, pq

and

µ“EpXq

. Then, for all 0

ăδă

PrpXě p1`δqµq ď expp´µδ2{3q

and

PrpXď p1´δqµq ď expp´µδ2{2q.

A NOTE ON NON-ISOMORPHIC EDGE-COLOR CLASSES IN RANDOM GRAPHS 3

Furthermore if Rě2eµ, we have

PrpXěRq ď 2´R.

We recently learned that the lower bounds in Theorems 1.1 and 1.2 can be also derived

from a result of Ferber and Samotij [6]. Since their approach is diﬀerent from ours, we

decided to keep our proofs for the sake of completeness.

§2. Proof of Theorem 1.1

2.1.

Upper bound.

We start with the lower bound. Let

pělog n

and

G“Gpn, pq

. We

are going to show that τpGq ď pn2{f, where f:“fpnq “ log n

2 log log n.

For a proof by contradiction, assume that

τpGq ą pn2{f

. Let

αěf

be the number of

color classes with at least

edges. Similarly, we deﬁne

αăf

as the number of color classes

with less than fedges.

First we estimate

αăf

from above. Observe that any graph with at most

edges and no

isolated vertices cannot have more than 2

vertices. Thus the number of colors having

edges is at most

ˆ`2i

2˘

i˙

, the number of ways to choose

edges on 2

vertices. Since we

consider graphs with at most fedges, we get

αăfď

i“1ˆ`2i

2˘

i˙ďfˆ`2f

2˘

f˙ďfˆ2f2

f˙ďfp2efqf“fexptflogp2ef qu

“fexp "log n

2 log log nplog log n´log log log n`1q*

ďfexp "1

2log n*“fn1{2“oˆpn2

f˙,(2.1)

where the latter follows from pělog n

Next note that

αěfě

pn2{p

; indeed, otherwise we would have

αěfă

pn2{p

and

therefore

pn2

făτpGq “ αěf`αăfă2pn2

3f`oˆpn2

f˙ăpn2

a contradiction.

Finally, observe that the the lower bound on

αěf

implies that the number of edges in

is at least

fαěfěf2pn2

3f“2pn2

which is a contradiction, since it is well-known that the number of edges in

is highly

concentrated around its mean `n

2˘p“ p1`op1qqpn2{2. Thus, τpGq ď pn2{f, as required.

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

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

10 玖币 0人已下载

立即下载

摘要：

ANOTEONNON-ISOMORPHICEDGE-COLORCLASSESINRANDOMGRAPHSPATRICKBENNETT,RYANCUSHMAN,ANDRZEJDUDEK,ANDELIZABETHSPRANGELAbstract.ForagraphG,letpGqbethemaximumnumberofcolorssuchthatthereexistsanedge-coloringofGwithnotwocolorclassesbeingisomorphic.WeinvestigatethebehaviorofpGqwhenGGpn;pqistheclassicalErd®s...

展开>> 收起<<

A NOTE ON NON-ISOMORPHIC EDGE-COLOR CLASSES IN RANDOM GRAPHS PATRICK BENNETT RYAN CUSHMAN ANDRZEJ DUDEK AND ELIZABETH SPRANGEL.pdf

共15页,预览3页

还剩页未读，继续阅读

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

A NOTE ON NON-ISOMORPHIC EDGE-COLOR CLASSES IN RANDOM GRAPHS PATRICK BENNETT RYAN CUSHMAN ANDRZEJ DUDEK AND ELIZABETH SPRANGEL

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: