On some three-color Ramsey numbers for paths

设为首页

收藏本站

网站地图 | English | 公务邮箱

远程访问

NSTL服务站

On some three-color Ramsey numbers for paths

详细信息查看全文

作者：Janusz Dybizbański^a ; ^{jdybiz@inf.ug.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Tomasz Dzido^a ; ^{tdz@inf.ug.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Stanisław Radziszowski^b ; ^{spr@cs.rit.edu" class="auth_mail" title="E-mail the corresponding author}
关键词：Three-color Ramsey number ; Path graph
刊名：Discrete Applied Mathematics
出版年：2016
出版时间：11 May 2016
年：2016
卷：204
期：Complete
页码：133-141
全文大小：405 K

文摘

For graphs n id="mmlsi88" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si88.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=0cd4f66aa328ada87d3f6e518b8b089b" title="Click to view the MathML source">G₁,G₂,G₃n>n class="mathContainer hidden">n class="mathCode">

G_{n>1 n>}, G_{n>2 n>}, G_{n>3 n>}

n>n>n>, the three-color Ramsey number n id="mmlsi89" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si89.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=f0795d8b998646ad2f30b882c1aba637" title="Click to view the MathML source">R(G₁,G₂,G₃)n>n class="mathContainer hidden">n class="mathCode">

R (G_{n>1 n>}, G_{n>2 n>}, G_{n>3 n>})

n>n>n> is the smallest integer n id="mmlsi90" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si90.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=dd570645ebbfb773d29f40827b5a4a1a" title="Click to view the MathML source">nn>n class="mathContainer hidden">n class="mathCode">

n

n>n>n> such that if we arbitrarily color the edges of the complete graph of order n id="mmlsi90" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si90.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=dd570645ebbfb773d29f40827b5a4a1a" title="Click to view the MathML source">nn>n class="mathContainer hidden">n class="mathCode">

n

n>n>n> with 3 colors, then it contains a monochromatic copy of n id="mmlsi92" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si92.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=3c2acc4a1e7968ffefa3e07bde2b5345" title="Click to view the MathML source">G_in>n class="mathContainer hidden">n class="mathCode">

G_{i}

n>n>n> in color n id="mmlsi93" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si93.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=2d1bb3a51e67ce3ea4184dbe292401db" title="Click to view the MathML source">in>n class="mathContainer hidden">n class="mathCode">

i

n>n>n>, for some n id="mmlsi94" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si94.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=03cfd5f99f17fb18d61014c096f61834" title="Click to view the MathML source">1≤i≤3n>n class="mathContainer hidden">n class="mathCode">

n>1 n> &le; i &le; n>3 n>

n>n>n>.

First, we prove that the conjectured equality n id="mmlsi95" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si95.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=a018f833fa772413ca8bcbb169c2f9d0" title="Click to view the MathML source">R(C_2n,C_2n,C_2n)=4nn>n class="mathContainer hidden">n class="mathCode"> $R (C_{n>2 n> n}, C_{n>2 n> n}, C_{n>2 n> n}) = n>4 n> n$ n>n>n>, if true, implies that n id="mmlsi96" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si96.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=81d4d0a2e382d6be7f14b7e7ad145686" title="Click to view the MathML source">R(P_2n+1,P_2n+1,P_2n+1)=4n+1n>n class="mathContainer hidden">n class="mathCode"> $R (P_{n>2 n> n + n>1 n>}, P_{n>2 n> n + n>1 n>}, P_{n>2 n> n + n>1 n>}) = n>4 n> n + n>1 n>$ n>n>n> for all n id="mmlsi97" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si97.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=38dd90d7f716299182177e5ab43545e6" title="Click to view the MathML source">n≥3n>n class="mathContainer hidden">n class="mathCode"> $n \geq n>3 n>$ n>n>n>. We also obtain two new exact values n id="mmlsi98" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si98.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=bef50d99914bc119417487940b8f8715" title="Click to view the MathML source">R(P₈,P₈,P₈)=14n>n class="mathContainer hidden">n class="mathCode"> $R (P_{n>8 n>}, P_{n>8 n>}, P_{n>8 n>}) = n>14 n>$ n>n>n> and n id="mmlsi99" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si99.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=1b89362bfd9b4b6fbce9a0ec920643ee" title="Click to view the MathML source">R(P₉,P₉,P₉)=17n>n class="mathContainer hidden">n class="mathCode"> $R (P_{n>9 n>}, P_{n>9 n>}, P_{n>9 n>}) = n>17 n>$ n>n>n>, furthermore we do so without help of computer algorithms. Our results agree with a formula n id="mmlsi100" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si100.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=cb889efead1c2c40e9f4d833b0591f89" title="Click to view the MathML source">R(P_n,P_n,P_n)=2n−2+(nmod2)n>n class="mathContainer hidden">n class="mathCode"> $R (P_{n}, P_{n}, P_{n}) = n>2 n> n − n>2 n> + (n mod n>2 n>)$ n>n>n> which was proved for sufficiently large n id="mmlsi90" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si90.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=dd570645ebbfb773d29f40827b5a4a1a" title="Click to view the MathML source">nn>n class="mathContainer hidden">n class="mathCode"> $n$ n>n>n> by Gyárfás, Ruszinkó, Sárközy, and Szemerédi (2007). This provides more evidence for the conjecture that the latter holds for all n id="mmlsi102" class="mathmlsrc">n class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005417&_mathId=si102.gif&_user=111111111&_pii=S0166218X15005417&_rdoc=1&_issn=0166218X&md5=eddaed538cebf59f4a4300f3ce99e4f5" title="Click to view the MathML source">n≥1n>n class="mathContainer hidden">n class="mathCode"> $n \geq n>1 n>$ n>n>n>.

地址：北京市海淀区学院路29号邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700