Non-Cancelling-Intersections conjecture

For every finite set $X$ and every finite family of subsets $A_1,\ldots,A_n\subseteq X$ , let $\mathcal{I}$ be the set of distinct nonempty intersections $\bigcap_{i\in S}A_i$ for $\varnothing\ne S\subseteq\{1,\ldots,n\}$ . For each $I\in\mathcal{I}$ , let $m(I)$ be its Möbius coefficient in the inclusion–exclusion expansion of the indicator function of $\bigcup_{i=1}^n A_i$ , and call $I$ non-cancelling when $m(I)\ne 0$ . The conjecture asserts that $\bigcup_{i=1}^n A_i$ can be constructed from the non-cancelling intersections using finitely many disjoint unions $B\sqcup C$ and subset complements $B\setminus C$ with $C\subseteq B$ .

References

Primary source

arXiv

Additional references

The Non-Cancelling-Intersections Conjecture Fails for Left-Linear Trees — arXiv — Wilhelm, Hermann

combinatorics mbius-inversion

1 week ago

Progress summary

Refreshed 1 week ago

Claimed progress

A new counterexample rules out a more restrictive version of the conjecture, but the original conjecture remains open.

The Non-Cancelling-Intersections conjecture asks whether every union represented by non-cancelling intersections can be constructed from those intersections using disjoint union and subset complement. A 2024 preprint established partial cases but did not resolve the general conjecture.

Known results

The conjecture holds when there are no cancelling intersections (2024 preprint).
It holds with exactly one cancelling intersection, by Theorem $6.2$ (2024 preprint).
Exhaustive computation verified the stronger left-linear version for underlying sets of size at most $5$ ; searches at size $6$ were incomplete (2024 preprint).
The unrestricted case with multiple zero-valued nodes remains unresolved (2024 preprint).

August 2026 left-linear counterexample

Hermann Wilhelm reported that the constructive representation fails when witnessing trees are required to be left-linear. This refutes that proposed strengthening, but the argument is non-constructive and leaves the unrestricted NCI conjecture untouched.

Current status (as of August 2026): The left-linear strengthening is refuted, while the original Non-Cancelling-Intersections conjecture remains open beyond its known partial cases.

Sources

No solutions have been posted yet.