8
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ 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 $\endgroup$ Jul 12, 2011 at 19:12
  • $\begingroup$ @Gerhard: You are correct. $\endgroup$
    – user6976
    Jul 12, 2011 at 19:32
  • $\begingroup$ 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 $\endgroup$ Jul 12, 2011 at 20:18
  • $\begingroup$ @Gerhard: These were my questions, I refer to them here. $\endgroup$
    – user6976
    Jul 12, 2011 at 20:54
  • $\begingroup$ 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 $\endgroup$ Jul 12, 2011 at 21:15

2 Answers 2

3
$\begingroup$

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}$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ By considering the colouring of the singletons and applying Pigeonhole we get $l \geq k/1000$. $\endgroup$
    – Tony Huynh
    Jul 12, 2011 at 19:33
  • $\begingroup$ @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? $\endgroup$
    – user6976
    Jul 12, 2011 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.