Universally Image Partition Regularity

Description

Universally Image Partition Regularity
Dibyendu De
School of Mathematics, University of Witwatersrand
Private Bag 3, Wits 2050, South Africa
[e-mail]
Ram Krishna Paul
Department of Mathematics, Jadavpur University
Kolkata-32, India
[e-mail]
Submitted: Sep 1, 2008; Accepted: Oct 29, 2008; Published: Nov 14, 2008
Mathematics Subject Classi cations: Primary 54D35; Secondary 22A15, 05D10, 54D80.
Abstract
Many of the classical results of Ramsey Theory, for example Schur’s Theorem,
van der Waerden’s Theorem, Finite Sums Theorem, are naturally stated in terms of
image partition regularity of matrices. Many characterizations are known of image
partition regularity over N and other subsemigroups of (R;+). In this paper we
introduce a new notion which we call universally image partition regular matrices,
which are in fact image partition regular over all semigroups and everywhere. We
also prove that such matrices exist in abundance.
1 Introduction
Many of the classical results of Ramsey Theory are naturally stated in terms of image
partition regularity of matrices. We start this discussions with the following de nition of
image partition regularity.
De nition 1.1 Let S be a subsemigroup of (R; +), let u; v 2 N, and let A be a u v
matrix with entries from Q. Then A is image partition regular over S (abbreviated IPR/S)
vif and only if, whenever Snf0g is nitely colored there exists ~x2 S such that the entries
of A~x are monochromatic.
One of the earliest results ...

Sujets

• Matrix
• Demi-groupe
• Universally Speaking
• Théorème de Rice
• Paper launch
• Compactifié d'Alexandroff

Informations

• Publié par: Phiem
• Nombre de lectures: 127
• Langue: English

Extrait

Universally Image Partition Regularity

Dibyendu De School of Mathematics, University of Witwatersrand Private Bag 3, Wits 2050, South Africa [e-mail]

Ram Krishna Paul Department of Mathematics, Jadavpur University Kolkata-32, India [e-mail]

Submitted: Sep1, 2008; Accepted:Oct 29, 2008; Published:Nov 14, 2008 Mathematics Subject Classifications:Primary 54D35; Secondary 22A15, 05D10, 54D80.

Abstract Many of the classical results of Ramsey Theory, for example Schur’s Theorem, van der Waerden’s Theorem, Finite Sums Theorem, are naturally stated in terms of image partition regularityof matrices.Many characterizations are known of image partition regularity overNand other subsemigroups of (R,this paper we+). In introduce a new notion which we calluniversally image partition regular matrices, which are in fact image partition regular over all semigroups and everywhere.We also prove that such matrices exist in abundance.

1 Introduction Many of the classical results of Ramsey Theory are naturally stated in terms ofimage partition regularityof matrices.We start this discussions with the following definition of image partition regularity. Definition 1.1LetSbe a subsemigroup of (R,+), letu, v∈N, and letAbe au×v matrix with entries fromQ. ThenAisimage partition regular overS(abbreviated IPR/S) v if and only if, wheneverS\ {0}is finitely colored there exists~x∈Ssuch that the entries of~Axare monochromatic. One of the earliest results of Ramsey Theory is Schur’s Theorem [9] which says that whenever the setNof positive integers is partitioned into finitely many classes (orfinitely colored) there existxandysuch thatx,y, andx+yare contained in one cell of the

the electronic journal of combinatorics15(2008), #R141

1

