Monochromatic Vs multicolored paths |
| |
Authors: | Hanno Lefmann Vojtěch Rödl Robin Thomas |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, Emory University, 30322 Atlanta, GA, USA;(2) School of Mathematics, Georgia Institute of Technology, 30332 Atlanta, GA, USA;(3) Department of Mathematics and Computer Science, Emory University, 30322 Atlanta, GA, USA;(4) School of Mathematics, Georgia Institute of Technology, 30332 Atlanta, GA, USA |
| |
Abstract: | Letl andk be positive integers, and letX={0,1,...,l k?1}. Is it true that for every coloring δ:X×X→{0,1,...} there either exist elementsx 0<x 1<...<x l ofX with δ(x 0,x 1)=δ(x 1,x 2)=...=δ(x l?1,x l), or else there exist elementsy 0<y 1<...<y k ofX with δ(y i?1,y i) ∈ δ(y j?1,y j) for all 1<-i<j≤k? We prove here that this is the case if eitherl≤2, ork≤4, orl≥(3k)2k . The general question remains open. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|