Timeline for Number of couples of sets with empty intersection in a separating union-closed family of sets
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2022 at 13:15 | comment | added | Peter Taylor |
@BillyJoe, the brute force search terminated without finding anything better than (compressed format) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 31, 63].
|
|
| Oct 16, 2022 at 8:43 | history | bounty ended | Fabius Wiesner | ||
| Oct 13, 2022 at 12:54 | vote | accept | Fabius Wiesner | ||
| Oct 8, 2022 at 23:55 | comment | added | Peter Taylor | I'm pretty sure that just requires adding $[k-1]\cup\{k+1\}$ and $[k-1]\cup\{k+2\}$. | |
| Oct 8, 2022 at 15:34 | comment | added | Fabius Wiesner | I have just added the requirement that the Hasse diagram graph cannot have articulation vertices. | |
| Oct 6, 2022 at 16:12 | comment | added | Peter Taylor | I've killed it and added more progress logging... | |
| Oct 6, 2022 at 10:40 | comment | added | Fabius Wiesner | Did the $n=6$ brute force search terminate? | |
| Oct 5, 2022 at 12:22 | comment | added | Fabius Wiesner | Maybe we exclude families such that there exists a vertex ($\not = U(\mathcal{F})$) in their Hasse diagram such that removing that vertex makes the graph disconnected. In our case it is $[k]$. | |
| Oct 5, 2022 at 12:09 | comment | added | Peter Taylor | The entry to the wider cap would still be by two edges, so maybe you could say that no vertex in the Hasse diagram may have in-degree 1. But then the same idea can be taken one further to add three new elements in pairs. | |
| Oct 5, 2022 at 11:58 | comment | added | Peter Taylor | I think that can be worked around by introducing two new elements and then building a "cap" of width three: ${2^{[k]}} \cup {\{[m] : k+2 \le m \le n \}} \cup {\{[m] \setminus \{k+1\} : k+2 \le m \le n \}} \cup {\{[m] \setminus \{k+2\} : k+2 \le m \le n \}} \setminus \emptyset$ | |
| Oct 5, 2022 at 11:24 | comment | added | Fabius Wiesner | I think that the no-"capped" concept can be formalized saying that we exclude families such that there exists an edge in their Hasse diagram such that removing that edge makes the graph disconnected. | |
| Oct 5, 2022 at 10:29 | comment | added | Peter Taylor | Two approaches which I can see would be to require that each element be in at least $\alpha |\mathcal{F}|$ members of the family, or that each element be in a set of size no more than $\alpha n$. Those may still allow some workarounds. As a separate note, I have a brute force search running for $n=6$ and if the optimal family it finds is better than a "capped" $2^{[4]}$ this may suggest a less objectionable construction. | |
| Oct 5, 2022 at 10:21 | comment | added | Fabius Wiesner | I wonder if there is a way to formalize the concept of a family without "cap", because here we have a smaller union closed family $2^{[k]}$ then "capped" where the abundant elements of $2^{[k]}$ are also abundant elements of $\mathcal{f}$. | |
| Oct 5, 2022 at 10:06 | comment | added | Peter Taylor | @BillyJoe, take the construction given and add one set: $[n-2] \cup \{n\}$ to meet the new constraint. | |
| Oct 5, 2022 at 9:20 | comment | added | Fabius Wiesner | Thank you very much, although I am tempted to reformulate the question excluding families such that there does not exist $A,B \in \mathcal{F}$, $A \not = B$, $A,B \not = U(\mathcal{F})$ such that $A \cup B = U(\mathcal{F})$. I don't know if it is better that I post a new question. | |
| Oct 5, 2022 at 8:37 | history | answered | Peter Taylor | CC BY-SA 4.0 |