Timeline for Maximal number of subsets in $\{1,\dots,n\}$ such that neither is contained in a union of two others
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 14, 2015 at 12:51 | vote | accept | Fedor Petrov | ||
| Aug 14, 2015 at 12:45 | answer | added | Boris Bukh | timeline score: 6 | |
| Aug 14, 2015 at 11:26 | comment | added | Wolfgang | Oh I see now, e.g. $f(9)\ge12$, attained by taking the 9 sets 123,234,... (cyclically) plus the 3 sets 147,258,369. Interesting! | |
| Aug 14, 2015 at 10:18 | comment | added | Fedor Petrov | Choose, say, subsets $A_1,\dots,A_M$ of size $n/4$ at random. The probability of any event $A_i\subset A_j\cup A_k$ is exponentially small in $n$, thus for small $c_1$ close to 1 with positive probability no event happens. This may be improved by optimization in size and by using Lovász Local Lemma. | |
| Aug 14, 2015 at 10:13 | history | edited | Fedor Petrov | CC BY-SA 3.0 |
edited body
|
| Aug 14, 2015 at 10:00 | comment | added | Wolfgang | How do you come up with your lower bound $c_1^n$? I cannot seem to find anything better than linear, e.g. $A_i=\{i\}$. | |
| Aug 14, 2015 at 9:40 | comment | added | Wolfgang | You use $k$ twice for different things, maximal $N$ would be better. :) | |
| Aug 14, 2015 at 9:02 | history | edited | Fedor Petrov |
edited tags
|
|
| Aug 14, 2015 at 8:52 | history | asked | Fedor Petrov | CC BY-SA 3.0 |