The Non-Cancelling-Intersections Conjecture Fails for Left-Linear Trees

Abstract

First formulated by Amarilli, Monet, and Suciu (arXiv:2401.16210, 2024), the Non-Cancelling Intersections (NCI) conjecture is an open problem in combinatorics stating that any set union can be constructively built from its algebraically non-cancelling intersections using only disjoint unions and subset complements. In the same paper, two orthogonal possible strengthenings are proposed: using only left-linear trees, and using non-trivial intersections only positively or only negatively depending on the sign of their Möbius value. Here we show that using only left-linear trees, the conjecture is false (independent of the other strengthening). Our argument is non-constructive. We prove the existence of a counterexample, though it is of immense size.

Disclosure

“count) and characterizing which µ = 0 vertices are necessary. 3. Full NCI conjecture: Determining whether this argument can be extended to refute the NCI conjecture in its full generality. This is work in progress. Use of AI Claude (Anthropic) was used to write the first four paragraphs of the introduction, parts of the preliminaries, the proof of Lemma A.1 and Theorem 6.2 and the argument that the gi in (6.1) may be taken to lie in Q. The formulation of Theorem 6.3”

PDF page 25

Classification

Substantial proof generation

Multiplier

10

Verified

2026-08-22T17:04:11.342618Z

Structural counts