Matematikai Intézet
Doktori értekezés tézisei Néhány Ramsey-és anti-Ramsey-típusú eredmény a kombinatorikus számelméletben és geometriában Borbély József
ELTE, Matematikai Doktori Iskola Az iskola vezet® je: Laczkovich Miklós, professzor, a Magyar Tudományos Akadémia rendes tagja
Elméleti doktori program Programfelel®s: Sz¶cs András, professzor, a Magyar Tudományos Akadémia levelez® tagja
Konzulensek: Károlyi Gyula, egyetemi tanár, az MTA
doktora Sárközy András, Professzor Emeritus Eötvös Loránd Tudományegyetem, Budapest, 2015
1
Az értekezés tézisei
Ebben a disszertációban kombinatorikus módszerek néhány alkalmazását kívánom bemutatni a számelméletben, csoportelméletben és a geometriai gráfelméletben. A kombinatorikus módszereket manapság a matematika mély és aktuális témájának tekintik. Jómagam f®ként Ramsey- és anti-Ramsey-típusú (vagy rainbow-típusú) problémákat vizsgálok a dolgozatomban. Az említett témákban cikkeket közl® folyóiratok nagy száma is tanúsítja az említett területek létjogosultságát. A következ® folyóiratok mindegyikében a fenti témákban jelennek meg cikkek (a teljesség igénye nélkül): Combinatorica , Discrete and Computational Geometry, Integers, Journal of Combinatorics and Number Theory, Moscow Journal of Combinatorics and Number Theory, The Electronic Journal of Combinatorics. A dolgozat egésze során Ramsey-típusú problémákra fókuszálunk. A dolgozatban akkor beszélünk Ramsey-típusú problémáról, ha az eredmény a következ®képp fogalmazható meg: ha kiszínezzük egy "nagy" struktúra minden egyes elemét k darab el®re megadott szín valamelyikével, akkor a konkrét színezést®l függetlenül mindenképpen találunk egy el®írt méret¶ egyszín¶ részstruktúrát. Az els® ilyen típusú eredmény Frank P. Ramsey-t®l származik (lsd. [13]). 1930-ban bekövetkezett halála óta számos új Ramsey-típusú problémát vetettek fel és oldottak meg. A téma kiterjedt szakirodalommal bír. Graham, Rotshild és Spencer könyve ([13]) a terület egyik alapm¶ve. Landman könyve ([27]) sok fontos Ramsey-típusú számelméleti eredményt tartalmaz. Különbséget kell tennünk Ramsey-típusú eredmények és s¶r¶ségi tételek között. Akkor beszélünk s¶r¶ségi tételr®l, ha az eredmény a következ®képpen fogalmazható meg: ha kiválasztjuk egy adott halmaz egy elég nagy részhalmazát, akkor ennek a részhalmaznak szükségképpen van egy olyan részhalmaza, ami valamilyen általunk már el®írt tulajdonságokkal bír. Nyilvánvaló módon a s¶r¶ségi tételek er®sebbek a Ramsey-típusú tételeknél. Vagyis lehetséges, hogy Ramsey-típusú eredményt találunk s¶r¶ségi tétel megléte nélkül, viszont ha belátunk egy s¶r¶ségi tételt, akkor Ramsey-típusú eredménynek is kell lennie. Tisztázásra szorul, hogy mit értünk rainbow Ramsey-típusú (vagy 2
másnéven anti-Ramsey-típusú) tétel alatt. Ilyenkor is kiszínezzük egy adott halmaz minden egyes elemét k darab el®re megadott szín valamelyikével, de most el®írt típusú tarka részstruktúrákat keresünk. A disszertáció során f®ként a számelméletben és a hozzá kapcsolódó területeken ismertetünk Ramsey- és anti-Ramsey-típusú eredményeket. Az els® fejezet [2] alapján készült. Ebben a fejezetben Roth egy problémája a kiindulópont (lsd. [17]), amire Erd®s, Sárközy és T. Sós adott elemi megoldást (lsd. [11]). Módszereik kiterjesztésével általánosabb eredményeket érünk el. Az r-dimenziós vektorok egy speciális részhalmazának k-színezéseire nézve megvizsgáljuk, hogy aszimptotikusan legalább hány olyan r-dimenziós vektor van, ami (a színezést®l függetlenül) el®áll különböz®, azonos szín¶ r-dimenziós vektorok összegeként. Az els® fejezetben a következ® jelöléseket használjuk: tetsz®leges k és l pozitív egészekre (ahol k ≤ l), (k, l) jelöli a {k, k + 1, · · · , l} halmazt. Valamint tetsz®leges r pozitív egész és H , H , · · · , H halmazok esetén a felsorolt r darab halmaz direkt szorzatát H × H × · · · × H jelöli. Ha H = H = · · · = H = H , akkor a H = H × H × · · · × H jelölést használjuk. Az els® fejezetben el®ször belátjuk az alábbi additív tételt: 1
2
r
1
r
r
1
2
r
2
1
2
r
Rögzített r, s és k pozitív egészekhez létezik olyan m0 pozitív egész, ami eleget tesz a következ® feltételeknek: tetsz®leges m > m0 és a (1, m)r halmaz bármely k- színezése esetén legalább Tétel 1.
h m ir s
− 3 · 2r−1 mr
1−2−ks+k−1
darab olyan ~x vektor van a (1, m)r halmazban, amelyhez ugyanebben a halmazban találhatóak olyan különböz®, azonos színü x~1 , x~2 , · · · , x~s vektorok, amelyek összege ~x.
Ebben a fejezetben az el®állítások számára vonatkozóan is bizonyítunk egy eredményt: Tétel 2.
Tetsz®leges α és β valós számokhoz, amik eleget tesznek az αr + β r ≤
3
1 22r+1 k
feltételnek, létezik olyan mαβ pozitív egész, hogy bármely m > mαβ egész szám és a Nr halmaz elemeinek minden k - színezése esetén az (1, m)r halmaz olyan r elemeinek száma, amik több, mint β2 mr -féleképpen állnak el® két azonos szín¶, különböz® vektor összegeként, legalább αr mr .
A második fejezet [3] alapján készült. Ebben a Roth-problémát más aspektusból vizsgáljuk. Az el®z®ekkel analóg eredményeket keresünk Abel-csoportokban, de ezúttal rainbow-típusúakat. Pontosabban speciálisan választott G Abel-csoportokban az elemek tetsz®leges k-színezése mellett (általában felteszszük, hogy minden színt felhasználunk) keressük azoknak a csoportelemeknek a minimális számát, amik el®állnak r darab olyan elem összegeként, amik különböz® szín¶ek. El®ször elemi úton bizonyítjuk a következ® tételt: Az 1, 2, ..., n pozitív egészek minden olyan k-színezése esetén, ahol az i-edik szín éppen ni -szer fordul el® (i = 1, 2, ..., k ) és n1 ≥ n2 ≥ · · · ≥ nk , P legfeljebb r − 1 + r−1 i=1 (r − i) ni darab {1, 2, · · · , n}-beli szám nem állítható el® r darab különböz® szín¶ szám összegeként (r ≥ 1).
Tétel 3.
Ezt követ®en véges Abel-csoportokban vizsgálunk hasonló kérdéseket. Kneser tételét felhasználva belátjuk az alábbit: Az m-edrend¶, véges, additív G Abel-csoport elemeinek minden olyan k -színezése mellett, ahol minden színt felhasználunk, legalább Tétel 4.
(k − 1) · m m min m − , Dk (G) dk (G)
olyan eleme van a csoportnak, ami el®áll a csoport k különböz® szín¶ elemének összegeként (itt dk (G) jelöli az m szám k -nál nem nagyobb maximális, míg Dk (G) az m szám k -nál nagyobb legkisebb osztóját).
Majd Vosper tételét felhasználva belátjuk az alábbi tételt Z -ben: p
Ha Zp elemeit k ≥ 2 darab színnel színezzük úgy, hogy minden szín el®fordul, akkor Zp -nek legalább p − 1 db eleme felírható Zp -nek k − 1 darab különböz® szín¶ elemének összegeként.
Tétel 5.
4
Sejtésem szerint a következ® er®sebb állítás is teljesül: Ha Zp elemeit k ≥ 4 darab színnel színezzük úgy, hogy minden szín el®fordul, akkor Zp -ben minden elem felírható Zp -nek k − 1 darab különböz® szín¶ elemének összegeként. Sejtés 1.
Természetesen vet®dik fel a kérdés, hogy miként lehetne az 5. tétel eredményét kiterjeszteni egyéb véges Abel-csoportokra. Ezzel kapcsolatos sejtésem a következ®:
Legyen G véges, m-edrend¶ Abel-csoport, valamint r és k olyan pozitív egészek, amelyekre 2 ≤ r < k teljesül. Ha m = p1 · p2 · · · tps , ahol a p1 ≤ p2 ≤ · · · ≤ ps számok prímek, akkor az alábbi érvényes: Az adott G csoport elemeinek minden olyan k -színezése esetén, ahol minden színt használunk, a G olyan elemeinek száma, amik el®állnak r darab különböz® szín¶ elem összegeként, (i) pontosan m, ha r = 2 és m < 2k − 1 (ii) legalább m − pm1 , ha r = 2 és 2k − 1 ≤ m m , ha 2 < r és k − r + 1 ≤ s (iii) legalább m − p1 ·p2 ···p k−r+1 (iv) pontosan m, ha 2 < r és k − r + 1 > s. A fenti korlátok élesek. Sejtés 2.
Nyilvánvaló módon az els® sejtés következménye a másodiknak. A harmadik fejezetben szorzatokra vonatkozó hasonló kérdéseket vizsgálunk. Azt becsüljük meg, hogy ha a pozitív egészeket M -ig valahogyan k-színezzük, akkor legalább hány olyan pozitív egész lesz, amik el®állnak r ugyanolyan szín¶ szám szorzataként. Ezek az eredmények szerepelnek [4]-ban. A harmadik fejezetben el®ször az alábbit igazoljuk:
Van olyan c pozitív abszolút konstans, hogy tetsz®leges r és k pozitív egészekre (ahol k nagyobb r-nél), valamint minden k-tól függ®en elég nagy M pozitív egészre igaz, hogy az {1, 2, · · · , M } halmaz minden k -színezésére teljesül a
Tétel 6.
X1 b∈B
b
>c·
2 1 · r−1 · log M, r k
5
egyenl®tlenség, ahol B jelöli azoknak a pozitív egészeknek a halmazát, amik felírhatók az {1, 2, · · · , M } halmaz r darab ugyanolyan szín¶ elemének szorzataként.
Az el®z®höz hasonló problémát is vizsgálunk néhány véges Abel-csoportban. Belátjuk az alábbi tételt: Minden k és r pozitív egészhez létezik olyan Tk,r pozitív egész, hogy minden Tk,r -nél nagyobb M pozitív egész esetén a következ® teljesül: tetsz®leges M -edrend¶ ciklikus G multiplikatív csoport elemeinek minden k -színezése mellett legalább Tétel 7.
M −3· (M, r)
M (M, r)
1−2−(k·(r−1)+1)
csoportbeli elem felírható a csoport r különböz®, azonos szín¶ elemének szorzataként (itt (M, r) az M és r számok legnagyobb közös osztóját jelöli).
A negyedik fejezetben a megfelel® rainbow-típusú problémát vizsgáljuk szorzatokra vonatkozóan. Egy aszimptotikusan pontos eredményt közlünk, ami [5]ben szerepel. Egészen pontosan, ha k rögzített pozitív egész és a pozitív egészeket n-ig k -színezzük úgy, hogy minden színt használunk, akkor R (n)-val jelölve azon számok minimális számát, amik el®állnak r darab különböz® szín¶ szám szorzataként belátjuk a következ®t: (r) k
(r)
Tétel 8.
limn→∞
Rk (n) n
=2−
1 2 2(r−1)(k−1)−(r−1)
.
Az utolsó fejezetben ismertetjük és megoldjuk Károlyi Gyula egy geometriai gráfelméleti sejtését, ami bizonyos részgráfok multiplicitására vonatkozik (lsd. [22]). Geometriai gráf alatt olyan gráfot értünk, ami le van rajzolva a síkba és minden csúcsa a sík egy pontja, míg minden éle két ilyen csúcs közt futó szakasz (feltesszük, hogy két csúcs közt futó szakaszon nincsen rajta egy harmadik csúcs). Konvex geometriai gráfról akkor beszélünk, ha a csúcsok konvex helyzetben vannak. Els®ként Harary és Prins vizsgálta absztrakt gráfok Ramsey-multiplicitását 6
(lsd. [19]). Hasonlóan kiterjeszthet® de níciójuk geometriai gráfokra. Tetsz®leges G gráf esetén a geometriai Ramsey-szám R (G) jelöli a legkisebb olyan pozitív egész r számot, amire az teljesül, hogy bármely legalább r csúcsú H teljes geometriai gráf éleinek tetsz®leges 2-színezése esetén van H -nak olyan részgráfja, aminek minden éle ugyanolyan színnel van színezve és nem tartalmaz keresztez® éleket. Ugyanígy de niálhatóak az R (G) számok, ahol konvex geometriai gráfokra szorítkozunk. Ismeretes, hogy a fenti számok pontosan akkor léteznek, ha a G gráf olyan síkgráf, ami lerajzolható oly módon a síkba, hogy csúcsainak mindegyike rajta van a végtelen lapon (lsd. [14]). RM (G) jelöli egy G gráf monokromatikus példányainak minimális számát egy teljes R (G)-csúcsú 2-színezett geometriai gráf részgráfjaként. Ugyanígy értelmezhet® az RM (G) szám konvex geometriai gráfok esetén. A 2n csúcsot tartalmazó, keresztez® élek nélküli teljes párosítást geometriai gráfok esetében M -nel fogjuk jelölni. Geometriai gráfokra ismeretes az alábbi (lsd. [24]): g
c
g
g
c
2n
Tétel 9.
Rg (M2n , M2n ) = 3n − 1
Károlyi vetette fel a kérdést, hogy mekkora lehet RM (M ) és RM (M ) értéke (lsd. [22]). Sejtése szerint ezek a csúcsok számának függvényében exponenciális nagyságrend¶ek. A sejtés teljesen logikusnak t¶nhet, hiszen absztrakt gráfok esetén a Ramsey- multiplicitás valóban nagy. Ezért is meglep® az állítás, amit a disszertációban bizonyítunk: g
Tétel 10.
2n
c
2n
RMg (M2n ) = RMc (M2n ) = 1.
References
[1] P. G. Agarwal and J. Pach, Combinatorial Geometry, Wiley, 1995. [2] J. Borbély, On the higher dimensional generalization of a problem of Roth, Integers, Volume 13, A64, 2013. 7
[3] J. Borbély, On the rainbow version of a problem of Roth, Journal of Combinatorics and Number Theory 6 , Volume 1, 67-75, 2014. [4] J. Borbély, Some Ramsey-type asymptotic results concerning products, submitted [5] J. Borbély, A rainbow-type asymptotic result concerning products, submitted [6] A. Cauchy, Recherches sur les nombres, Journal de l'École polytechnique, Volume 9, 99-116, 1813. [7] D. Conlon, Rainbow solutions of linear equations over Zp, Discrete Mathematics , Volume 306, Issue 17, 2056-2063, 2006. [8] J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassman derivatives and additive theory, Bulletin of the London Mathematical Society , Volume 26, 140-146, 1994. [9] P. Erd®s, Some unsolved problems, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, Volume A 6, 221-254, 1961. [10] P. Erd®s and A. Sárközy, On a conjecture of Roth and some related problems II, in: Number Theory, Proceedings of The First Conference of The Canadian Number Theory Association, edited by R. A. Mollin and Walter de Gruyter, Berlin-New York, 199-245, 1990. [11] P. Erd®s, A. Sárközy and Vera T. Sós, On a conjecture of Roth and some related problems I, Irregularities of partitions, Pap. Meet., Fert®d/Hung., in: Algorithms and Combinatorics, Volume 8, 47-59, 1989. [12] L. Gerencsér, A. Gyárfás, On Ramsey-type problems, Annales Universitatis Scientarium Budapestiensis Lorand Eötvös, Sectio Mathematica X, 167-170, 1967. [13] R. L. Graham, B. L. Rotschild, J. H. Spencer, Ramsey Theory, Wiley, 1980. 8
[14] P. Gritzmann, B. Mohar and J. Pach and R. Pollack, Embedding a planar triangulation with vertices at speci ed points, American Mathematical Monthly, Volume 98, 165-166, 1991. [15] D. S. Gunderson and V. Rödl, An alternate proof of Szemerédi's cube lemma using extremal hypergraphs, Diskrete Strukturen in der Mathematik, Preprintreihe, 1995. [16] D. S. Gunderson and V. Rödl, Extremal problems for a ne cubes of integers, Combinatorics, Probability and Computing , Volume 1, 65-79, 1998. [17] R. K. Guy, Unsolved Problems In Number Theory, Springer-Verlag, 1980. [18] Y. Hamidoune and Ø. Rødseth, An inverse theorem mod p , Acta Arithmetica , Volume 92, 251-262, 2000. [19] F. Harary and G. Prins, Generalized Ramsey theory for graphs IV, Ramsey multiplicities, Networks, Volume 4 (1974), 163-173, 1974. [20] D. Hilbert, Über die Irreduzibilität ganzer rationaler Funktionen mit ganzzähligen Koe zienten, Crelle's Journal, Volume 110, 104-129, 1892. [21] V. Jungi¢ , J. Ne²et°il and R. Radoi£i¢, Rainbow Ramsey Theory, Integers, Volume 5, 2005. [22] G. Károlyi, Ramsey-type problems for geometric graphs, in: Thirty Essays on Geometric Graph Theory, Springer, 371-382, 2013. [23] G. Károlyi, J. Pach and G. Tóth, Ramsey-type results for geometric graphs I, Discrete and Computational Geometry, Volume 18, 247-255, 1997. [24] G. Károlyi, J. Pach, G. Tóth and P. Valtr, Ramsey-type results for geometric graphs II, Discrete and Computational Geometry, Volume 20, 375-388, 1998. [25] J. B. Keller and C. Knessl, Partititon asymptotics from recursion equations, SIAM Journal on Applied Mathematics, Volume 50, No. 2, 323-338, 1990. 9 7
[26] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Mathematische Zeitschrift, Volume 58, 459-484, 1953. [27] B. M. Landman and A. Robertson, Ramsey Theory On The Integers, American Mathematical Society, 2004. [28] M. B. Nathanson, Additive Number Theory: The Classical Bases, Graduate Texts in Mathematics, 1996. [29] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Graduate Texts in Mathematics, Volume 164, 1996. [30] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Graduate Texts in Mathematics, Volume 165, 1996. [31] J. Solymosi, Bounding multiplicative energy by the sumset, Advances in Mathematics, Volume 222, Issue 2, 2009, 402-408. 1990. [32] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27, 199-245, 1975. [33] T. Tao and V. H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, Volume 105, 2006. [34] A. G. Vosper, The critical pairs of subsets of a group of prime order, Journal of the London Mathematical Society, Volume 31, 200-205, 1956. [35] B. S. Webb (editor), Surveys in Combinatorics, London Mathematical Society Lecture Note Series, Volume 327, 2005.
10
