Timeline for Can a partition free family in $2^{[n]}$ always be enlarged to one of size $2^{n-1}$?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2021 at 5:28 | comment | added | Aaron Meyerowitz | Define the distance between two maximal intersecting families $d(F,G)$ to be the number of complementary pairs on which they disagree. If there are any such, then there is an $A \in F$ which is minimal in $F$ and not in $G.$ The complement $B$ of $A$ intersects everything else in $F$ save $A$ so the switch makes $F$ into some other maximal intersecting family $F’$ with $d(F’,G)=d(F,G)-1$. If $d(F’,G)>0$ then there is a switch giving $d(F’’, G)=d(F’,G)-1$ | |
| Dec 22, 2021 at 5:05 | comment | added | Aaron Meyerowitz | @AyamGorengPedes From the family we started with, we can’t add 24 since , while it does intersect 12 of the 16 members, it is disjoint from each of the members 1,13,15,135. At the step you are considering we got rid of 1,13,15 in favor of 2345,345,234 . (We also swapped 12 for 345 and 14 for 235 and 134 for 25…but 24 intersects both members of those pairs) So now 24 is only disjoint from 135 and we can switch them. | |
| Dec 22, 2021 at 0:44 | comment | added | AyamGorengPedes | And after we swap 134 with 25, how do we swap 135? I couldn't find a workaround | |
| Dec 21, 2021 at 7:07 | comment | added | Aaron Meyerowitz | @AyamGorengPedes Suppose $n=5$ and write 12 for $\{1,2\}$. First replace 1 with 2345 then 13,14,15 with 245,235,234 (one at at time) then 134,135,145 with 25,24,23 finally 1345 with 2. The start and end families had an overlap of $8$ out of $16$. Each move increases the overlap with the end by $1$. | |
| Dec 19, 2021 at 21:30 | comment | added | AyamGorengPedes | Uhmm, that is not my confusion, but rather "any maximal intersecting family can be changed into any other". For example given the base set [1,...,n], and we take all of the sets that contain 1, how can we turn this into the family where all of it's sets contain 2? How to do it in general, is there an "algorithm" for it? | |
| Dec 19, 2021 at 21:15 | comment | added | Aaron Meyerowitz | If you have a minimal member A, every other member B has some element in B but not in A. So what f we discard A and replace it with its complement, you have a new intersecting family of size $2^{n-1}$ | |
| Dec 19, 2021 at 15:48 | comment | added | AyamGorengPedes | the last sentence in the paragraph is interesting, can you point me to a lecture/something that explains how to do it? I know this post was 7 years ago, so maybe someone else can also point me towards the right direction.. | |
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 13, 2014 at 6:41 | vote | accept | Aaron Meyerowitz | ||
| Jan 12, 2014 at 10:13 | answer | added | Jeremy Rickard | timeline score: 14 | |
| Jan 12, 2014 at 9:04 | history | asked | Aaron Meyerowitz | CC BY-SA 3.0 |