Cheap and Secure Web Hosting Provider : See Now

Paths between tuples, MSV, decision trees

, , No Comments
Problem Detail: 

I'm reading about Multiset Size Verification Problem and in the following paper - - I got stuck just on the first lemma. However, since my concrete problem is rather specific, I'll describe it as self-contained, so that no background in terms of what MSV really is will be needed (but I encourage you to check it :)).

Fix natural $k, n$ such that $k \le n$. Let $$ Y = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n : |\{ z_1, z_2, \ldots, z_n \}| = k \} $$ Next, let $$ T = \{ (z_1, z_2, \ldots, z_n) \in \mathbb{R}^n : \{z_1, z_2, \ldots, z_k \} = \{1, 2, \ldots, k \} \ \text{and} \ z_i \in \{1, 2, \ldots, k \} \ for \ i \in \{ k+1, \ldots, n \} \} $$ In the paper that I linked to, they claim that for any distinct $a, b \in T$, on any continuous path from $a$ to $b$ we must encounter a point $p$ that is outside $Y$, i.e. $p \in \mathbb{R}^n - Y$. Apparently, it is not hard to see that, but I have a big difficulty proving it formally.

I wasn't sure whether to ask this question on Math community, or here, since the problem itself is purely mathematical. It's closely related to CS, though.

Asked By : socumbersome
Answered By : Yuval Filmus

Consider any path from $a \in T$ to $b \in T$ inside $Y$. Let $t$ be the first time in which the first $k$ coordinates are not distinct. Prior to time $t$, for each $1 \leq i \leq k$, all coordinates in $j \in \{k+1,\ldots,n\}$ such that $a_j = a_i$ must keep satisfying this relation along the path, since otherwise there will be more than $k$ distinct values. Therefore at the point $t$, there will be fewer than $k$ distinct values. We conclude that the first $k$ coordinates always remain distinct, and that they determine the rest of the vector. In particular, the values in the first $k$ coordinates can't cross each other: if $a_i < b_i$ and $a_j > b_j$ then the intermediate value theorem shows that at some point $x$ along the path, $x_i = x_j$. We conclude that $a_1,\ldots,a_k = b_1,\ldots,b_k$. Since the first $k$ coordinates determine the rest, in fact $a = b$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback