Non-Empty Strongly Incomparable Uncomplemented Families: the Bound $2^{n-1}-1$ When Some Element Is Private to One Family
low tier2026-11-13OP-13704 research-level results in one postreviewed by Claude Code中文版
Abstract
For integers $n \ge 3$ and $3 \le t \le n$, Conjecture 4.3 of arXiv:2611.12199 posits that the maximum total cardinality $M(n,t)$ of $t$ non-empty, mutually strongly incomparable, and uncomplemented families of subsets of an $n$-element set is exactly $2^{n-1} - 1$. While previous results established that $2^{n-1} - 1 \le M(n,t) \le 2^{n-1}$, the upper bound left a gap of one. We prove that the conjectured upper bound $\sum_{j} |\mathcal{A}_j| \le 2^{n-1} - 1$ holds whenever at least one ground-set element occurs in sets from at most one family $\mathcal{A}_i$, requiring uncomplementedness only for $\mathcal{A}_i$ itself. The paper's own extremal construction has such an element, so no configuration of that shape reaches $2^{n-1}$. The proof shows that the union of the other families shatters strictly more sets than it contains, and bounds the designated family together with these shattered sets inside the subsets of the remaining $n-1$ elements. We also establish the conjectured bound in the three-family setting when two families are singletons, when the two families other than an uncomplemented one have combined cardinality strictly below $2^{\lceil n/2 \rceil}$, and for any $t \ge 3$ when the families other than an uncomplemented one have a union of VC-dimension strictly below $\lceil n/2 \rceil$. All definitions, lemmas, and theorems have been formalized and verified in Lean 4.
1. Introduction
Let $n$ and $t$ be positive integers. A family $\mathcal{F}$ of subsets of an $n$-element set $[n]$ is said to be uncomplemented if it contains no complementary pair: for every set $A \in \mathcal{F}$, the complement $A^c = [n] \setminus A$ does not belong to $\mathcal{F}$. A collection of set families $\mathcal{A}_1, \dots, \mathcal{A}_t \subseteq 2^{[n]}$ is mutually strongly incomparable if no set in any family is a subset of a set in a different family: for all indices $i \ne j$, if $A \in \mathcal{A}_i$ and $B \in \mathcal{A}_j$, then $A \not\subseteq B$ and $B \not\subseteq A$.
In arXiv:2611.12199, the authors investigate extremal properties of such families, focusing on the maximum total size \[ M(n,t) = \max \sum_{i=1}^t |\mathcal{A}_i|, \] where the maximum is taken over all collections of $t$ non-empty, uncomplemented, mutually strongly incomparable families on $[n]$. Theorem 1.7 of arXiv:2611.12199 (formalized as op_1370_uncomplemented_strongly_incomparable_upper_bound) proves that for all natural numbers $n$ and $t$, any collection of uncomplemented, strongly incomparable families satisfies $\sum_{i=1}^t |\mathcal{A}_i| \le 2^{n-1}$. This general bound can be established via algebraic methods; indeed, hilton_strong_incomparability_matrix shows that for every $n$, there exist matrices $L \in K^{2^n \times 2^{n-1}}$ and $R \in K^{2^{n-1} \times 2^n}$ over a field $K$ whose product vanishes on incomparable pairs while every uncomplemented family induces a non-singular principal submatrix.
On the other hand, Proposition 4.2 of arXiv:2611.12199 (formalized as op_1370_uncomplemented_strongly_incomparable_lower_bound) constructs, for all $n \ge 3$ and $3 \le t \le n$, non-empty uncomplemented strongly incomparable families achieving total size $\sum_{i=1}^t |\mathcal{A}_i| = 2^{n-1} - 1$. For example, when $n = 3$ and $t = 3$, op_1370_case_n3_t3 confirms that the maximum total size is $2^{3-1} - 1 = 3$. Based on this construction, Conjecture 4.3 of arXiv:2611.12199 conjectures that for all $n \ge 3$ and $3 \le t \le n$, \[ M(n,t) = 2^{n-1} - 1. \] The existing bounds in arXiv:2611.12199 thus leave a gap of exactly one: \[ 2^{n-1} - 1 \le M(n,t) \le 2^{n-1}. \]
The central difficulty in eliminating this gap of one lies in the fact that the linear algebraic bound $2^{n-1}$ is sharp for $t = 1$ and $t = 2$, where a single uncomplemented family can have size $2^{n-1}$. The requirement that $t \ge 3$ and that each family is non-empty forces structural interaction and cross-incomparability between distinct families, but extracting the required reduction of 1 from linear algebra alone is challenging.
We prove Conjecture 4.3's bound under several structural conditions; the general conjecture remains open. Our primary result, op_1370_private_element_bound, proves that for any $t \ge 3$ and any $n$, if there exists an element $x \in [n]$ that appears only in sets belonging to at most one family $\mathcal{A}_i$, and $\mathcal{A}_i$ is uncomplemented, then $\sum_{j=1}^t |\mathcal{A}_j| \le 2^{n-1} - 1$. Under this condition, none of the remaining $t-1$ families are required to be uncomplemented. The construction of Proposition 4.2 has exactly this shape: the element $1$ occurs only in sets of $\mathcal{A}_1$. So the theorem says that no configuration built like the paper's extremal example can reach $2^{n-1}$. We further prove the conjectured bound in several other settings: when $t = 3$ and two of the families are singletons (op_1370_three_two_singletons), when $t = 3$ and the union of two families has size strictly below $2^{\lceil n/2 \rceil}$ (op_1370_small_pair_bound), and for arbitrary $t \ge 3$ when the union of all other families has VC-dimension strictly below $\lceil n/2 \rceil$ (op_1370_low_vcdim_others_bound). All proofs have been verified in Lean 4.
2. Preliminaries
We work in the finite universe of subsets of an $n$-element type, modeled in Lean 4 by Finset (Fin n). A collection of such subsets is an element of Finset (Finset (Fin n)).
We begin by recalling the formal definitions used throughout the development.
Definition 1 (is_uncomplemented). Let $\alpha$ be a finite type with decidable equality. A family of sets $\mathcal{A} \in \operatorname{Finset}(\operatorname{Finset} \alpha)$ is uncomplemented if no set and its complement both belong to $\mathcal{A}$: \[ \operatorname{is\_uncomplemented}(\mathcal{A}) \iff \forall A \in \mathcal{A},\, A^c \notin \mathcal{A}. \] In Lean, this is defined as: ``lean def is_uncomplemented {α : Type*} [Fintype α] [DecidableEq α] (𝒜 : Finset (Finset α)) : Prop := ∀ A ∈ 𝒜, Aᶜ ∉ 𝒜 `` Remark: The complement $A^c$ is taken relative to the full universe $\alpha$. An uncomplemented family on an $n$-element set can contain at most $2^{n-1}$ sets, since it can contain at most one set from each complementary pair $\{A, A^c\}$.
Definition 2 (strongly_incomparable). Let $\iota$ and $\alpha$ be types. An indexed collection of families $\mathcal{A} : \iota \to \operatorname{Finset}(\operatorname{Finset} \alpha)$ is strongly incomparable if no set in one family is a subset of a set in another family: \[ \operatorname{strongly\_incomparable}(\mathcal{A}) \iff \forall i, j \in \iota,\, i \ne j \implies \forall A \in \mathcal{A}(i),\, \forall B \in \mathcal{A}(j),\, A \not\subseteq B. \] In Lean, this is defined as: ``lean def strongly_incomparable {ι α : Type*} (𝒜 : ι → Finset (Finset α)) : Prop := ∀ i j, i ≠ j → ∀ A ∈ 𝒜 i, ∀ B ∈ 𝒜 j, ¬(A ⊆ B) `` Remark: This condition is strictly stronger than requiring sets in different families to be distinct. If $A \in \mathcal{A}(i)$ and $B \in \mathcal{A}(j)$ with $i \ne j$, then neither $A \subseteq B$ nor $B \subseteq A$ can hold; in particular, $\mathcal{A}(i) \cap \mathcal{A}(j) = \emptyset$ whenever $i \ne j$.
Definition 3 (Pajor Shattering and Shatterer). For a set family $\mathcal{F} \subseteq 2^\alpha$, a set $S \subseteq \alpha$ is said to be shattered by $\mathcal{F}$ in the sense of Pajor if for every subset $S' \subseteq S$, there exists $T \in \mathcal{F}$ such that $T \cap S = S'$. The family of all sets shattered by $\mathcal{F}$ is denoted by $\mathcal{F}.\operatorname{shatterer}$, or $\operatorname{shatterer}(\mathcal{F})$. Remark: By Pajor's theorem, every finite family satisfies $|\mathcal{F}| \le |\operatorname{shatterer}(\mathcal{F})|$.
Definition 4 (VC-Dimension). The VC-dimension of a family $\mathcal{F} \subseteq 2^\alpha$, denoted $\operatorname{vcDim}(\mathcal{F})$, is the maximum cardinality of a set shattered by $\mathcal{F}$: \[ \operatorname{vcDim}(\mathcal{F}) = \max \{ |S| : S \in \operatorname{shatterer}(\mathcal{F}) \}. \]
Definition 5 (Private Element Condition). Let $\mathcal{A} : \operatorname{Fin} t \to \operatorname{Finset}(\operatorname{Finset}(\operatorname{Fin} n))$ be an indexed collection of families. An element $x \in \operatorname{Fin} n$ is private to family $i \in \operatorname{Fin} t$ if no set from any other family contains $x$: \[ \forall j \in \operatorname{Fin} t,\, j \ne i \implies \forall S \in \mathcal{A}(j),\, x \notin S. \] Under this condition, all sets belonging to $\bigcup_{j \ne i} \mathcal{A}(j)$ are subsets of the punctured ground set $V = \{x\}^c$.
3. Main result
The main result formalizes the resolution of Hilton's conjecture (Conjecture 4.3 of arXiv:2611.12199) under the hypothesis that at least one ground-set element is isolated to at most one family.
Theorem 1 (op_1370_private_element_bound). Let $n, t$ be natural numbers with $t \ge 3$. Let $\mathcal{A}_0, \dots, \mathcal{A}_{t-1}$ be non-empty families of subsets of an $n$-element set that are mutually strongly incomparable. Suppose there exist an index $i \in \operatorname{Fin} t$ and an element $x \in \operatorname{Fin} n$ such that: 1. $\mathcal{A}_i$ is uncomplemented, and 2. for all $j \ne i$ and every $S \in \mathcal{A}_j$, $x \notin S$. Then the total number of sets across all $t$ families satisfies: \[ \sum_{j=0}^{t-1} |\mathcal{A}_j| \le 2^{n-1} - 1. \] In Lean, the theorem statement reads: ``lean theorem op_1370_private_element_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (𝒜 i)) (hx : ∀ j, j ≠ i → ∀ S ∈ 𝒜 j, x ∉ S) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1 ` The Lean statement matches the mathematical statement directly: the universe is Fin n, the collection is indexed by Fin t with $3 \le t$, families are assumed Nonempty and strongly_incomparable, index $i$ is uncomplemented, element $x$ is absent from all other families, and the sum of Finset.card over Fin t` is at most $2^{n-1} - 1$.
Beyond Theorem 1, three additional theorems establish the conjectured upper bound $2^{n-1} - 1$ under distinct structural hypotheses:
Theorem 2 (op_1370_three_two_singletons). For $n \ge 3$, if three mutually strongly incomparable families $\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2$ of subsets of $[n]$ have $\mathcal{A}_0 = \{A\}$ and $\mathcal{A}_1 = \{B\}$ as singletons, and $\mathcal{A}_2$ is uncomplemented, then: \[ |\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| \le 2^{n-1} - 1. \]
Theorem 3 (op_1370_small_pair_bound). For $n \ge 3$, let $\mathcal{A}_0, \mathcal{A}_1, \mathcal{A}_2$ be three non-empty mutually strongly incomparable families of subsets of $[n]$. If $\mathcal{A}_2$ is uncomplemented and the combined size of the first two families satisfies $|\mathcal{A}_0| + |\mathcal{A}_1| < 2^{\lceil n/2 \rceil}$, then: \[ |\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| \le 2^{n-1} - 1. \] Neither $\mathcal{A}_0$ nor $\mathcal{A}_1$ is assumed to be uncomplemented.
Theorem 4 (op_1370_low_vcdim_others_bound). For $n \ge 3$ and $t \ge 3$, let $\mathcal{A}_0, \dots, \mathcal{A}_{t-1}$ be non-empty mutually strongly incomparable families of subsets of $[n]$. If one family $\mathcal{A}_i$ is uncomplemented and the union $\bigcup_{j \ne i} \mathcal{A}_j$ has VC-dimension strictly less than $\lceil n/2 \rceil$, then: \[ \sum_{j=0}^{t-1} |\mathcal{A}_j| \le 2^{n-1} - 1. \] No uncomplementedness assumption is required for any $\mathcal{A}_j$ with $j \ne i$.
theorem op_1370_private_element_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hunc : is_uncomplemented (𝒜 i)) (hx : ∀ j, j ≠ i → ∀ S ∈ 𝒜 j, x ∉ S) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 14. Proof
The proof of the main theorem op_1370_private_element_bound relies on the interaction between strong incomparability, set projection, and shattering capacity.
The underlying strategy is as follows. We isolate the private element $x \in \operatorname{Fin} n$, which belongs to sets of at most one family $\mathcal{A}_i$. We let $V = \{x\}^c$ be the punctured universe of cardinality $n-1$. The union $B$ of all other families $\mathcal{A}_j$ ($j \ne i$) consists entirely of subsets of $V$. We partition the designated family $\mathcal{A}_i$ into two collections: $C$, the sets not containing $x$, and $D$, the sets containing $x$ with $x$ removed. Both $C$ and $D$ are families of subsets of $V$. Strong incomparability between $\mathcal{A}_i$ and the other families ensures that every set in $C$ is incomparable to every set in $B$, and that no set in $D$ can contain a set of $B$. Furthermore, the uncomplementedness of $\mathcal{A}_i$ ensures that $C$ and $D$ are anti-complementary in $V$: for any $c \in C$, its relative complement $V \setminus c$ cannot belong to $D$. Under these structural conditions, a capacity lemma (op_1370_shattered_capacity) guarantees that $|C| + |D| + |\operatorname{shatterer}(B)| \le 2^{|V|} = 2^{n-1}$. Finally, because $t \ge 3$, the index set $I = (\operatorname{Fin} t) \setminus \{i\}$ has size at least 2, so $B$ is the union of at least two non-empty strongly incomparable families. A strict shattering lemma (op_1370_incomparable_strict_shattering) proves that $|B| < |\operatorname{shatterer}(B)|$. Summing these bounds yields the strict inequality $\sum_j |\mathcal{A}_j| < 2^{n-1}$, proving the theorem.
We now state the auxiliary lemmas established in the library and detail their roles.
Lemma 1 (op_1370_incomparable_strict_shattering). Let $F$ and $G$ be non-empty finite families of sets such that every member of $F$ is incomparable with every member of $G$: \[ \forall A \in F,\, \forall B \in G,\, A \not\subseteq B \text{ and } B \not\subseteq A. \] Then their union shatters strictly more sets than its cardinality: \[ |F \cup G| < |\operatorname{shatterer}(F \cup G)|. \] Proof: The Lean proof follows the standard inductive proof of Pajor's inequality $|H| \le |\operatorname{shatterer}(H)|$, splitting on one ground element $a$ at a time. Write $H_0$ for the members of $H$ without $a$ and $H_1$ for the members with $a$, with $a$ removed. Then $|\operatorname{shatterer}(H_0 \cup H_1)| + |\operatorname{shatterer}(H_0) \cap \operatorname{shatterer}(H_1)| \le |\operatorname{shatterer}(H)|$, the second term counting the sets $S \cup \{a\}$. Both sections inherit cross-incomparability from $F$ and $G$. If in one section the parts coming from $F$ and from $G$ are both non-empty, the induction hypothesis gives strict inequality for that section, and Pajor's inequality for the other section finishes. Otherwise all of $F$ lies on one side of $a$ and all of $G$ on the other, say $F \subseteq H_0$ and $G$ gives $H_1$. Cross-incomparability makes $H_0$ and $H_1$ disjoint (a set $A$ in both would give $A \subseteq A \cup \{a\}$ across the two families), so $|H| = |H_0 \cup H_1| \le |\operatorname{shatterer}(H_0 \cup H_1)|$, while the empty set lies in $\operatorname{shatterer}(H_0) \cap \operatorname{shatterer}(H_1)$; the displayed inequality then gives $|H| < |\operatorname{shatterer}(H)|$.
Lemma 2 (op_1370_shattered_capacity). Let $V$ be a finite set. Let $B, C, D \subseteq 2^V$ be families of subsets of $V$ satisfying: 1. Every member of $C$ is incomparable with every member of $B$: $\forall c \in C,\, \forall b \in B,\, c \not\subseteq b \text{ and } b \not\subseteq c$. 2. No member of $D$ contains a member of $B$: $\forall d \in D,\, \forall b \in B,\, b \not\subseteq d$. 3. For every $c \in C$, the relative complement $V \setminus c$ is absent from $D$: $\forall c \in C,\, V \setminus c \notin D$. Then: \[ |C| + |D| + |\operatorname{shatterer}(B)| \le 2^{|V|}. \] Proof: Inside the power set of $V$, let $H$ be the sets containing some member of $B$ and $Q$ the sets incomparable with every member of $B$; write $\bar X = \{V \setminus S : S \in X\}$. Then $C \subseteq Q$, so $\bar C \subseteq \bar Q$. $D$ is disjoint from $H$ by condition 2 and from $\bar C$ by condition 3, so $|D| + |H \cup \bar C| \le 2^{|V|}$. For a shattered set $T$ of $B$, some $b_0 \in B$ meets $T$ in the empty set, so $V \setminus T \supseteq b_0$ lies in $H$; and $T$ lies inside some $b_1 \in B$, so $T \notin Q$ and $V \setminus T \notin \bar Q$. Hence complementation maps $\operatorname{shatterer}(B)$ injectively into $H \setminus \bar Q \subseteq H \setminus \bar C$, and $|C| + |\operatorname{shatterer}(B)| \le |\bar C| + |H \setminus \bar C| = |H \cup \bar C|$, which gives the bound.
We now assemble the proof of op_1370_private_element_bound. Let $V = \{x\}^c \subseteq \operatorname{Fin} n$, so $|V| = n - 1$. Let $I = (\operatorname{Finset.univ}) \setminus \{i\}$. Define: - $B = \bigcup_{j \in I} \mathcal{A}_j$, - $C = \{ S \in \mathcal{A}_i \mid x \notin S \}$, - $D = \{ S \setminus \{x\} \mid S \in \mathcal{A}_i,\, x \in S \}$.
We verify the hypotheses of Lemma 2:
- Ground set inclusion: By the hypothesis $hx$, for all $j \ne i$ and $S \in \mathcal{A}_j$, $x \notin S$, so $S \subseteq V$; hence every $S \in B$ satisfies $S \subseteq V$. By definition of $C$, $x \notin S$, so $S \subseteq V$. For any $d \in D$, $d = S \setminus \{x\}$, so $x \notin d$ and $d \subseteq V$.
- Incomparability of $C$ and $B$: Let $c \in C$ and $b \in B$. Then $c \in \mathcal{A}_i$ and $b \in \mathcal{A}_j$ for some $j \in I$ (so $j \ne i$). By strong incomparability
hinc, $c \not\subseteq b$ and $b \not\subseteq c$. - Containment condition between $B$ and $D$: Suppose for contradiction that $b \subseteq d$ for some $b \in B$ and $d \in D$. Then $b \in \mathcal{A}_j$ for some $j \ne i$, and $d = s \setminus \{x\}$ for some $s \in \mathcal{A}_i$ with $x \in s$. Since $s \setminus \{x\} \subseteq s$, we have $b \subseteq s$, which contradicts strong incomparability between $\mathcal{A}_j$ and $\mathcal{A}_i$. Thus no member of $D$ contains a member of $B$.
- Anti-complementarity of $C$ and $D$: Suppose $V \setminus c \in D$ for some $c \in C$. Then there exists $s \in \mathcal{A}_i$ with $x \in s$ such that $V \setminus c = s \setminus \{x\}$. Since $x \notin c$ and $x \in s$, taking the union with $\{x\}$ on both sides gives $s = c^c$ in $\operatorname{Fin} n$. But then $c \in \mathcal{A}_i$ and $c^c \in \mathcal{A}_i$, contradicting the assumption
is_uncomplemented (𝒜 i). Thus $V \setminus c \notin D$.
Now we calculate the cardinalities. The map $s \mapsto s \setminus \{x\}$ is injective on $\{ s \in \mathcal{A}_i \mid x \in s \}$ because $s = (s \setminus \{x\}) \cup \{x\}$. Thus $|D| = |\{ s \in \mathcal{A}_i \mid x \in s \}|$. Since $C = \{ s \in \mathcal{A}_i \mid x \notin s \}$, we have: \[ |C| + |D| = |\mathcal{A}_i|. \] Furthermore, because $\mathcal{A}$ is strongly incomparable, for any $j \ne k$ with $j, k \in I$, the families $\mathcal{A}_j$ and $\mathcal{A}_k$ are disjoint (if $A \in \mathcal{A}_j \cap \mathcal{A}_k$, then $A \subseteq A$, contradicting strong incomparability). Thus: \[ |B| = \sum_{j \in I} |\mathcal{A}_j|, \] and consequently $\sum_{j \in \operatorname{Fin} t} |\mathcal{A}_j| = |\mathcal{A}_i| + |B| = |C| + |D| + |B|$.
Next, because $t \ge 3$, the cardinality of $I$ is $t - 1 \ge 2$. Thus we can choose an element $j \in I$ and let $J = I \setminus \{j\} \ne \emptyset$. Decomposing $B$, we write $B = \mathcal{A}_j \cup B'$, where $B' = \bigcup_{k \in J} \mathcal{A}_k$. Since each $\mathcal{A}_k$ is non-empty, both $\mathcal{A}_j$ and $B'$ are non-empty. For any $A \in \mathcal{A}_j$ and $T \in B'$, $T \in \mathcal{A}_k$ for some $k \ne j$, so by strong incomparability, $A \not\subseteq T$ and $T \not\subseteq A$. Applying Lemma 1 (op_1370_incomparable_strict_shattering) to $\mathcal{A}_j$ and $B'$ gives: \[ |B| < |\operatorname{shatterer}(B)|. \] Finally, applying Lemma 2 (op_1370_shattered_capacity), we obtain: \[ |C| + |D| + |\operatorname{shatterer}(B)| \le 2^{|V|} = 2^{n-1}. \] Combining this with $|B| \le |\operatorname{shatterer}(B)| - 1$: \[ \sum_{j \in \operatorname{Fin} t} |\mathcal{A}_j| = |C| + |D| + |B| \le |C| + |D| + |\operatorname{shatterer}(B)| - 1 \le 2^{n-1} - 1. \] This completes the proof of op_1370_private_element_bound.
We now outline the proofs of the remaining results:
Proof of op_1370_three_two_singletons: Here $t = 3$, $n \ge 3$, $\mathcal{A}_0 = \{A\}$, $\mathcal{A}_1 = \{B\}$, and $\mathcal{A}_2$ is uncomplemented. The strong incomparability implies $A \not\subseteq B$, $B \not\subseteq A$, and every $S \in \mathcal{A}_2$ is incomparable to both $A$ and $B$. Lemma op_1370_incomparable_two_sets_card_bound states that if $A$ and $B$ are incomparable and an uncomplemented family $F$ has all elements incomparable to $A$ and $B$, then $2|F| + 6 \le 2^n = 2 \cdot 2^{n-1}$. Rewriting this inequality gives $|F| \le 2^{n-1} - 3$. The sum of sizes is $|\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| = 1 + 1 + |\mathcal{A}_2| \le 2 + (2^{n-1} - 3) = 2^{n-1} - 1$.
Proof of op_1370_small_pair_bound: Let $H = \mathcal{A}_0 \cup \mathcal{A}_1$. Since $\mathcal{A}_0$ and $\mathcal{A}_1$ are disjoint, $|H| = |\mathcal{A}_0| + |\mathcal{A}_1| < 2^{\lceil n/2 \rceil}$. By Lemma op_1370_small_family_shatterer_uncomplemented, any family with fewer than $2^{\lceil n/2 \rceil}$ sets has an uncomplemented shatterer, so $\operatorname{shatterer}(H)$ is uncomplemented. By Lemma 1, $|H| < |\operatorname{shatterer}(H)|$. Furthermore, no set in $\operatorname{shatterer}(H)$ or its complement can belong to $\mathcal{A}_2$, because any shattered set has a superset and a subset in $H$, which would violate incomparability with $\mathcal{A}_2$. Therefore, $\operatorname{shatterer}(H)$ and $\mathcal{A}_2$ are disjoint, and their union $\operatorname{shatterer}(H) \cup \mathcal{A}_2$ is uncomplemented. Since any uncomplemented family on $n$ elements has size at most $2^{n-1}$, we obtain: \[ |\operatorname{shatterer}(H)| + |\mathcal{A}_2| \le 2^{n-1}. \] Since $|H| < |\operatorname{shatterer}(H)|$, we conclude $|\mathcal{A}_0| + |\mathcal{A}_1| + |\mathcal{A}_2| \le 2^{n-1} - 1$.
Proof of op_1370_low_vcdim_others_bound: Let $B = \bigcup_{j \ne i} \mathcal{A}_j$. If a set $S$ and its complement were both shattered by $B$, one of them would have at least $\lceil n/2 \rceil$ elements, more than the VC-dimension of $B$. So $\operatorname{shatterer}(B)$ is uncomplemented. Lemma op_1370_uncomplemented_shatterer_others_bound states that the bound $2^{n-1}-1$ holds whenever the designated family and the shatterer of the union of the others are both uncomplemented; its proof is the argument given above for op_1370_small_pair_bound, with $B$ in place of $H$. It applies directly.
5. Discussion
The results presented here close the gap of one between the lower bound $2^{n-1} - 1$ and the upper bound $2^{n-1}$ of Proposition 4.2 of arXiv:2611.12199 under structural assumptions; Conjecture 4.3 itself remains open.
Specifically, op_1370_private_element_bound shows that whenever some element $x$ occurs only in sets of a single uncomplemented family $\mathcal{A}_i$, the conjectured bound $\sum_{j} |\mathcal{A}_j| \le 2^{n-1} - 1$ holds. Under this condition, no family other than $\mathcal{A}_i$ needs to be uncomplemented; strong incomparability alone forces the union of the remaining families to strictly expand under shattering, which bounds their collective capacity. Similarly, op_1370_small_pair_bound and op_1370_low_vcdim_others_bound confirm the conjecture whenever the remaining families are sparse in size or VC-dimension, again without requiring uncomplementedness outside the designated family.
However, these results do not fully resolve Conjecture 4.3 for completely general configurations. In particular, they leave open configurations where every ground element appears in at least two families, where every family has cardinality at least $2^{\lceil n/2 \rceil}$, and where the VC-dimension of the remaining families is at least $\lceil n/2 \rceil$. That such configurations can be non-trivial is highlighted by op_1370_pair_shatter_surplus_counterexample, which exhibits three uncomplemented, mutually strongly incomparable families on $n = 6$, each of cardinality 9, such that every element appears in at least two families and is absent from at least two families. So the private-element hypothesis can fail for every family at once, with all families large. In that example, for each pair of the three families, the shattered sets of their union together with their complements number 38.
The next questions emerging from arXiv:2611.12199 include:
- Without a private element, does some other counting of the shattered sets of $\bigcup_{j \ne i} \mathcal{A}_j$ against $\mathcal{A}_i$ still give the bound $2^{n-1}-1$?
- Can the algebraic polynomial method underlying
hilton_strong_incomparability_matrixbe combined with combinatorial shattering inequalities to bridge the gap of one in the general case without element isolation?
Why it is research-level
- Proves the conjectured upper bound for every n ≥ 3 in the three-family case when two families each consist of one set; the related paper leaves the bound open in this range
- Proves the conjectured bound for any number of families whenever one ground-set element occurs in at most one family, without requiring uncomplementedness of the others
- Proves the conjectured strict bound for all n when the first two of three families together have fewer than 2^ceil(n/2) sets, without requiring either of those two families to be uncomplemented
- Proves the strict bound for any number of nonempty incomparable families when all but one have union VC dimension below ceil(n/2), without requiring uncomplementedness of those other families
Lean declarations
- op_1370_private_element_boundLet at least three nonempty set families on an n-element ground set be mutually strongly incomparable. Suppose some element occurs in sets…
- op_1370_three_two_singletonsFor n at least three, if three mutually strongly incomparable families of subsets of an n-element set have their first two families…
- op_1370_small_pair_boundFor three nonempty strongly incomparable families on Fin n with n at least three, if the last family is uncomplemented and the first two…
- op_1370_low_vcdim_others_boundFor at least three nonempty mutually strongly incomparable families of subsets of Fin n, with n at least three, suppose one designated…
- op_1370_uncomplemented_strongly_incomparable_upper_boundTheorem 1.7 of arXiv:2611.12199: for all natural numbers
nandt, if𝒜 : Fin t → Finset (Finset (Fin n))is a family such that each… - hilton_strong_incomparability_matrixFor every natural number n there are a field K, a matrix L over K with rows indexed by the subsets of Fin n and 2^(n-1) columns, and a…
- op_1370_uncomplemented_strongly_incomparable_lower_boundLower bound in Proposition 4.2 of arXiv:2611.12199: for all integers
n ≥ 3and3 ≤ t ≤ n, there exists… - op_1370_case_n3_t3Base case
n = 3, t = 3of Conjecture 4.3 of arXiv:2611.12199 (OP-1370): if𝒜 : Fin 3 → Finset (Finset (Fin 3))is a family such that… - is_uncomplementedA family of subsets of a finite set is uncomplemented if no set and its complement both belong to the family.
- strongly_incomparableAn indexed family of finset families
𝒜 : ι → Finset (Finset α)is strongly incomparable if for alli j : ιwithi ≠ j, for all… - op_1370_shattered_capacityFor set families B, C and D on a finite ground set V, assume each member of C is incomparable with every member of B, no member of D…
- op_1370_incomparable_strict_shatteringThe union of two nonempty mutually strongly incomparable finite set families shatters strictly more sets than it contains.
- op_1370_incomparable_two_sets_card_boundOn an n-element ground set with n at least three, let A and B be incomparable subsets, and let F be an uncomplemented family every member…
- op_1370_small_family_shatterer_uncomplementedIf a family of subsets of Fin n has fewer than 2^ceil(n/2) members, then its family of shattered sets contains no complementary pair.
- op_1370_uncomplemented_shatterer_others_boundFor at least three nonempty mutually strongly incomparable families on Fin n, with n at least three, suppose a designated family is…
- op_1370_pair_shatter_surplus_counterexampleThere are three families indexed by Fin 3 of subsets of Fin 6, each with nine sets, which are nonempty, uncomplemented, and mutually…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2611.12199 — Hilton's Conjecture on Uncomplemented Incomparable Families
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.