[#P2884] Constructing a union from non-cancelling intersections

A flat mathematical diagram showing sets joined by intersection and union operations. — A schematic view of sets joined by intersection and union operations.

Problem. Let \(\mathcal F=\{S_1,\ldots,S_n\}\) be a finite family of pairwise inclusion-incomparable finite sets. For each nonempty \(T\subseteq\{1,\ldots,n\}\), put \(S_T=\bigcap_{i\in T}S_i\). For each distinct set \(U\) among the \(S_T\), define \(\mu(U)=\sum_{T:S_T=U}(-1)^{|T|+1}\), and call \(U\) non-cancelling when \(\mu(U)\ne0\). Starting with the non-cancelling intersections, one may form \(A\mathbin{\dot\cup}B=A\cup B\) only when \(A\cap B=\varnothing\), and \(A\mathbin{\dot\setminus}B=A\setminus B\) only when \(B\subseteq A\). Can \(\bigcup_{i=1}^n S_i\) always be obtained by finitely many such operations?

1Context

The conjecture has a natural finite search at each ground-set size. Minimal counterexample searches, canonical intersection lattices, and expression certificates are compact artifacts that can be reused across algebraic and database-theoretic approaches.

2Problem setup

Definition 1 (The coefficient mu(U). The coefficient mu(U) is the total coefficient of the distinct intersection U after equal terms in the inclusion-exclusion formula are collected.

Definition 2 (The two partial operations are disjoint union and subset complement; an expression). The two partial operations are disjoint union and subset complement; an expression is valid only when every operation node satisfies its stated disjointness or containment condition.

Remark 1. The conjecture has a natural finite search at each ground-set size. Minimal counterexample searches, canonical intersection lattices, and expression certificates are compact artifacts that can be reused across algebraic and database-theoretic approaches.

3What counts as a solution

Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.
A counterexample must list the sets, compute every collected coefficient mu(U), and include a complete finite invariant or exhaustive certificate excluding all valid expression trees.

1Status

Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.^[1]

1Packet records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.^[1] Relevance to this problem For non cancelling intersections conjecture, pins the dated research frontier: UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. Give a valid expression for every finite incomparable. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven. A complete resolution must satisfy this condition: Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists. Open full record →
	Trace	Reported
attempt · Route 1 Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists.^[1] Relevance to this problem For Constructing a union from non-cancelling intersections, record non-cancelling-intersections-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Give a valid expression for every finite incomparable family and prove the construction terminates, or give a finite family for which no expression over the allowed leaves and partial operations exists. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-31. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.

On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for question 467258; all mathematical comments were checked for proposed counterexamples and clarifications.
Amarilli, Monet, and Suciu, arXiv:2401.16210, is the primary source for the exact conjecture. Version 1 gives a Boolean-lattice reformulation and partial cases while retaining the general statement as a conjecture.
A 2024 SIGMOD Record survey says the associated database-circuit question still hinges on the unproven non-cancelling intersections conjecture; searches through 2026 located no superseding proof.
A TheoremDB search for non-cancelling intersections, dot-algebra, inclusion-exclusion coefficients, and the Boolean-lattice formulation found no duplicate.

Recorded example 1. For S1={a,b,d}, S2={a,b,c,e}, and S3={a,c,f}, collecting equal intersections cancels {a}; the remaining intersections can still be combined by valid subset complements and disjoint unions to obtain {a,b,c,d,e,f}.

Computational notes

The primary note reports brute-force success on large collections of finite examples but presents that evidence only as support for the conjecture.

How the 2 records connectTyped relations and evidence flow

ProblemConstructing a union from non-cancelling intersections

Claim 1Current status and unresolved remainderin this packetSupported
Route 1Resolve the stated acceptance conditionaddressesReported

2See also

Cycle Double Cover Conjecturecombinatorics
The Total Coloring Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics

How to cite

TheoremDB contributors, “Constructing a union from non-cancelling intersections,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/non-cancelling-intersections-conjecture

This page as plain text: non-cancelling-intersections-conjecture.md

This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net^[1], current as of July 31, 2026.

1References

Packet source. MathOverflow: A conjecture about inclusion-exclusion. Question 467258 and all visible comments, checked through the Stack Exchange API on 2026-07-27. Question 467258 and all visible comments, checked through the Stack Exchange API on 2026-07-27. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Constructing a union from non-cancelling intersections: UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Source named by the research packet.
Antoine Amarilli, Mikaël Monet, and Dan Suciu, “The Non-Cancelling Intersections Conjecture”. arXiv:2401.16210 (2024). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:2401.16210, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Also cited at Full preprint relevant to Constructing a union from non-cancelling intersections.Source used to assess the problem's recorded status.For Constructing a union from non-cancelling intersections: UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.
Antoine Amarilli and Florent Capelli, “Tractable Circuits in Database Theory,” SIGMOD Record 53(2) (2024), 6-20. Status evidence identified in the source record and checked at the linked publication. ↗website · primary source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has zero answers. The authors' primary 2024 note states the conjecture, proves a partial result, and does not give a general solution; later checked research material still calls it unproven.Also cited at Section 5, discussion of the non-cancelling intersections conjecture, especially page 13.Source used to assess the problem's recorded status.For Constructing a union from non-cancelling intersections, this source records a 2024 survey use of the conjecture and its unresolved role in probabilistic-query provenance.

This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.

[#P2884] Constructing a union from non-cancelling intersections

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance