Timeline for How many elements with a hamming distance of 3 or less?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jun 8, 2011 at 6:16 | vote | accept | chous | ||
| Jun 8, 2011 at 6:15 | vote | accept | chous | ||
| S Jun 8, 2011 at 6:16 | |||||
| Jun 7, 2011 at 22:50 | answer | added | Douglas Zare | timeline score: 5 | |
| Jun 7, 2011 at 19:19 | history | edited | Douglas Zare | CC BY-SA 3.0 |
adjusted rewrite statement
|
| Jun 7, 2011 at 12:12 | vote | accept | chous | ||
| Jun 8, 2011 at 6:15 | |||||
| Jun 7, 2011 at 8:29 | comment | added | Douglas Zare | You are asking for a wheel with parameters $(50,5,2)$. A covering design is different, which is unfortunate because there is a nice searchable database of covering designs, the La Jolla Covering Repository which Gerhard Paseman mentions. Most of the web hits when you search for lottery wheels are trying to sell junk to lottery players. | |
| Jun 7, 2011 at 4:21 | answer | added | Aaron Meyerowitz | timeline score: 7 | |
| Jun 7, 2011 at 1:46 | comment | added | Gerhard Paseman | Oops. In the above, please read "symmetric difference" for "symmetric distance" . Gerhard "This Goes Out To Emily" Paseman, 2011.06.06 | |
| Jun 7, 2011 at 1:44 | comment | added | Gerhard Paseman | Hamming distance works better on sequences than on sets. Although we could phrase your distance in terms of the symmetric distance of two sets, I think it easier to say "For any 5-set t, I want there to be at least one of my 5-sets s in S such that s intersect t has at least two elements. Further, I want S chosen so that S has as few 5-sets in it as can be managed." The La Jolla Covering Repository answers this sort of question (if I read it right). Do a web search and check it out if you agree. Gerhard "Donates Regularly To Mega Millions" Paseman, 2011.06.06 | |
| Jun 7, 2011 at 0:54 | comment | added | Robert Israel | @chous: you have not really defined $S_3$ uniquely. I think what you're really saying is that you want some set $T$ such that for every $s \in S$ there is some $t \in T$ with $d_h(s,t) \le 3$. There are lots of such sets, for example $S$ itself. But perhaps what you want is one with minimum cardinality: you're talking about a "minimal cover problem" in a graph $G$ consisting of the elements of $S$, with edges corresponding to pairs with Hamming distance $\le 3$. | |
| Jun 6, 2011 at 23:34 | history | edited | Gerry Myerson |
removed finite-groups tag
|
|
| Jun 6, 2011 at 20:11 | comment | added | chous | @alpoge - How can I particularize the concept of 'distance' in your approach of using the domination number? If I understood it correctly, using the domination number to define S3 implies, for each possible tuple, S3 would contain a tuple in which all numbers can differ, but must be directly reachable, i.e. each number with a maximum distance of 1. | |
| Jun 6, 2011 at 18:56 | comment | added | chous | @Ashok - I don't think your proposal of $S_3$ such as all members of $S_3$ have a distance $\le$ 3 satisfies my goal. I need $S_3$ as the subset of $S$ that satisfies: - Given any $s$ in $S$, there exists at least one $s_3$ of $S_3$ such as $d_h(s, s_3) \le 3$ I'm sorry for my lack of accuracy. The reason behind the question is to find the set $S_3$ to be sure that, for any possible tuple of $S$, I can find an element in $S_3$ subset matching 2 or more numbers of the given tuple. | |
| Jun 6, 2011 at 18:53 | comment | added | Gerhard Paseman | This sounds like lottery wheels or lottery designs. I suggest a web search. Gerhard "Ask Me About System Design" Paseman, 2011.06.06 | |
| Jun 6, 2011 at 16:52 | comment | added | alpoge | (Whoops! $K_{50}$, not $K_50$.) | |
| Jun 6, 2011 at 16:52 | comment | added | alpoge | A quick comment: this is probably not useful, but I think you want the domination number $\gamma(G)$ of the graph $G = (K_50^{\times 5})^3$, where $\times$ denotes the Cartesian product (i.e., the cube of the fifth Cartesian power of $K_50$). I don't really know much past this, but hopefully there are ways of relating $\gamma(G)$ and $\gamma(G^n)$ for sufficiently 'nice' graphs $G$ other than $\gamma(G^n)\leq \gamma(G)$ (and probably $\gamma(K_50^{\times 5})$ is very easy to describe--I haven't thought much past the easy bound of (50)^4...). | |
| Jun 6, 2011 at 16:51 | comment | added | Ashok | Your description of $S_3$ doesn't make sense. I think you are interested in the cardinality of the set $S_3$ of tuples as described in $S$ such that any two members of $S_3$ have Hamming distance(in your meaning)$\le 3$. Am I right? If this is the case then the problem is same as finding the number of selections of $5$ objects from $50$ objects such that no two of the selections share more than $3$ objects in common | |
| Jun 6, 2011 at 14:08 | comment | added | chous | Yeah, sorry. $S$ is a 5-element tuple consisting of numbers between 1 and 50. They are ordered and cannot contain duplicates. $d_h$ is the number of differences between two given tuples: 5 - number of matching numbers. For example, to convert (1,2,3,4,5) into (1,3,5,6,7) I'd have to replace 2 with 6 and 4 with 7. So the distance is 2. | |
| Jun 6, 2011 at 14:04 | history | edited | chous | CC BY-SA 3.0 |
Redefining $S_3$
|
| Jun 6, 2011 at 13:58 | comment | added | James Cranch | Could you explain your definition of $d_h$ a bit more? (By the way, that formula defining $S$ is horrendous! Words really are better for these things.) | |
| Jun 6, 2011 at 13:50 | history | asked | chous | CC BY-SA 3.0 |