A Multidimensional Ramsey Theorem

2025-04-30 0 0 296.14KB 10 页 10玖币

侵权投诉

DISCRETE ANALYSIS, 2024:21, 10 pp.

www.discreteanalysisjournal.com

A Multidimensional Ramsey Theorem

António Girão *‡Gal Kronenberg *†Alex Scott *‡

Received 9 April 2023; Published 31 December 2024

Abstract: In this paper, we prove a “multidimensional" generalisation of Ramsey’s Theorem

to cartesian products of graphs, showing that a doubly exponential upper bound is enough in

every dimension. More precisely, we prove that for every

r,n,d∈N

, in any

-colouring of the

edges of the Cartesian product

□dKN

copies of

there is a copy of

□dKn

such that the

edges in each direction are monochromatic, provided

N≥22C(d)rnd

. As an application of our

new approach we obtain improvements on the multidimensional Erd˝

os-Szekeres Theorem

proved by Fishburn and Graham 30 years ago thus conﬁrming a conjecture posed by Buci´

Sudakov, Tran.

Key words and phrases: Ramsey Theory, Erd˝

os-Szekeres.

1 Introduction

The study of Ramsey theory is a longstanding and central part of combinatorics. As usual, for positive

integers

r,k

, the Ramsey number

Rr(k)

is the smallest

for which every

-colouring of

contains

a monochromatic copy of

. Ramsey [

] showed in 1930 that these numbers exist. Since then,

Ramsey numbers have been studied extensively, upper and lower bounds have been proved and many

generalisations have been considered, see, e.g. [

]. Even for

r=2

, the asymptotics

are still not fully resolved. It is not hard to show that

R2(k)

grows at exponential rate, but the constant

in the exponent is yet not known: the best current bounds are

(1+o(1))√2(k+1)

e2k+1/2≤R2(k+1)≤

Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road,

Oxford, United Kingdom. E-mail: {girao,kronenberg,scott}@maths.ox.ac.uk.

†

Research supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska

Curie grant agreement No. 101030925, and by the Royal Commission for the Exhibition of 1851.

‡

Research supported by EPSRC grant EP/V007327/1. AS would like to thank the Department of Mathematics at the

University of Arizona where some of this work was completed.

onio Gir˜

ao, Gal Kronenberg, and Alex Scott

cb Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.19086/da.127777

arXiv:2210.09227v2 [math.CO] 31 Dec 2024

ANT ´

ONIO GIR ˜

AO, GAL KRONENBERG,AND ALEX SCOTT

e−clog2k2k

k

the lower bound due to Spencer [

] and upper bound by Sah [

]. For larger

, the gap

between the upper and lower bound is even larger, and even for

k=3

, we do not understand the behaviour

Rr(3)

r→∞

. Very recently, Conlon and Ferber [

], Wigderson [

], and Sawin [

] found nice

constructions which give the best known lower bounds for

Rr(k)

when

r≥3

. In a recent breakthrough,

Campos, Grifﬁths, Morris and Sahasrabudhe [

], reduced the the long standing upper bound of

(4−ε)k

. This is the ﬁrst exponential improvement over the upper bound of Erd˝

os and Szekeres, proved

in 1935.

In this paper, we prove a “multidimensional" generalisation of Ramsey’s Theorem for cartesian

products of graphs. Given two graphs

and

, we write

G□H

for the Cartesian product of

and

namely the graph with vertex set

V(G)×V(H)

in which

(x,y)

is joined to

(x′,y′)

if and only if

x=x′

and

yy′∈E(H)

xx′∈E(G)

and

y=y′

. The Cartesian product is associative, so it makes sense to

write

G1□G2□···□Gd

(without brackets) for the Cartesian product of

graphs; we write

□dG

for the

product

G□···□G

copies of

. Note that in a Cartesian product of

graphs

G1,...,Gd

, there is an

edge between

v= (v1,...,vd)

and

w= (w1,...,wd)

if and only if there is some

such that

viwi

is an edge

of Giand vj=wjfor j̸=i, and in this case we will say that the edge vw is in direction i.

Given a colouring

of the edges of

□dKn

, we say that

is monochromatic in every direction if for

each

i∈ {1,...,d}

there is some

such that all edges in direction

have colour

. For positive integers

r,d

, we deﬁne

Rr(d,n)

to be the smallest

such that every

-colouring of the edges of

□dKN

contains a

copy of

□dKn

that is monochromatic in every direction. Note that we cannot demand a copy of

□dKn

that has the same colour in every direction, as we are asking for a full-dimensional subgraph: for example,

□dKN

could be coloured with colour

for all edges in direction

and coloured with 2 for the edges in

all other directions. It is easy to see that if we demand a monochromatic copy of

□ℓKn

then

ℓ

must be at

most ⌈d/r⌉. It will follow from Theorem 1.1 that this is also tight.

It is not too hard to prove that

Rr(d,n)

exists by an iterated application of Ramsey’s Theorem.

However, this would only give an upper bound of tower-type as a function of

. Our main goal is to show

that a doubly exponential bound on ndsufﬁces.

Theorem 1.1. Let

be a positive integer. There exists

Cd>0

such that for every

n,r

the following holds.

For

N≥rrCdrnd

, every

-colouring of

□dKN

contains a copy of

□dKn

which is monochromatic in every

direction. That is, Rr(d,n)≤rrCdrnd

As an immediate corollary, we see that any

-edge colouring of

□dKN

contains a monochromatic

copy of □ℓKnfor ℓ=⌈d/r⌉.

Corollary 1.2. Let

n,d,r

be positive integers and

ℓ=⌈d/r⌉

. For

N≥rrCdrnd

, every

-edge-colouring of

□dKNcontains a monochromatic copy of □ℓKn. The value of ℓis tight.

Another foundational result in Ramsey theory appears in a paper Erd˝

os and Szekeres [

] from 1935:

any sequence of

n2+1

distinct real numbers contains either an increasing or decreasing subsequence of

length

n+1

. There are a number of different ways to generalise the Erd˝

os-Szekeres Theorem to higher

dimensions (see, for example, [

]). Perhaps the most natural approach was

developed thirty years ago by Fishburn and Graham [10].

-dimensional array is an injective function

from

A1×... ×Ad

where

A1,...Ad

are non-

empty subsets of

; we say

has size

|A1|×···×|Ad|

; if

|Ai|=n

for each

, it will be convenient to

DISCRETE ANALYSIS, 2024:21, 10pp. 2

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

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

10 玖币 0人已下载

立即下载

摘要：

DISCRETEANALYSIS,2024:21,10pp.www.discreteanalysisjournal.comAMultidimensionalRamseyTheoremAntónioGirão*‡GalKronenberg*†AlexScott*‡Received9April2023;Published31December2024Abstract:Inthispaper,weprovea“multidimensional"generalisationofRamsey’sTheoremtocartesianproductsofgraphs,showingthatadoublyexp...

展开>> 收起<<

A Multidimensional Ramsey Theorem.pdf

共10页,预览2页

还剩页未读，继续阅读

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

A Multidimensional Ramsey Theorem

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: