Timeline for Large Intersecting Subsets of a Set
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2012 at 9:07 | answer | added | Peter | timeline score: 3 | |
| Oct 24, 2012 at 17:50 | answer | added | Kevin P. Costello | timeline score: 3 | |
| Oct 24, 2012 at 11:25 | answer | added | Padraig Ó Catháin | timeline score: 3 | |
| Oct 24, 2012 at 5:16 | history | edited | Andrés E. Caicedo |
edited tags
|
|
| Oct 24, 2012 at 5:04 | answer | added | Gerhard Paseman | timeline score: 4 | |
| Oct 24, 2012 at 4:40 | comment | added | Gerhard Paseman | I bet Will Orrick could handle the case of n odd. Gerhard "Maybe Somebody Could Ask Him" Paseman, 2012.10.23 | |
| Oct 24, 2012 at 4:36 | comment | added | Gerhard Paseman | Also, something that might help for many even n is real Hadamard matrices of order 2n. When normalized so that the first row is all ones, the remaining 2n-1 rows have the property that each pair of rows share exactly n/2 ones. Gerhard "Ask Me About System Design" Paseman, 2012.10.23 | |
| Oct 24, 2012 at 0:40 | comment | added | fedja | Here is an explicit construction with $Cn$ elements. Take any prime $p\approx 10n$. Let $n$ be even and $S_j=\{jk:k=1,\dots,n}$ (modulo $p$). Then all intersections are pretty much the same and we just need to prove that $|S_j\cap S_1|\le n/2$ for all $j=2,\dots,p-1$. However, this is obvious for $|j|\le 5, j\ne 1$ and if $6\le|j|\le \frac{p-1}2$, choose the least $u$ such that $u|j|>n$ and notice that if $u=1$, then $jk\in S_1$ implies $j(k+1)\notin S_1$ but if $2\le u\le n/5$, then $jk\in S_1$ implies $j(k+u), j(k+2u)\notin S_1$. | |
| Oct 23, 2012 at 22:05 | comment | added | Smart_Mathematician | Thanks Johan, I think that works! Also, condition (3) is correct. I want the the intersection to be small. | |
| Oct 23, 2012 at 22:00 | comment | added | Johan Wästlund | With $(2+\epsilon)\cdot n$ elements, you can pick the subsets randomly. It will be exponentially unlikely that two subsets intersect in more than $n/2$ elements, and there are only quadratically many pairs of sets, so for large $n$, the conditions will be met with positive probability. | |
| Oct 23, 2012 at 21:50 | comment | added | Gerhard Paseman | O(n^3/2) comes quickly by considering the case n=2. I am confident that O(nlogn) is asymptotically acheivable for n sufficiently large. Gerhard "Ask Me About System Design" Paseman, 2012.10.23 | |
| Oct 23, 2012 at 21:33 | comment | added | Tony Huynh | I took the liberty of editing since the mistake seems like an obvious typo. @Smart_Mathematician, feel free to re-edit if you had something else in mind. | |
| Oct 23, 2012 at 21:31 | history | edited | Tony Huynh | CC BY-SA 3.0 |
changed inequality and added combinatorics tag
|
| Oct 23, 2012 at 21:11 | comment | added | Barry Cipra | I think you got the inequality in (3) backwards. As stated, you can let all the $S_i$'s be the same, and thus get by with a set $U$ of exactly $n$ elements. | |
| Oct 23, 2012 at 21:00 | history | asked | Smart_Mathematician | CC BY-SA 3.0 |