Timeline for Minimally intersecting subsets of fixed size
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Nov 20, 2015 at 15:41 | answer | added | NP2P | timeline score: 0 | |
| Jan 18, 2015 at 14:01 | history | edited | Jim | CC BY-SA 3.0 |
added 4 characters in body
|
| Jan 16, 2015 at 21:13 | comment | added | Dima Pasechnik | @Bill - I added a possible construction to my answer. | |
| Jan 16, 2015 at 18:24 | comment | added | Gerhard Paseman | Consider variants on Hadamard matrix generation. Choose integers [1, n/2] for the first set, [1, n/4] union [n/2 + 1, 3n/4] for the second, and for the remainder, sample half the elements from each of the quarter intervals. This guarantees small intersections with the first two sets and with high probability small intersections among the latter sets. Gerhard "Probabilistic Hadamard Matrices? Hmmm, Interesting..." Paseman, 2015.01.16 | |
| Jan 16, 2015 at 18:18 | history | edited | Jim | CC BY-SA 3.0 |
added tag, slightly changed original formulation.
|
| Jan 16, 2015 at 18:06 | comment | added | Jim | @DimaPasechnik That is exactly what I want to contrast it with. I would be happy with a strong heuristic approach. | |
| Jan 15, 2015 at 20:55 | comment | added | Dima Pasechnik | If your $k$ is so small you may just choose your subsets at random. Say, for $m=n/2$ the intersection of two of them will be of size about $n/4$. | |
| Jan 15, 2015 at 18:02 | comment | added | Jim | @DimaPasechnik The case that I am concerned with has for example $n = 100, 1000$ or $10^6$, $m = n/2$ or $n/3$ and $k=5, 10$ or $20$ (to give an impression). So I want to avoid enumerating/searching over all $m$-subsets as there are simply too many ($n \choose m$). Intuitively, I want a sequence of subsets that are "maximally different" vis-a-vis the subsets already in the sequence. | |
| Jan 15, 2015 at 16:08 | comment | added | Dima Pasechnik | in the form given in your Edit, the question makes little sense; indeed, just enumerate all the $m$-subsets of the $n$-set. This is easy to do efficiently. (However, this way the guaranteed minimal distance is 2, which is not what most people want). | |
| Jan 15, 2015 at 13:49 | history | edited | Jim | CC BY-SA 3.0 |
added 148 characters in body
|
| Jan 15, 2015 at 13:32 | history | edited | Jim | CC BY-SA 3.0 |
added 442 characters in body
|
| Jan 14, 2015 at 20:06 | history | edited | Dima Pasechnik |
edited tags
|
|
| Jan 14, 2015 at 20:06 | answer | added | Dima Pasechnik | timeline score: 5 | |
| Jan 14, 2015 at 19:48 | history | edited | Jim |
edited tags
|
|
| Jan 14, 2015 at 16:24 | history | edited | Jim | CC BY-SA 3.0 |
deleted 8 characters in body
|
| Jan 14, 2015 at 14:55 | review | First posts | |||
| Jan 14, 2015 at 15:15 | |||||
| Jan 14, 2015 at 14:46 | history | asked | Jim | CC BY-SA 3.0 |