Universally Image Partition Regularity

pages

English

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

English

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Phiem

Nombre de lectures

Langue

English

Universally Image Partition Regularity
Dibyendu De
School of Mathematics, University of Witwatersrand
Private Bag 3, Wits 2050, South Africa
dibyendude@gmail.com
Ram Krishna Paul
Department of Mathematics, Jadavpur University
Kolkata-32, India
rmkpaul@gmail.com
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 ...

Voir

Publié par

Phiem

Nombre de lectures

Langue

English

Universally Image Partition Regularity

Dibyendu De School of Mathematics, University of Witwatersrand Private Bag 3, Wits 2050, South Africa dibyendude@gmail.com

Ram Krishna Paul Department of Mathematics, Jadavpur University Kolkata-32, India rmkpaul@gmail.com

Submitted: Sep1, 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 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 deﬁnition of image partition regularity. Deﬁnition 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 ﬁnitely 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 ﬁnitely many classes (orﬁnitely colored) there existxandysuch thatx,y, andx+yare contained in one cell of the

the electronic journal of combinatorics15(2008), #R141

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 ﬁnitely colored there must exist arbitrarily long arithmetic progressions. Thelength ﬁve 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 ﬁrst inﬁnite 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 compactiﬁcation 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. Deﬁnition 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 ﬁnitely colored andδ >0, there exists~x∈S such that the entries ofA~xare monochromatic and lie in the interval (−δ, δ). Being motivated by the deﬁnition of image partition regularity near zero we introduce the following deﬁnition. Deﬁnition 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

