COMPOSITE RAMSEY THEOREMS VIA TREES MATT BOWEN Abstract. We prove a theorem ensuring that the compositions of certain Ramsey families

2025-04-29 0 0 432.25KB 14 页 10玖币

侵权投诉

COMPOSITE RAMSEY THEOREMS VIA TREES

MATT BOWEN

Abstract.

We prove a theorem ensuring that the compositions of certain Ramsey families

are still Ramsey. As an application, we show that in any ﬁnite coloring of

there is an

inﬁnite set

and an as large as desired ﬁnite set

with (

)

∪

(

) monochromatic,

answering a question from a recent paper of Kra, Moreira, Richter, and Robertson. In fact,

we prove an iterated version of this result that also generalizes a Ramsey theorem of Bergelson

and Moreira that was previously only known to hold for ﬁelds. Our main new technique is

an extension of the color focusing method that involves trees rather than sequences.

1. Introduction

Ramsey theory on

is centered around characterizing the structures of the following

form.

Deﬁnition 1.1.

We say a family

B ⊆ P

(

) is

Ramsey

if for any ﬁnite coloring

N→

[

]

there is some A∈ B such that cis constant on A.

The

linear Rado families

, i.e. the Ramsey families

that are generated by the set

of solutions to a ﬁnite system of linear equations, are completely characterized by Rado’s

theorem [

]. Moreover, given any such family we can obtain a

geometric Rado family

composing a given coloring with the homomorphism

n7→

. For example, Schur’s theorem

tells us that