partition (or aremonochromatictheorem may also be viewed as saying that the). Schur’s matrix   1 0   0 1 1 1 isimage partition regularoverN. Another of the earliest results of Ramsey Theory is van der Waerden’s Theorem [11] which says that wheneverNis finitely colored there must exist arbitrarily long arithmetic progressions. Thelength five version of van der Waerden’s Theorem is clearly equivalent to the statement that the matrix   1 0 1 1 1 2    1 3 1 4 is image partition regular. Generally image partition regularity of a matrix is considered over certain semigroups. In this paper we are interested in the class of matrices with entries fromω, whereω= N∪ {0}is the first infinite cardinal, which are image partition regular over all semigroups and everywhere in the sense explained latter.Unless otherwise stated our semigroups will always be considered with the discrete topology. ˇ [3] is a paper concerned with algebraic results in the Stone-Cech compactification of various dense subsemigroups of (R,In [1] a stronger+) with the discrete topology. notion of image partition regularity over various dense subsemigroups of (R,+) has been introduced. Definition 1.2LetSbe a subsemigroup of (R,+) with 0∈c`(S\ {0}), letu, v∈N, and letAbe au×vmatrix with entries fromQ. ThenAisimage partition regular overS v near zeroif and only if, wheneverS\ {0}is finitely colored andδ >0, there exists~x∈S such that the entries ofA~xare monochromatic and lie in the interval (−δ, δ). Being motivated by the definition of image partition regularity near zero we introduce the following definition. Definition 1.3Let (S,+) be a semigroup andA ⊆ P(S) satisfying the following prop- erties: (1) (∀A∈ A)(∀B∈ A)(A∩B∈ A); (2)A 6=∅and∅/∈ A; (3) (∀A∈ A)(∀a∈A)(∃B∈ A)(a+B⊆A); and (4) (∀A∈ A)(∃B∈ A)(B+B⊆A).

the electronic journal of combinatorics15(2008), #R141

2

LetMbe au×vmatrix with entries fromω. ThenMis said to beimage partition S r regular overSwith respect toA(abbreviatedIP R/S A ) if wheneverS=C i and i=1 v A∈ Athen there exists~x∈Sandi∈ {1,2,∙ ∙ ∙, r}such that~xM⊆C i ∩A. For some explanations we mention that in the case of image partition regularity near zero over a dense subsemigroupSofR, one hasA={(−δ, δ)∩S:δ >0}. From now on by a pair (S,A) we shall always mean a semigroupSwithA ⊆ P(S) satisfying the above four properties.Further any matrix will be considered with entries fromω. Definition 1.4Au×vmatrixMis said to beuniversally image partition regularif given any pair (S,A),Mis image partition regular overSwith respect toA. In the following discussions we shall observe that for matrices of finite order image partition regularity and universally image partition regularity are the same notion. Lemma 1.5Let(S,A)be a pair andMbe au×vmatrix with entries fromω. ThenM is image partition regular overNimplies thatMisIP R/S A . S r Proof. LetS=C i andA∈ A. Bya standard compactness argument (see [5, i=1 S r Section 5.5] ) there existsk∈Nsuch that whenever{1,2,∙ ∙ ∙, k}=D i there exists i=1 v u ~x∈ {1,2,∙ ∙ ∙, k}andi∈ {1,2,∙ ∙ ∙, r}such thatM~x∈(D i Now by (1) and (4) of) . Definition 1.3 we can chooseB∈ Asuch thatiB⊆Afor alli∈ {1,2,∙ ∙ ∙, k}. Infact we can do this by induction.Let this be true forn∈N, and we chooseC∈ Asuch that iC⊆Afor alli∈ {1,2,∙ ∙ ∙, n}by (4) of Definition 1.3, for. ThenC∈ Awe can choose D∈ Asuch thatD+D⊆C(1),. ByB=C∩D∈ ATo this end, which does the rest. let us pickz∈Beach. Fori∈ {1,2,∙ ∙ ∙, r}let us setD i ={t∈ {1,2,∙ ∙ ∙, k}:tz∈C i }. S r v Then{1,2,∙ ∙ ∙, k}=D i . Sothere existsx~∈ {1,2,∙ ∙ ∙, k}andi∈ {1,2,∙ ∙ ∙, r}such i=1 u u that~Mx∈(D i ) . Put~y=~zx. ThenM~y∈(C i ∩A) . As an immediate corollary of the above lemma we get the following. Corollary 1.6LetMbe au×vmatrix with entries fromω. ThenMis universally image partition regular if and only if it is image partition regular overN. ˇ To end this introductory discussions let us discuss the algebra of the Stone-Cech compactification of a discrete semigroup.IfSis a discrete space, we take the points ˇ of the Stone-Cech compactificationβSofSto be the ultrafilters onS, identifying the principal ultrafilters with the points ofS(and thus pretending thatS⊆βSa). Given setA⊆S,A={p∈βS:A∈p}. Thesets{A:A⊆S}form a basis for the open sets ofSas well as a basis for the closed sets ofS. Given a discrete semigroup (S,+) the operation extends toβSmaking (βS,+) a right topological semigroup (meaning that for eachp∈βS, the functionρ p :βS→βSdefined byρ p (q) =q+pis continuous) withScontained in its topological center (meaning that for eachx∈S, the functionλ x :βS→βSdefined byλ x (q) =x+qis continuous).Given p, q∈βSandA⊆S, we have thatA∈p+qif and only if{x∈S:−x+A∈q} ∈p, where−x+A={y∈S:x+y∈A}.

the electronic journal of combinatorics15(2008), #R141

3

2 InfiniteMatrices The definition ofuniversally image partition regularityhas a natural generalization for the matrices of orderω×ω. Wemention here that when we talk of an infinite matrix we shall assume that each row of it contains only finitely many nonzero elements.In the previous section we have seen that if a matrix with entries fromωis image partition regular overNthen it is universally image partition regular.In this section we see that there are a lots of variety in the infinite case.First we observe that the finite sums matrix   1 0 0 0. . . 0 1 0 0. . . 1 1 0 0. . . 0 0 1 0. . . A= 0 1 1 0. . .   1 1 1 0. . .   . . . . . . . (whose rows are all vectors with entries from{0,1}with only finitely many 1’s and not all T 0’s) is universally image partition regular.In fact let (S,A) be a pair withT=clA A∈A S r andS=C r . Thenby [5, Theorem 4.20]Tis a compact right topological semigroup i=1 and we choose an idempotentp∈T. Hencethere existsi∈ {1,2,∙ ∙ ∙, r}such that ∞ A∩C i ∈pfor allA∈ Aby [5, Theorem 5.12] there exists a sequence. Thereforehx n i n=1 ∞ ) thereforewe have inSsuch thatF S(hx n i n=1 ⊆A∩C i and A~x⊆A∩C i . From [1, Lemma 3.9] it follows that there are infinite image partition regular matrices which are not universally image partition regular. In fact if we consider the following infinite matrix   1 0 0 0. . . 2 1 0 0. . . 4 0 1 0. . . M=  8 0 0 1. . .   . . . . . . . ∞ andNis finitely colored we can choose a monochromatic sequencehy n i n=0 such that n n y n >2y 0 for eachn∈N. Letx 0 =y 0 and for eachn∈N, letx n =y n −2y 0 . Then M~x=y~, so thatMis IPR/Nif we take. ButA={(0, ) : >0}thenMis not + + ω ω IPR/Rfact if possible let there exists. In~x∈(Rthat) such~y=~xA∈((0,Then1)) . A k k x 0 =y 0 >0. Pickk∈Nsuch that 2x 0 >1. Theny k = 2x 0 +x k >1, a contradiction. Now we shall turn our attention to the Milliken-Taylor matrices with entries fromω which are one of the main sources of infinite image partition regular matrices overN. In the following theorem we shall prove that these matrices are also universally image partition regular.

the electronic journal of combinatorics15(2008), #R141

4

m∞ Definition 2.1Letm∈ω,~a=ha i i i=0 be a sequence inN, and~x=hx n i n=0 be a sequence inSby. ThenMilliken-Taylor systemdetermined by~aand~x, denoted by P P m M T(~a,~x) we mean the following set{a i ∙x t : eachF i ∈ P f (ω) and ifi < m, i=0t∈F i then maxF i <minF i+1 }.

Notice that if~ahas adjacent repeated entries and~cis obtained from~aby deleting such repetitions, then for any infinite sequence~x, one hasM T(~a,~x)⊆M T(~,xc~), so it suffices to consider sequences~cwithout adjacent repeated entries.

Definition 2.2Let~abe a finite or infinite sequence inωwith only finitely many nonzero entries. Thenc(~a) is the sequence obtained from~aby deleting all zeroes and then deleting all adjacent repeated entries.The sequencec(~a) is thecompressed formof~a. If~a=c(~a), then~ais acompressed sequence.

For example, if~a=h0,1,0,0,1,2,0,0,2,2,0,0, . . .i, thenc(~a) =h1,2i.

Definition 2.3Let~abe a compressed sequence inN. AMilliken-Taylor matrix deter- mined by~ais anω×ωmatrixAsuch that the rows ofAare all possible rows with finitely many nonzero entries and compressed form equal to~a.

Notice that ifAis a Milliken-Taylor matrix whose rows all have compressed form~a and~xis an infinite sequence inS, then the set of entries of~xAis preciselyM T(x~,a~).

Definition 2.4If (S,+) is a discrete semigroup,p∈βSandn∈N, thenn∙pwill denote the ultrafilter determined by the set{nA:A∈p}wherenA={nx:x∈A}. T Lemma 2.5Let(S,A)be a pair,T=clAandp=p+p∈T. Thenfor anya∈N A∈A we havea∙p∈T.

Proof. TakeA∈ A. Thenusing (1) and (4) of Definition 1.3 and and applying induction we can findB∈ Asuch thataB⊆A. NowB∈pso thataB∈a∙p. HenceA∈a∙p, and thereforea∙p∈T.

m Theorem 2.6Let(S,A)b bea c e a pair and~a=ha i i i=0 ompressed sequence inN, and letAbe a Milliken-Taylor matrix determined by~a. ThenAis IPR/S A is, whenever. That S r ∞ r∈N,S=C i , andA∈ A, there existi∈ {1,2, . . . , r}and a sequencehx n isuch i=1 n=0 thatM T(x~,a~)⊆C i ∩A. T Proof. LetT=clAby [5, Theorem 4.20]. ThenTis a compact right topological A∈A semigroup so that we can choose an idempotentp∈T. Letq=a 0 ∙p+a 1 ∙p+∙ ∙ ∙+a m ∙p. Then by the above lemmaq∈T. Soit suffices to show that wheneverQ∈q, there is a ∞ sequencehx n iinSsuch thatM T(a,~~x)⊆Q. n=0 −1 LetQ∈qAssume first thatbe given.m= 0.Then (a 0 )Q∈pso there is a sequence ∞ ∞−1 hx n isuch thatF S(hx n i)⊆(a 0 )Q. ThenM T(~xa,~)⊆Q. n=0n=0

the electronic journal of combinatorics15(2008), #R141

5

Nowassumethatm >0. Then

{y∈S:−y+Q∈a 1 ∙p+a 2 ∙p+. . .+a m ∙p} ∈a 0 ∙p

so that P={x∈S:−(a 0 ∙x) +Q∈a 1 ∙p+a 2 ∙p+. . .+a m ∙p} ∈p. Givenn∈ {1,2, . . . , m−1}andx 0 , x 1 , . . . , x n−1 , letP(x 0 , x 1 , . . . , x n−1 ) ={y∈S: −(a 0 ∙x 0 +. . .+a n−1 ∙x n−1 +a n ∙y) +Q∈a n+1 ∙p+. . .+a m ∙p}. Ifx 0 ∈Pand for each i∈ {1,2, . . . , n−1},x i ∈P(x 0 , x 1 , . . . , x i−1 ), thenP(x 0 , x 1 , . . . , x n−1 )∈p. Now givenx 0 , x 1 , . . . , x m−1 , let us setP(x 0 , x 1 , . . . , x m−1 ) ={y∈S:a 0 ∙x 0 +a 1 ∙ x 1 +. . .+a m−1 ∙x m−1 +a m ∙y∈Q}. Ifx 0 ∈Pand for eachi∈ {1,2, . . . , m−1}, x i ∈P(x 0 , x 1 , . . . , x i−1 ), thenP(x 0 , x 1 , . . . , x m−1 )∈p. ? ? Given anyB∈p, letB={x∈B:−x+B∈p}. ThenB∈pand by [[5], Lemma ? ? 4.14] for eachx∈B,−x+B∈p. ? Choosex 0 ∈P. Letn∈ωand assume that we have chosenx 0 , x 1 , . . . , x n such that P ? (1) if∅ 6=F⊆ {0,1, . . . , n}, thenx t ∈P, and t∈F (2) ifk∈ {1,2, . . . ,min{m, n}},F 0 , F 1 , . . . , F k ∈ P f ({0,1, . . . , n}), and for eachj∈ {0,1, . . . , k−1}, maxF j <minF j+1 , then P PP P ? x t ∈P(x t , x t . . . ,x t ) . t∈F t∈F t∈F t∈F k 0 1 k−1 Both the hypothesis hold atn= 0, (2) vacuously. Forr∈ {0,1, . . . , n}, let X E r ={x t :∅ 6=F⊆ {r, r+ 1, . . . , n}}. t∈F

Fork∈ {0,1, . . . , m−1}andr∈ {0,1, . . . , n}, let P P W k,r ={(x t , . . . ,x t ) :F 0 , F 1 , . . . , F k ∈ P f ({0,1, . . . , r}) t∈F t∈F 0 k and for eachi∈ {0,1, . . . , k−1},maxF i <minF i+1 }

Note thatW k,r 6=∅if and only ifk≤r. ? ? Ify∈E 0 , theny∈P, so−y+P∈pandP(y)∈p. Ifk∈ {1,2, . . . , m− 1}and (y 0 , y 1 , . . . , y k )∈W k,m , then we havey k ∈P(y 0 , y 1 , . . . , y k−1 ). Whichimplies ? thatP(y 0 , y 1 , . . . , y k )∈pand thusP(y 0 , y 1 , . . . , y k )∈p. Ifr∈ {0,1, . . . , n−1},k∈ ? {0,1, . . . ,min{m−1, r}}, (y 0 , y 1 , . . . , y k )∈W k,r , andz∈E r+1 , thenz∈P(y 0 , y 1 , . . . , y k ) ? so−z+P(y 0 , y 1 , . . . , y k )∈p. ∗? ? Ifn= 0, letx 1 ∈P∩(−x 0 +P)∩P(x 0 ) thenthe hypotheses are satisfied. Now assume thatn≥1 and pick T ? ? x n+1 ∈P∩(−y+P) y∈E 0 T T min{m−1,n} ? ∩P(y 0 , . . . , y k ) k=0 ( y ,...,y)∈W 0 k k,m T TT T n− 1 min{m−1,r} ? ∩(−z+P(y 0 , . . . , y k ) ). r=0 k=0 ( y 0 ,...,y k )∈W k,r z∈E r+1

the electronic journal of combinatorics15(2008), #R141

6