LetMbe au×vmatrix with entries fromω. ThenMis said to beimage partition S r regular overSwith respect toA(abbreviatedIP R/SA) if wheneverS=Ciand i=1 v A∈ Athen there exists~x∈Sandi∈ {1,2,∙ ∙ ∙, r}such that~xM⊆Ci∩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ω. Deﬁnition 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 ﬁnite 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/SA. S r Proof. LetS=CiandA∈ A. Bya standard compactness argument (see [5, i=1 S r Section 5.5] ) there existsk∈Nsuch that whenever{1,2,∙ ∙ ∙, k}=Dithere exists i=1 v u ~x∈ {1,2,∙ ∙ ∙, k}andi∈ {1,2,∙ ∙ ∙, r}such thatM~x∈(DiNow by (1) and (4) of) . Deﬁnition 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 Deﬁnition 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 setDi={t∈ {1,2,∙ ∙ ∙, k}:tz∈Ci}. S r v Then{1,2,∙ ∙ ∙, k}=Di. Sothere existsx~∈ {1,2,∙ ∙ ∙, k}andi∈ {1,2,∙ ∙ ∙, r}such i=1 u u that~Mx∈(Di) . Put~y=~zx. ThenM~y∈(Ci∩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 compactiﬁcation of a discrete semigroup.IfSis a discrete space, we take the points ˇ of the Stone-Cech compactiﬁcationβSofSto be the ultraﬁlters onS, identifying the principal ultraﬁlters 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→βSdeﬁned byρp(q) =q+pis continuous) withScontained in its topological center (meaning that for eachx∈S, the functionλx:βS→βSdeﬁned 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

2 InﬁniteMatrices The deﬁnition ofuniversally image partition regularityhas a natural generalization for the matrices of orderω×ω. Wemention here that when we talk of an inﬁnite matrix we shall assume that each row of it contains only ﬁnitely 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 inﬁnite case.First we observe that the ﬁnite 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 ﬁnitely 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=Cr. 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∩Ci∈pfor allA∈ Aby [5, Theorem 5.12] there exists a sequence. Thereforehxni n=1 ∞ ) thereforewe have inSsuch thatF S(hxnin=1⊆A∩Ciand A~x⊆A∩Ci. From [1, Lemma 3.9] it follows that there are inﬁnite image partition regular matrices which are not universally image partition regular. In fact if we consider the following inﬁnite matrix   1 0 0 0. . . 2 1 0 0. . . 4 0 1 0. . . M=  8 0 0 1. . .   . . . . . .. ∞ andNis ﬁnitely colored we can choose a monochromatic sequencehynin=0such that n n yn>2y0for eachn∈N. Letx0=y0and for eachn∈N, letxn=yn−2y0. 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 x0=y0>0. Pickk∈Nsuch that 2x0>1. Thenyk= 2x0+xk>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 inﬁnite 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

m∞ Deﬁnition 2.1Letm∈ω,~a=haiii=0be a sequence inN, and~x=hxnin=0be a sequence inSby. ThenMilliken-Taylor systemdetermined by~aand~x, denoted by P P m M T(~a,~x) we mean the following set{ai∙xt: eachFi∈ Pf(ω) and ifi < m, i=0t∈Fi then maxFi<minFi+1}.

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

Deﬁnition 2.2Let~abe a ﬁnite or inﬁnite sequence inωwith only ﬁnitely 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.

Deﬁnition 2.3Let~abe a compressed sequence inN. AMilliken-Taylor matrix deter-mined by~ais anω×ωmatrixAsuch that the rows ofAare all possible rows with ﬁnitely 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 inﬁnite sequence inS, then the set of entries of~xAis preciselyM T(x~,a~).

Deﬁnition 2.4If (S,+) is a discrete semigroup,p∈βSandn∈N, thenn∙pwill denote the ultraﬁlter 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 Deﬁnition 1.3 and and applying induction we can ﬁndB∈ 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=haiii=0ompressed sequence inN, and letAbe a Milliken-Taylor matrix determined by~a. ThenAis IPR/SAis, whenever. That S r ∞ r∈N,S=Ci, andA∈ A, there existi∈ {1,2, . . . , r}and a sequencehxnisuch i=1n=0 thatM T(x~,a~)⊆Ci∩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=a0∙p+a1∙p+∙ ∙ ∙+am∙p. Then by the above lemmaq∈T. Soit suﬃces to show that wheneverQ∈q, there is a ∞ sequencehxniinSsuch thatM T(a,~~x)⊆Q. n=0 −1 LetQ∈qAssume ﬁrst thatbe given.m= 0.Then (a0)Q∈pso there is a sequence ∞ ∞−1 hxnisuch thatF S(hxni)⊆(a0)Q. ThenM T(~xa,~)⊆Q. n=0n=0

the electronic journal of combinatorics15(2008), #R141

Nowassumethatm >0. Then

{y∈S:−y+Q∈a1∙p+a2∙p+. . .+am∙p} ∈a0∙p

so that P={x∈S:−(a0∙x) +Q∈a1∙p+a2∙p+. . .+am∙p} ∈p. Givenn∈ {1,2, . . . , m−1}andx0, x1, . . . , xn−1, letP(x0, x1, . . . , xn−1) ={y∈S: −(a0∙x0+. . .+an−1∙xn−1+an∙y) +Q∈an+1∙p+. . .+am∙p}. Ifx0∈Pand for each i∈ {1,2, . . . , n−1},xi∈P(x0, x1, . . . , xi−1), thenP(x0, x1, . . . , xn−1)∈p. Now givenx0, x1, . . . , xm−1, let us setP(x0, x1, . . . , xm−1) ={y∈S:a0∙x0+a1∙ x1+. . .+am−1∙xm−1+am∙y∈Q}. Ifx0∈Pand for eachi∈ {1,2, . . . , m−1}, xi∈P(x0, x1, . . . , xi−1), thenP(x0, x1, . . . , xm−1)∈p. ? ? Given anyB∈p, letB={x∈B:−x+B∈p}. ThenB∈pand by [[5], Lemma ? ? 4.14] for eachx∈B,−x+B∈p. ? Choosex0∈P. Letn∈ωand assume that we have chosenx0, x1, . . . , xnsuch that P ? (1) if∅ 6=F⊆ {0,1, . . . , n}, thenxt∈P, and t∈F (2) ifk∈ {1,2, . . . ,min{m, n}},F0, F1, . . . , Fk∈ Pf({0,1, . . . , n}), and for eachj∈ {0,1, . . . , k−1}, maxFj<minFj+1, then P PP P ? xt∈P(xt, xt. . . ,xt) . t∈F t∈F t∈F t∈F k0 1k−1 Both the hypothesis hold atn= 0, (2) vacuously. Forr∈ {0,1, . . . , n}, let X Er={xt:∅ 6=F⊆ {r, r+ 1, . . . , n}}. t∈F

Fork∈ {0,1, . . . , m−1}andr∈ {0,1, . . . , n}, let P P Wk,r={(xt, . . . ,xt) :F0, F1, . . . , Fk∈ Pf({0,1, . . . , r}) t∈F t∈F 0k and for eachi∈ {0,1, . . . , k−1},maxFi<minFi+1}

Note thatWk,r6=∅if and only ifk≤r. ? ? Ify∈E0, theny∈P, so−y+P∈pandP(y)∈p. Ifk∈ {1,2, . . . , m− 1}and (y0, y1, . . . , yk)∈Wk,m, then we haveyk∈P(y0, y1, . . . , yk−1). Whichimplies ? thatP(y0, y1, . . . , yk)∈pand thusP(y0, y1, . . . , yk)∈p. Ifr∈ {0,1, . . . , n−1},k∈ ? {0,1, . . . ,min{m−1, r}}, (y0, y1, . . . , yk)∈Wk,r, andz∈Er+1, thenz∈P(y0, y1, . . . , yk) ? so−z+P(y0, y1, . . . , yk)∈p. ∗? ? Ifn= 0, letx1∈P∩(−x0+P)∩P(x0) thenthe hypotheses are satisﬁed. Now assume thatn≥1 and pick T ? ? xn+1∈P∩(−y+P) y∈E0 T T min{m−1,n} ? ∩P(y0, . . . , yk) k=0 (y ,...,y)∈W 0k k,m T TT T n−1 min{m−1,r} ? ∩(−z+P(y0, . . . , yk) ). r=0k=0 (y0,...,yk)∈Wk,rz∈Er+1

the electronic journal of combinatorics15(2008), #R141

Voir