Universally Image Partition Regularity
7 pages
English

Universally Image Partition Regularity

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

Description

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 ...

Sujets

Informations

Publié par
Nombre de lectures 127
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 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, vN, 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~xSsuch 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 0c`(S\ {0}), letu, vN, 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~xS 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)(AB∈ A); (2)A 6=and/∈ A; (3) (A∈ A)(aA)(B∈ A)(a+BA); and (4) (A∈ A)(B∈ A)(B+BA).
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/SA) if wheneverS=Ciand i=1 v A∈ Athen there exists~xSandi∈ {1,2,∙ ∙ ∙, r}such that~xMCiA. 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/SA. S r Proof. LetS=CiandA∈ A. Bya standard compactness argument (see [5, i=1 S r Section 5.5] ) there existskNsuch 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) . Definition 1.3 we can chooseB∈ Asuch thatiBAfor alli∈ {1,2,∙ ∙ ∙, k}. Infact we can do this by induction.Let this be true fornN, and we chooseC∈ Asuch that iCAfor alli∈ {1,2,∙ ∙ ∙, n}by (4) of Definition 1.3, for. ThenC∈ Awe can choose D∈ Asuch thatD+DC(1),. ByB=CD∈ ATo this end, which does the rest. let us pickzBeach. Fori∈ {1,2,∙ ∙ ∙, r}let us setDi={t∈ {1,2,∙ ∙ ∙, k}:tzCi}. 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(CiA) . 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 setAS,A={pβS:Ap}. Thesets{A:AS}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 eachxS, the functionλx:βSβSdefined byλx(q) =x+qis continuous).Given p, qβSandAS, we have thatAp+qif and only if{xS:x+Aq} ∈p, wherex+A={yS:x+yA}.
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=Cr. Thenby [5, Theorem 4.20]Tis a compact right topological semigroup i=1 and we choose an idempotentpT. Hencethere existsi∈ {1,2,∙ ∙ ∙, r}such that ACipfor allA∈ Aby [5, Theorem 5.12] there exists a sequence. Thereforehxni n=1 ) thereforewe have inSsuch thatF S(hxnin=1ACiand A~xACi. 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 sequencehynin=0such that n n yn>2y0for eachnN. Letx0=y0and for eachnN, letxn=yn2y0. 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. PickkNsuch 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 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
mDefinition 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{aixt: eachFi∈ Pf(ω) and ifi < m, i=0tFi then maxFi<minFi+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βSandnN, thennpwill denote the ultrafilter determined by the set{nA:Ap}wherenA={nx:xA}. T Lemma 2.5Let(S,A)be a pair,T=clAandp=p+pT. Thenfor anyaN A∈A we haveapT.
Proof. TakeA∈ A. Thenusing (1) and (4) of Definition 1.3 and and applying induction we can findB∈ Asuch thataBA. NowBpso thataBap. HenceAap, and thereforeapT.
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 rN,S=Ci, andA∈ A, there existi∈ {1,2, . . . , r}and a sequencehxnisuch i=1n=0 thatM T(x~,a~)CiA. T Proof. LetT=clAby [5, Theorem 4.20]. ThenTis a compact right topological A∈A semigroup so that we can choose an idempotentpT. Letq=a0p+a1p+∙ ∙ ∙+amp. Then by the above lemmaqT. Soit suffices to show that wheneverQq, there is a sequencehxniinSsuch thatM T(a,~~x)Q. n=0 1 LetQqAssume first thatbe given.m= 0.Then (a0)Qpso 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
5
Nowassumethatm >0. Then
{yS:y+Qa1p+a2p+. . .+amp} ∈a0p
so that P={xS:(a0x) +Qa1p+a2p+. . .+amp} ∈p. Givenn∈ {1,2, . . . , m1}andx0, x1, . . . , xn1, letP(x0, x1, . . . , xn1) ={yS: (a0x0+. . .+an1xn1+any) +Qan+1p+. . .+amp}. Ifx0Pand for each i∈ {1,2, . . . , n1},xiP(x0, x1, . . . , xi1), thenP(x0, x1, . . . , xn1)p. Now givenx0, x1, . . . , xm1, let us setP(x0, x1, . . . , xm1) ={yS:a0x0+a1x1+. . .+am1xm1+amyQ}. Ifx0Pand for eachi∈ {1,2, . . . , m1}, xiP(x0, x1, . . . , xi1), thenP(x0, x1, . . . , xm1)p. ? ? Given anyBp, letB={xB:x+Bp}. ThenBpand by [[5], Lemma ? ? 4.14] for eachxB,x+Bp. ? Choosex0P. Letnωand assume that we have chosenx0, x1, . . . , xnsuch that P ? (1) if∅ 6=F⊆ {0,1, . . . , n}, thenxtP, and tF (2) ifk∈ {1,2, . . . ,min{m, n}},F0, F1, . . . , Fk∈ Pf({0,1, . . . , n}), and for eachj{0,1, . . . , k1}, maxFj<minFj+1, then P PP P ? xtP(xt, xt. . . ,xt) . tF tF tF tF k0 1k1 Both the hypothesis hold atn= 0, (2) vacuously. Forr∈ {0,1, . . . , n}, let X Er={xt:∅ 6=F⊆ {r, r+ 1, . . . , n}}. tF
Fork∈ {0,1, . . . , m1}andr∈ {0,1, . . . , n}, let P P Wk,r={(xt, . . . ,xt) :F0, F1, . . . , Fk∈ Pf({0,1, . . . , r}) tF tF 0k and for eachi∈ {0,1, . . . , k1},maxFi<minFi+1}
Note thatWk,r6=if and only ifkr. ? ? IfyE0, thenyP, soy+PpandP(y)p. Ifk∈ {1,2, . . . , m1}and (y0, y1, . . . , yk)Wk,m, then we haveykP(y0, y1, . . . , yk1). Whichimplies ? thatP(y0, y1, . . . , yk)pand thusP(y0, y1, . . . , yk)p. Ifr∈ {0,1, . . . , n1},k? {0,1, . . . ,min{m1, r}}, (y0, y1, . . . , yk)Wk,r, andzEr+1, thenzP(y0, y1, . . . , yk) ? soz+P(y0, y1, . . . , yk)p. ? ? Ifn= 0, letx1P(x0+P)P(x0) thenthe hypotheses are satisfied. Now assume thatn1 and pick T ? ? xn+1P(y+P) yE0 T T min{m1,n} ? P(y0, . . . , yk) k=0 (y ,...,y)W 0k k,m T TT T n1 min{m1,r} ? (z+P(y0, . . . , yk) ). r=0k=0 (y0,...,yk)Wk,rzEr+1
the electronic journal of combinatorics15(2008), #R141
6