Timeline for Distinguishing points by sets of given size
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Aug 3, 2018 at 11:59 | comment | added | Brendan McKay | I think these are called "separating systems". Using that as a search key might dig up something. If I remember correctly, the exact value is not known in general. | |
| Aug 2, 2018 at 6:18 | answer | added | Seva | timeline score: 2 | |
| Jul 24, 2018 at 16:53 | history | edited | LeechLattice | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 24, 2018 at 16:51 | comment | added | LeechLattice | @GerhardPaseman n is just the size of B. | |
| Jul 24, 2018 at 16:46 | comment | added | Gerhard Paseman | OK. Suppose B contains all k subsets that contain a given two element set, and one other k element set. What n are you going to choose? Gerhard "Is Looking For More Clarity" Paseman, 2018.07.24. | |
| Jul 24, 2018 at 16:31 | history | undeleted | LeechLattice | ||
| Jul 24, 2018 at 16:31 | history | deleted | LeechLattice | via Vote | |
| Jul 24, 2018 at 16:04 | comment | added | LeechLattice | @IvanIzmestiev There is a better lower bound by information theory: $n>-\text{log}x÷(f(\frac{k}{x})+f(\frac{x-k}{x}))$, where $f(x)=x\text{log}x$. | |
| Jul 24, 2018 at 16:01 | history | edited | LeechLattice | CC BY-SA 4.0 |
added 243 characters in body; edited body
|
| Jul 24, 2018 at 15:50 | comment | added | LeechLattice | @GerhardPaseman Clarified. | |
| Jul 24, 2018 at 15:38 | comment | added | Gerhard Paseman | It is not clear what is meant by the problem. If the question asks what is the smallest j such that the intersection of any j sets from B has size at most one, there is the obvious 1+ ( x-2 choose k-2). Gerhard "Is That What You're Asking?" Paseman, 2018.07.24. | |
| Jul 24, 2018 at 15:37 | comment | added | Ivan Izmestiev | Well, an obvious lower bound is $\log_2 x$, and it is attained for $k=x/2$ and $x$ a power of $2$: the $i$-th set consists of all numbers whose $i$-th binary digit is $1$. For $k$ different from $x/2$ this looks more complicated. | |
| Jul 24, 2018 at 15:29 | history | asked | LeechLattice | CC BY-SA 4.0 |