MICHAEL S. YANG

DOI: https://doi.org/10.5281/zenodo.22082890

The Non-Cancelling Intersections (NCI) Conjecture of Amarilli, Monet, and Suciu asks whether the union of a finite inclusion-incomparable family can always be constructed from exactly those intersections whose collected inclusion–exclusion coefficients are nonzero, using only disjoint union and subset complement. We prove a structural sufficient condition formulated in terms of an acyclic hypergraph representation. Let N be the family of non-cancelling intersections and let B be its inclusion-maximal members. If B admits a join tree satisfying the running-intersection property and every nonempty edge separator of that tree belongs to N, then ⋃︁F has an explicit left-linear construction over N. Rooting the join tree, one subtracts the parent separator from each child bag and then adjoins the resulting residue by disjoint union. Running intersection guarantees that each residue is disjoint from everything assembled earlier. This yields a linear-size structural certificate and a direct polynomial-time verifier once the join tree is supplied. We compare the theorem with the known partial cases and strengthenings in the original NCI paper and with the recent failure of unrestricted left-linear witnesses. As supporting evidence only, a public implementation verified 50,000 independently generated theorem-eligible instances, including examples with eleven collected cancelling intersections. The theorem and verifier are independent of any private search acceleration.

non-cancelling intersections, inclusion–exclusion, Möbius inversion, join trees, acyclic hypergraphs, running intersection, disjoint union, subset complement.

We proved a constructive acyclic-hypergraph sufficient condition for the Non-Cancelling Intersections Conjecture. If the maximal non-cancelling intersections admit a join tree whose nonempty edge separators are themselves non-cancelling, then the target union has the explicit left-linear representation ⋃︂ F =Br ˙ ∪ ˙ ⋃︂ (︂ B ˙ \ (B ∩P(B)) )︂ . B̸=Br 9 The proof is a rooted residue decomposition: running intersection makes each child residue disjoint from the already assembled side, while separator non-cancellation makes each residue legally constructible. The theorem yields a linear-size structural certificate and a polynomial-time verifier once a join tree is supplied. It also identifies a natural positive left-linear class despite the failure of unrestricted left-linearity. Supporting computation verified the construction on 50,000 independently generated theorem-eligible families in both a reference run and an independent Carnets/SciPy replication.

[1] A. Amarilli, M. Monet, and D. Suciu, “The Non-Cancelling Intersections Conjecture,” arXiv preprint
arXiv:2401.16210, 2024. Available: https://arxiv.org/abs/2401.16210.
[2] H. Wilhelm, “The Non-Cancelling-Intersections Conjecture Fails for Left-Linear Trees,” arXiv preprint
arXiv:2608.19414, 2026. Available: https://arxiv.org/abs/2608.19414.
[3] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, “On the Desirability of Acyclic Database Schemes,” Journal of
the ACM, vol. 30, no. 3, pp. 479–513, 1983.
[4] G.-C. Rota, “On the Foundations of Combinatorial Theory I. Theory of Möbius Functions,” Zeitschrift für
Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 2, pp. 340–368, 1964.
[5] R. P. Stanley, Enumerative Combinatorics, Volume 1, 2nd ed. Cambridge University Press, 2011.

MICHAEL S. YANG (2026). A JOIN-TREE SUFFICIENT CONDITION FOR THE NON-CANCELLING INTERSECTIONS CONJECTURE. International Journal of Computer Techniques, 13(4), 266–275. ISSN: 2394-2231. DOI: https://doi.org/10.5281/zenodo.22082890