Timeline for A conjecture about inclusion–exclusion
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 17 at 8:25 | comment | added | a3nm | @PietroMajer: Good question! (I'm one of the colleagues mentioned in the post who worked on the conjecture.) There are two different claims: that the union can be expressed as an expression with arbitrary parentheses and nesting; or that the union can always be expressed by starting by a non-cancelling intersection and alternatively doing complement, union, complement, union, etc. (This means that the expression can be written without parentheses, or that it is a left-linear tree.) We don't know if either claim is true (the second is stronger), we also don't know if they are equivalent. | |
| Sep 5 at 11:39 | comment | added | Pietro Majer | do you conjecture some particular form of expression with disjoint union and subset complement, or do you think that one may need to apply these operations with any hyerarchy of parentheses? (that is e.g. a disjoint union of subset complements of disjoint unions of discrete complements of disjoint unions .. etc) | |
| Mar 21 at 6:07 | comment | added | Ilya Bogdanov | @juan Perhaps, it is better to insert such explanations into the question, in order for the reader to learn that without reading all the comments. | |
| Mar 20 at 15:02 | comment | added | M.Monet | @SamHopkins: yes, the coefficients of the various intersections are given by the Mobiüs function of the corresponding "intersection lattice". I do not mention the Mobiús function in this post to simplify the presentation as it is not needed to explain the conjecture | |
| Mar 20 at 14:56 | comment | added | M.Monet | @MaxAlekseyev: We do not require such a thing, the only requirement is to obtain an expression that, at the leaves (seing the expression as a tree with disjoint unions and subset complements as the internal nodes), uses only the non-cancelling intersections. But it is possible to show that if such an expression exists then there is one in which all the non-cancelling intersections occur, and with their multiplicity being given by the Mobius fonction (consequence of Lemma 4.4 and Proposition 4.7 of the note, if you are curious) | |
| Mar 20 at 10:27 | comment | added | juan | @Ilya Bogdanov In your case the intersection $\{a\}$ is also non cancelling, because it is equal to $S_1\cap S_2$, $S_1\cap S_3$, $S_2\cap S_3$ and also to $S_1\cap S_2\cap S_3\}$ so its coefficient is $3(-1)+1(+1)=-2$. More explanation in my entry explaining the conjecture in the "Blog del Imus" institucional.us.es/blogimus/en/2024/03/still-hot-from-the-oven | |
| Mar 20 at 7:02 | comment | added | Ilya Bogdanov | If $S_1=\{a,b\}$, $S_2=\{a,c\}$, $ S_3=\{a,d\}$, then the only non-cancelling intersections are the $S_i$ themselves, and you cannot do anything with them using the operations at hand. Perhaps, you need to correct the definition of cancelling? | |
| Mar 19 at 19:25 | comment | added | Jérôme JEAN-CHARLES | I am not sure but KLaus Dohmen : Improved Bonferroni Inequalities via Abstract Tubes might provide some tools. | |
| Mar 19 at 10:44 | comment | added | Max Alekseyev | Do you require each non-cancelling intersection present in the expression for $\cup_i S_i$ and only once? Does intersection $S_T$ have to be a part of disjoint union if $|T|$ is odd, and complemented otherwise? | |
| Mar 18 at 16:44 | comment | added | Sam Hopkins | @mathworker21 Touché. So I added tags for these. | |
| Mar 18 at 16:43 | history | edited | Sam Hopkins |
edited tags
|
|
| Mar 18 at 16:03 | comment | added | mathworker21 | @SamHopkins You could also click on the paper | |
| Mar 18 at 15:39 | comment | added | LSpice |
MathJax note: The $ that ends the "preamble" must appear immediately adjacent to the opening text of the post, or else the post itself will start with spurious blank space. TeX note: In {align} environments, even-numbered columns start with atoms, making $\begin{aligned}a&=b\end{aligned}$ \begin{align} a & = b \end{align} space nicely but requiring you to insert the atom yourself in $\begin{aligned}a=&b\end{aligned}$ \begin{align} a = & b \end{align}, making it $\begin{aligned}a={}&b\end{aligned}$ \begin{align} a ={} & b \end{align}, for proper spacing. I edited both accordingly.
|
|
| Mar 18 at 15:36 | history | edited | LSpice | CC BY-SA 4.0 |
Spacing
|
| Mar 18 at 15:29 | comment | added | Sam Hopkins | I feel that there must be a way to formulate this using lattices... (And I see that you have "Möbius inversion" as a tag.) | |
| Mar 18 at 14:24 | history | edited | M.Monet | CC BY-SA 4.0 |
formating
|
| S Mar 18 at 13:55 | review | First questions | |||
| Mar 18 at 14:45 | |||||
| S Mar 18 at 13:55 | history | asked | M.Monet | CC BY-SA 4.0 |