Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is related to this one but feels more Ramsey-type, so perhaps it is easier. Let $S$ be a finite set, $|S|=k$. Suppose we color all subsets of $S$ in $1000$ colors. What is the maximal (in terms of $k$) guaranteed length $l=l(k)$ of a monochromatic sequence of pairwise different subsets $A_1,A_2,..., A_l$ such that $|A_i\setminus A_{i+1}|+|A_{i+1}\setminus A_i|\le 2$ for every $i$? Clearly if $A$ is a subset of $S$ such that all 2-element subsets of $A$ are monochromatic, then $l(n)\ge |A|-1$ (there is a sequence of 2-element subsets of $A$ which satisfies the above property). So $l(k)$ is at least as big as the corresponding number from the Ramsey theory. Is it much bigger? The number 1000 is of course "any fixed number".

Update 1 Fedor and Tony showed below that $l(k)\ge k/1000$. Thus only the first question remains: What is $l(k)$? Is it exponential in $k$, for example?

Update 2 Although the question I asked makes sense (see Update 1), I realized that it is not the question I meant to ask. Here is the correct question. Same assumptions: $|S|=k$, 1000 colors. We consider monochromatic sequences of pairwise different subsets ${\mathcal A}=A_1,A_2,...,A_l$, where $|A_i\setminus A_{i+1}|+|A_{i+1}\setminus A_i|\le 2$. For each of these sequences we compute $\chi({\mathcal A})=|A_1\setminus A_l|+|A_l\setminus A_1|$. Now the question: what is the maximal guaranteed $\chi({\mathcal A})$ in terms of $k$, call it $\chi(k)$? By Ramsey, this number grows with $k$. Indeed if we color just $s$-element subsets, we will be able (if $k\gg s$) to find a subset of size $2s$ where all subsets of size $s$ are colored with the same color; then we can find a monochromatic sequence of subsets of size $s$ with the above property and $\chi=2s$ because the first and the last subsets in that sequence are disjoint. The question is what is the growth rate of $\chi(k)$. The question is motivated by Justin Moore's answer here.

share|improve this question
    
A natural assumption is that the A_i are all required to be distinct. Another is if A_i = A_j, then either i=j or A_i+1 is not equal to A_j+1. Are you interested in no cycles or in a long Eulerian path? Gerhard "Email Me About System Design" Paseman, 2011.07.12 –  Gerhard Paseman Jul 12 '11 at 19:12
    
@Gerhard: You are correct. –  Mark Sapir Jul 12 '11 at 19:32
    
I'll take that as meaning that both versions are of interest. I am struggling to remember a MathOverflow question which used the term "2-connected" to mean roughly that points were within distance 2 of one another. Although the enumeration problem discussed was different, you might still find it of interest in tackling this problem. When I find it, I'll post a link to it. Gerhard "Email Me About System Design" Paseman, 2011.07.12 –  Gerhard Paseman Jul 12 '11 at 20:18
    
@Gerhard: These were my questions, I refer to them here. –  Mark Sapir Jul 12 '11 at 20:54
    
My memory says this question that I am trying to remember was not one of yours, It was trying to compute something like the expected size of a 2 neighborhood of a graph, and had a reference whose name I am also trying to remember. Unless this triggers someone else's memory, I'n afraid we will have to let me continue the struggle. Gerhard "Connected Associative Memories Work Better" Paseman, 2011.07.12 –  Gerhard Paseman Jul 12 '11 at 21:15
show 8 more comments

2 Answers

Here is a proof of a very weak upper bound for $l(k)$. Consider the colouring of $2^S$ where each set is coloured by its size (mod 1000). A good monochomatic sequence must consist of sets of the same size. Thus we obtain $l(k) \leq \binom{k}{k/2}$.

However, we can be a bit smarter. Instead of colouring all $i$-subsets of $S$ with the same colour, we can use 333 colours and still guarantee that a good monochromatic sequence must use sets of the same size. Thus, we are lead to the problem of 333-colouring $\binom{S}{i}$ to minimize the length of a good monochromatic sequence inside $\binom{S}{i}$.

share|improve this answer
add comment

It is much bigger for sure, even if we restrict two subsets of cardinality 2 (call them edges). You need monochromatic path of length $\ell$. Take the color with at least $k(k-1)/2000$ edges of this color, consider only them. Consider the maximal path in our graph. It has length at most $l-1$. Hence it endpoint (both of them) has degree at most $l-1$. Remove it and repeat (or use induction). We get that our graph has at most $(l-1)k$ edges. So, $k(k-1)/2000\leq (l-1)k$, $l\geq (k-1)/2000+1$.

share|improve this answer
    
By considering the colouring of the singletons and applying Pigeonhole we get $l \geq k/1000$. –  Tony Huynh Jul 12 '11 at 19:33
    
@Fedor and Tony: this answers the second question, $l(k)\ge k/1000$. But what is the growth of $l(k)$. Is it exponential or polynomial or something in between? –  Mark Sapir Jul 12 '11 at 19:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.