{{x, y, z}

is a linear Rado family, which in turn implies that

{{x, y, z}

is a geometric Rado family. From now on we will simply write, for

example, that {x, y, x +y}is Ramsey, a slight abuse of notation.

In contrast to the linear and geometric case, characterizations of other Ramsey families

are still quite elusive, and determining if even some of the simplest non-linear families are

Ramsey has been the subject of much recent study; see, e.g., [

], for some

recent rsults of this type. Here we further this line of work by showing that certain non-linear

compositions of Ramsey families are still Ramsey.

Theorem 1.2. Let Tbe the smallest collection of families of subsets of Nsuch that:

(1) If Bis a ﬁnite linear or geometric Rado family, then B ∈ T

(2) If B ∈ T,then for any ﬁnite set Pof integral polynomials and k∈Nthe family

{{x, xa, x +p(a) : a∈A, x ∈X, p ∈P}:X∈N

k, A ∈ B} ∈ T.

Date: October 2022.

McGill University, Montr´eal, Quebec, Canada. matthew.bowen2@mail.mcgill.ca .

arXiv:2210.14311v2 [math.CO] 21 Nov 2022

2 MATT BOWEN

Any family

B ∈ T

is Ramsey. Moreover, if the family is as in point (2) then there is

an inﬁnite set of x∈Nwitnessing this fact.

This theorem is somewhat abstract, so we discuss some concrete applications.

For the ﬁrst, consider the family

N

k

consisting of all

element subsets of

This is

a linear Rado family by the pigeonhole principle, and so applying Theorem 1.2 with

and

the constant polynomial n7→ nwe obtain the following:

Corollary 1.3.

In any ﬁnite coloring of

there is an inﬁnite set

and set

B∈N

k

such

that (A+B)∪(AB)is monochromatic.

The

|A|

|B|

= 1 case of this corollary is Moreira’s theorem [

]. Recently, in [

]

Question 8.4, Kra, Moreira, Richter, and Robertson asked if the above result is true when

is also required to be inﬁnite and stated that even the

|A|

|B|

= 2 case seemed out of

reach.

Applying Theorem 1.2 to the family from Corollary 1.3 again, we ﬁnd monochromatic

sets of the form

(A+B+C)∪(A+ (BC)) ∪(A(B+C)) ∪(ABC).(1)

Doing this repeatedly, we show:

Corollary 1.4. In any ﬁnite coloring of Nthere are sets A1, ..., An∈N

ksuch that

{a1◦1(a2◦2(... ◦n−2(an−1◦n−1an)...) : ai∈Ai,◦i∈ {+,·}}

is monochromatic.

Previously, the above result for

|Ai|

= 1 was known to hold in ﬁnite colorings of

by a

theorem of Bergelson and Moreira [

]. However, even the

|Ai|

= 1 case of Example 1was

open for colorings of N.

So far we have only considered applications of Theorem 1.2 that begin with the pigeonhole

principle as the base family. Instead starting with a geometric family, we obtain the following

common extension of the linear and geometric van der Waerden Theorems by applying

Theorem 1.2 with the geometric Rado family

{zyi, y

i≤k}

and the linear polynomials

n7→ in.

Corollary 1.5. The family {x+iy, xy, z ·xyi:i≤k}is Ramsey for any k∈N.

Notice that this tells us that any ﬁnite coloring of

contains arbitrarily long arithmetic

and geometric progressions of the same color and step size, and moreover with starting points

that are a simple multiplicative shift of each other. One hope might be to prove the following

reﬁnement of this result.

Question 1. Is the family {x+iy, xyi:i≤k}Ramsey for any k∈N?

Our proof of Theorem 1.2 builds oﬀ of the ideas used in Moreira’s proof that the family

{xy, x

is Ramsey [

]. We use the fact that there are many potential choices for

and

in each step of the proof to build a tree of possible choices for these values. From here we

deduce new Ramsey theorems by running color focusing arguments on this tree; see especially

Figures 1and 2for illustrations of this idea.

COMPOSITE RAMSEY THEOREMS VIA TREES 3

Acknowledgements.

Thanks to Zach Hunter and Marcin Sabok for many helpful comments

on an earlier version of this paper.

2. Notation and technical background

In this section we collect the notation and technical facts that will be used throughout the

paper. The reader should note that the proofs of the concrete Theorems in Section 3, which

contain almost all of the combinatorial ideas needed for the proof of our general theorem,

mostly manages to avoid these notations and relies on more well known facts. Namely, the

only thing from Subsection 2.2 needed in Section 3is the more usual

case of the

polynomial van der Waerden theorem, and Subsection 2.3 can be entirely skipped.

The main technical diﬃculty with the proof of Theorem 1.2 is that each step of our

induction will require us to prove Ramsey theoretic results on the space of polynomials with

an additional variable (see the discussion after the proof of Theorem 3.3), which leads to

notational diﬃculties if not combinatorial ones.

2.1.

Trees.

In this paper, by a

tree

we mean a collection of ﬁnite words (including the

empty word) where the

th letter comes from alphabet

An.

More precisely, given ﬁnite sets

A0, ..., AR,

we’ll consider trees of the form

S0≤i≤R+1 Qj<i Aj.

In particular,

is rooted

at the empty set, which has |A0|children, and so on.

Given a tree

as above, we deﬁne the

’th level of the tree as

Qj<i Aj.

Further, we

will use ato denote concatenation, i.e., given t∈Tiand p∈Ai, t ap∈Ti+1.

2.2.

Polynomial spaces, notions of size, and van der Waerden’s theorem.

As men-

tioned above, the proof of Theorem 1.2 will require us to consider spaces of many variabled

polynomials with rational coeﬃcients.

Deﬁnition 2.1.

Let

and having deﬁned

Pn,

let

Pn+1

be the set of all formal objects

of the form a1

b1xn+1 +a2

b2x2

n+1 +... +ak

bkxk

n+1,where k∈Nand aj, bj∈S0≤i≤nPi.

In particular,

[

]

the space of all formal polynomials of degree at least one with

rational coeﬃcients.

Given

P⊂Pn

and

d∈Pm,

(

) we mean the formal object obtained by replacing

every instance of

with

We will only do this in instances where

in which

case this is the composition of polynomials, or when

n−

where we can think of this

as evaluation. Note that in the latter case in general this might not be a subset of

Pn−1,

but

in all of our uses of this notation dwill have been chosen such that it is.

We will need a piecewise syndetic version of the polynomial van der Waerden theorem for

our proofs. To formally state this, we need the following deﬁnitions.

Deﬁnition 2.2.

•A set S⊆Pnis syndetic if there is a ﬁnite set F⊂Pnsuch that Pn=S−F.

•set T⊆Pnis thick if for any ﬁnite set F, there is a t∈Tsuch that tF ⊂T.

•

A set

A⊆Pn

piecewise syndetic

if there is a thick set

and a syndetic set

with S∩T⊆A.

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

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

10 玖币 0人已下载

立即下载

摘要：

COMPOSITERAMSEYTHEOREMSVIATREESMATTBOWENAbstract.WeproveatheoremensuringthatthecompositionsofcertainRamseyfamiliesarestillRamsey.Asanapplication,weshowthatinanynitecoloringofNthereisaninnitesetAandanaslargeasdesirednitesetBwith(A+B)[(AB)monochromatic,answeringaquestionfromarecentpaperofKra,Moreir...

展开>> 收起<<

COMPOSITE RAMSEY THEOREMS VIA TREES MATT BOWEN Abstract. We prove a theorem ensuring that the compositions of certain Ramsey families.pdf

共14页,预览3页

还剩页未读，继续阅读

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

COMPOSITE RAMSEY THEOREMS VIA TREES MATT BOWEN Abstract. We prove a theorem ensuring that the compositions of certain Ramsey families

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: