Schur numbers involving rainbow colorings

angleški

2020

letnik 18, številka 2

anti-Ramseyeva števila   Gallaieva barvanja   mavrični trikotniki   Schurova števila

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

V članku vpeljemo dve posplošitvi Schurovih števil, povezani z mavričnimi barvanji. Spodbujeni z dobro znanimi posplošitvami Ramseyevih števil, najprej definiramo mavrično Schurovo število ?$RS(n)$? kot najmanjše število barv, potrebnih za to, da vsako barvanje množice ?$\{1, 2, \dots , n\}$?, v katerem so uporabljene vse barve, ki so na voljo, vsebuje mavrično rešitev enačbe ?$a+b=c$?. Dokažemo, da velja ?$$RS(n)=\lfloor \log_2(n)\rfloor + 2, \quad \text{for all} \; n \ge 3.$$? Kot drugo, obravnavamo Gallai-Schurovo število ?$GS(n)$?, definirano kot najmanjše naravno število, pri katerem velja, da vsako ?$n$?-barvanje množice ?$\{1, 2,\dots, GS(n)\}$?, ki ne premore mavričnih rešitev enačbe ?$a+b=c$?, neizogibno vsebuje enobarvno rešitev te enačbe. To število povežemo z ?$n$?-barvnim Gallai-Ramseyevim številom za trikotnike in dokažemo, da za vse ?$n \ge 3$? velja ?$$ GS(n) = \begin{cases} 5^k & \text{if} \; n=2k \\ 2 \cdot 5^k & \text{if} \; n=2k+1. \\ \end{cases}$$?

28.04.2021