Non-redundant Independence Atoms

Non-redundant Independence Atoms

arXiv:2611.05568v1 [math.CO] 3 Nov 2026

Attila Sali HUN-REN Alfréd Rényi Institute of Mathematics and Department of Computer Science, BUTE Jun Yan∗ Faculty of Mathematics, University of Waterloo November 5, 2026

Abstract Independence atom is a key concept in relational database theory. In the present paper, we prove that the maximum possible size of
a non-redundant set of independence atoms on n n attributes is asymptotically (1 + o(1)) ⌊n/2⌋ . It turns out that this problem is closely related to two extremal set theory problems, the Katona-Tarján question on “V”-free families of subsets of [n] for the lower bound, and Kleitman’s bound on union-free families for the upper bound.

1

Introduction

Independence and conditional independence are fundamental concepts in areas as diverse as artificial intelligence, probability theory, social choice theory, and statistics [Daw79, Hal17, Pea88]. In the present paper we investigate independence atoms, which are specializations of the logic concept introduced in [GV13] and studied in detail in [KLV13]. Let {A1 , . . . , An } be a set of n attributes. Given disjoint X, Y ⊂ {A1 , . . . , An } and an n-ary relation r over {A1 , . . . , An }, we say that r satisfies the independence atom X ⊥ Y if for all tuples t1 , t2 ∈ r there is some tuple t ∈ r which matches the values of t1 on all coordinates in X and matches the values of t2 on all coordinates in Y . More intuitively, if a relation r satisfies X ⊥ Y , then the occurrences of X-values are independent of the occurrences of Y -values. As with any other integrity constraint, it is natural to investigate the implication problem for independence atoms. If Σ is a collection of independence atoms and σ is an independence atom, then Σ implies σ, denoted by Σ |= σ, if any n-ary (database) relation r that satisfies every independence atom in Σ also satisfies σ. The implication problem was axiomatized by Kontinen, Link, and Väänänen [KLV13] (see Theorem 2.3). They also provided a divide-and-conquer algorithm that when given (Σ, σ), decides in polynomial time whether Σ |= σ. Our focus in this paper is the following extremal combinatorial problem raised by Link [Lin24]. What is the maximum possible size of a non-redundant set of independence atoms on n attributes? A set Σ of independence atoms is non-redundant if, for each atom σ ∈ Σ, Σ \ {σ} ̸|= σ. Equivalently, no atom in Σ can be derived from the other atoms. Let f (n) be the largest size of a non-redundant set of independence atoms on n attributes. In an undergraduate research paper, Alland, Sali, and Wu [ASW25] showed that  Θ

2n √ n

 =

n−1 X i=1

i ⌈i/2⌉



⌊2n/3⌋

≤ f (n) ≤ 2



n ⌊2n/3⌋



∗ Was supported by ERC Advanced Grant 883810 during part of this project.

1

 =Θ

3n √ n

 .

Our main result determines f (n) asymptotically.
n Theorem 1.1. f (n) = (1 + o(1)) ⌊n/2⌋ . More precisely,  1+

2 +o n

         √ 1 n π 1 n ≤ f (n) ≤ 1 + √ + O . n ⌊n/2⌋ n ⌊n/2⌋ 2n

We also establish connections between this problem and two other problems in extremal set theory. A family F of subsets of [n] is called “V”-free if there does not exist distinct A, B, C ∈ F with A ⊂ B and A ⊂ C. Let g(n) be the maximum size of a “V”-free family of subsets of [n], and let g2 (n) be the maximum size of a “V”-free family of subsets of [n] that contains only sets
of size ⌊n/2⌋ and n ⌊n/2⌋ + 1. Katona and Tarján [KT83] proved that g2 (n) ≤ g(n) ≤ (1 + 2/n) ⌊n/2⌋ , and also provided a construction originating from Graham and
Sloane’s work on constant weight codes [GS80], which n proved that g2 (n) ≥ (1 + 1/n + o(1/n)) ⌊n/2⌋ . A family F of subsets of [n] is called union-free if there does not exist distinct A, B, C ∈ F with A = B ∪ C. Let h(n) be the maximum size
of a union-free family of subsets of [n]. Kleitman [Kle76] √ n proved that h(n) ≤ (1 + O(1/ n)) ⌊n/2⌋ . While it is clear that h(n) ≥ g(n), as far as we can tell it is √ not known whether the correct second-order term for h(n) should be Θ(1/n), Θ(1/ n), or something in between. We will prove that   n g2 (n) ≤ f (n) ≤ h(n) + O , ⌈n/3⌉ so lower bounds on g2 (n) and upper bounds on h(n) imply corresponding bounds on f (n) as well. Like for h(n), it remains open what the asymptotically correct second-order term of f (n) should be. The rest of the paper is organized as follows. In Section 2, we provide more background on relational database and independence atoms, and record Kontinen, Link, and Väänänen’s [KLV13] axiomatization of the implication problem, as well as their algorithm for deciding whether Σ |= σ. In Section 3, we use the algorithmic characterization of implication problem and the LYM inequality to prove the upper bound for f (n). We also establish the connection between f (n) and h(n), which then gives an asymptotically equivalent upper bound using Kleitman’s bound on h(n). In Section 4, we provide two lower bounds for f (n). The first one is recursive and improves the lower bound of Alland, Sali, and Wu [ASW25] by a linear factor in n. The second one is better asymptotically, and uses an improved bound on g2 (n) recently obtained by Zhan, Lu, and Zhao [ZLZ26].

2

Database background

In this section, we first summarize basic concepts from the relational model of databases, then introduce the syntax and semantics of independence atoms, and finally summarize the results from [KLV13] that are needed in our proofs. A relation schema is a finite set R = {A1 , A2 , . . . , An } of n different attributes, where for each Ai , dom(Ai ) is a set of possible values that can be taken for the i-th attribute. As an example, the attribute A1 may be eye color, and dom(A1 ) is then the set of possible eye colors. A tuple over R is an element in dom(A1 ) × dom(A2 ) × · · · × dom(An ), and a relation r over R is a finite set of tuples Q over R, or equivalently a subset of dom(A1 ) × dom(A2 ) × · · · × dom(An ). For X ⊂ [n],Q let t(X) ∈ i∈X dom(Ai ) denote the restriction of the tuple t to X, and let r(X) = {t(X) : t ∈ r} ⊂ i∈X dom(Ai ) denote the restriction of the relation r to X. Definition 2.1. Let R be a relation schema with n attributes. Let X, Y be disjoint subsets of [n]. A relation r over R satisfies the independence atom X ⊥ Y if for all tuples t1 , t2 ∈ r, there exists a tuple t ∈ r such that t(X) = t1 (X) and t(Y ) = t2 (Y ).

2

In other words, if a relation r satisfies X ⊥ Y , then the occurrences of X-values are independent of the occurrences of Y -values, in the sense that r(X ∪ Y ) = r(X) × r(Y ). Definition 2.2. Let Σ be a collection of independence atoms on n attributes, and let σ be an independence atom on the same set of attributes. We say that Σ implies σ, denoted by Σ |= σ, if any relation r over this set of attributes that satisfies every independence atom in Σ also satisfies σ. The implication problem was axiomatized by Kontinen, Link, and Väänänen [KLV13] as follows. Theorem 2.3 ([KLV13, Theorem 1]). The following four axioms form a sound and complete axiom system for the implication of independence atoms. That is, Σ |= σ if and only if σ can be derived from the atoms in Σ using the following four axioms. A1 |= X ⊥ ∅ (trivial independence, T ). A2 X ⊥ Y |= Y ⊥ X (symmetry, S). A3 X ⊥ (Y ∪ Z) |= X ⊥ Y (decomposition, D). A4 X ⊥ Y ∧ (X ∪ Y ) ⊥ Z |= X ⊥ (Y ∪ Z) (exchange, E). That is, Σ |= σ iff σ has a finite derivation from Σ using the rules above. We will need the following theorem, which is a straightforward corollary of the algorithmic characterization of implications of independence atoms proven in [KLV13, Theorem 2]. For a set of independence atoms Σ and an atom X ⊥ Y , let Σ[X ∪ Y ] denote the restriction of Σ to X ∪ Y , that is, Σ[X ∪ Y ] = {(U ∩ (X ∪ Y )) ⊥ (V ∩ (X ∪ Y )) : U ⊥ V ∈ Σ} Theorem 2.4. Let Σ be a set of independence atoms and let σ = X ⊥ Y be an atom. Then Σ |= σ if and only if one of the following holds. 1. σ is trivial, i.e., X = ∅ or Y = ∅. 2. X ⊥ Y ∈ Σ or Y ⊥ X ∈ Σ. 3. There exists a non-trivial U ⊥ V ∈ Σ[X ∪ Y ] satisfying U ∪ V = X ∪ Y with the following property. Let Q = U ∩ X, R = U ∩ Y , S = V ∩ X, and T = V ∩ Y , so that U = Q ∪ R, V = S ∪ T , X = Q ∪ S, and Y = R ∪ T . Then, both Σ[X ∪ Y ] |= Q ⊥ R and Σ[X ∪ Y ] |= S ⊥ T hold.

3

Upper Bound

In this section, we prove the upper bound part of Theorem 1.1. We begin by defining minimal non-redundant sets of independence atoms, and studying their properties. Definition 3.1. A non-redundant set Σ of independence atoms is called containment minimal or simply minimal, if for every atom A ⊥ B ∈ Σ and all subsets A′ ⊂ A and B ′ ⊂ B satisfying A′ ∪ B ′ ̸= A ∪ B, we have Σ \ {A ⊥ B} |= A′ ⊥ B ′ . Lemma 3.2. Suppose Σ is a non-redundant set of independence atoms. Let A ⊥ B ∈ Σ, let A′ ⊂ A, and let B ′ ⊂ B. If Σ \ {A ⊥ B} ̸|= A′ ⊥ B ′ , then Σ∗ := (Σ \ {A ⊥ B}) ∪ {A′ ⊥ B ′ } is non-redundant. Proof. Suppose for a contradiction that Σ∗ is redundant. Then, we have the following two cases. Case I. Σ∗ \ {A′ ⊥ B ′ } |= A′ ⊥ B ′ . This is impossible as Σ∗ \ {A′ ⊥ B ′ } = Σ \ {A ⊥ B}, and we have Σ \ {A ⊥ B} ̸|= A′ ⊥ B ′ from the assumption. Case II. There exists X ⊥ Y ∈ Σ∗ with X ⊥ Y = ̸ A′ ⊥ B ′ , such that Σ∗ \ {X ⊥ Y } |= X ⊥ Y . ′ ′ Note that X ⊥ Y ∈ Σ as well, and A ⊥ B |= A ⊥ B by A2 and A3, so by replacing the occurrences of A′ ⊥ B ′ in the derivation of Σ∗ \ {X ⊥ Y } |= X ⊥ Y with A ⊥ B, we get a derivation of Σ \ {X ⊥ Y } |= X ⊥ Y . This contradicts that Σ is non-redundant. 3

Note that by repeated applications of Lemma 3.2, for any non-redundant set Σ of independence atoms, there is a minimal non-redundant set Σ′ of the same size. Therefore, when studying f (n), the maximum size of a non-redundant set, we can often assume it is minimal. The following result shows that the underlying sets corresponding to independence atoms in a minimal non-redundant set are pairwise distinct. Lemma 3.3. Let Σ be a minimal non-redundant set of independence atoms on [n]. Then, the map ϕ : Σ → P([n]) defined by ϕ(A ⊥ B) = A ∪ B is injective. Proof. Suppose for a contradiction that there exist distinct X ⊥ Y and U ⊥ V in Σ, such that ϕ(X ⊥ Y ) = X ∪ Y = U ∪ V = ϕ(U ⊥ V ). Let Q = X ∩ U , R = Y ∩ U , S = X ∩ V , and T = Y ∩ V . Let Σ′ = Σ \ {X ⊥ Y }, noting that Σ′ |= U ⊥ V = (Q ∪ R) ⊥ (S ∪ T ). We have two cases. Case I. At least one of Σ′ ̸|= Q ⊥ R and Σ′ ̸|= S ⊥ T holds. Without loss of generality, assume ′ Σ ̸|= Q ⊥ R. This contradicts the minimality of Σ as Q ⊂ X and R ⊂ Y . Case II. Σ′ |= Q ⊥ R and Σ′ |= S ⊥ T . Then, combining S ⊥ T and U ⊥ V = (Q ∪ R) ⊥ (S ∪ T ) gives S ⊥ (Q ∪ R ∪ T ) by A2 and A4, then A3 gives S ⊥ (R ∪ T ). Similarly, combining Q ⊥ R and (Q ∪ R) ⊥ (S ∪ T ) gives Q ⊥ (R ∪ S ∪ T ) by A4. Finally, combining Q ⊥ (R ∪ S ∪ T ) and S ⊥ (R ∪ T ) gives (Q ∪ S) ⊥ (R ∪ T ) = X ⊥ Y by A2 and A4. Therefore, Σ′ |= X ⊥ Y , contradicting that Σ is non-redundant. The next result gives a useful characterization of non-redundancy that will be used in both the upper bound and lower bound proofs of Theorem 1.1. Note that in the reverse direction, Σ is not necessarily minimal non-redundant. Lemma 3.4. If Σ is a minimal non-redundant set of independence atoms, then the following holds. For all distinct atoms A ⊥ B and A′ ⊥ B ′ in Σ, if A′ ∪ B ′ ⊂ A ∪ B, then either A′ ∪ B ′ ⊂ A or A′ ∪ B ′ ⊂ B. Conversely, if this condition holds and Σ contains no trivial atoms, then Σ is non-redundant. Proof. First suppose that Σ is a minimal non-redundant set, and both (A′ ∪ B ′ ) ∩ A ̸= ∅ and (A′ ∪ B ′ ) ∩ B ̸= ∅ hold. Let Q = A′ ∩ A, R = B ′ ∩ A, S = A′ ∩ B, and T = B ′ ∩ B. Set U = Q ∪ R and V = S ∪ T , so that A ⊥ B |= U ⊥ V by A3. Let Σ′ = Σ \ (A′ ⊥ B ′ ). Then, U ⊥ V is a non-trivial atom in Σ′ [A′ ∪ B ′ ]. Since Q, S ⊂ A′ and R, T ⊂ B ′ , the definition of minimality implies that Σ \ {A′ ⊥ B ′ } |= Q ⊥ R and Σ \ {A′ ⊥ B ′ } |= S ⊥ T . Thus, Theorem 2.4 applies to show that Σ′ = Σ \ {A′ ⊥ B ′ } |= A′ ⊥ B ′ , contradicting the minimality of Σ. On the other hand, assume now that Σ contains no trivial atoms, and for all distinct A ⊥ B and A′ ⊥ B ′ in Σ satisfying A′ ∪ B ′ ⊂ A ∪ B, we have either A′ ∪ B ′ ⊂ A or A′ ∪ B ′ ⊂ B. Suppose for a contradiction that Σ is redundant, then there exists a non-trivial A ⊥ B ∈ Σ such that Σ′ := Σ \ {A ⊥ B} |= A ⊥ B. If B ⊥ A ∈ Σ, then B ∪ A ⊂ A ∪ B, but B ∪ A is contained in neither A nor B, contradicting the assumption. Thus, by Theorem 2.4, we can find a non-trivial U ⊥ V ∈ Σ′ [A∪B] with U ∪V = A∪B, so that with Q = U ∩A, R = U ∩B, S = V ∩A, and T = V ∩B, we have both Σ′ [A ∪ B] |= Q ⊥ R and Σ′ [A ∪ B] |= S ⊥ T . However, since U ⊥ V ∈ Σ′ [A ∪ B], there exists U ′ ⊥ V ′ ∈ Σ′ ⊂ Σ such that U = U ′ ∩ (A ∪ B) and V = V ′ ∩ (A ∪ B). In particular, U ∪ V = A ∪ B ⊂ U ′ ∪ V ′ , so from the assumption, either A ∪ B ⊂ U ′ or A ∪ B ⊂ V ′ . This implies that either U = ∅ or V = ∅, contradicting that U ⊥ V is a non-trivial atom in Σ′ [A ∪ B]. Theorem 3.5. For all n ≥ 6,  f (n) ≤

       √ ⌈n/2⌉  n 1 X n+1 π 1 n . + = 1+ √ +O ⌊n/2⌋ n + 1 t=3 t n ⌊n/2⌋ 2n

Proof. Let Σ be a maximum non-redundant system on [n]. By repeatedly applying Lemma 3.2 to Σ, we may assume that Σ is minimal. Then, by Lemma 3.3, ϕ : Σ → P([n]) given by ϕ(A ⊥ B) = A ∪ B is injective. In particular, for any S ∈ ϕ(Σ), there is a unique atom AS ⊥ BS ∈ Σ with AS ∪ BS = S. Let ak be the number of atoms A ⊥ B in Σ with |A| + |B| = k. 4

Fix any 2 ≤ t ≤ n − 1. Let It be the set of pairs (S, T ) such that S ∈ ϕ(Σ), T ⊊ S, |T | = t, and T ∩ AS , T ∩ BS ̸= ∅. By Lemma 3.4, if (S, T ) ∈ It , then T ̸∈ ϕ(Σ). On the one hand, for every |=
S ∈
ϕ(Σ)
with
|S| = s,
if |ASs−1
a and |BS | = b, with a + b = s, then Pt−1
b
there are i=1 ai t−i = st − at − bt ≥ st − s−1 = t t−1 ways to pick T . On the other hand, for a fixed T with |T | = t, if (S1 , T ), (S2 , T ) ∈ It , then we cannot have S1 ⊂ S2 . Indeed, otherwise we have T ⊂ S1 ⊂ S2 , and so S1 ∩ AS2 , S1 ∩ BS2 ̸= ∅. By Lemma 3.4, this implies that S1 ̸∈ ϕ(Σ), a contradiction. Therefore, for a fixed T , the set of S with (S, T ) ∈ It form an antichain in the poset {R : T ⊂ R}. Thus, by the LYM inequality, X

1

S:(S,T )∈It

n−t |S|−t

≤ 1.

Summing over all |T | = t not in ϕ(Σ), and combining the two previous paragraphs, we get

  s−1 n n X X X X X as s−1 1 n t−1 t−1


= ≤ ≤ − at . n−t n−t n−t t s−t s−t |S|−t s=t+1 s=t+1 T ̸∈ϕ(Σ):|T |=t S:(S,T )∈It

S∈ϕ(Σ):|S|=s

After simplification, this gives n X as 1
bt := n ≤ . t s s s=t
Set bn+1 = 0. Note that at = (bt − bt+1 )t nt for every 2 ≤ t ≤ n, so n X

n X

  n t t=2 t=2       X n n n n bt t = 2b2 + − (t − 1) . t t−1 2 t=3

|Σ| =

at =

(bt − bt+1 )t

n Using bt ≤ 1/t, and that t nt − (t − 1) t−1 is only positive when t ≤ ⌈n/2⌉, we get |Σ| = 2b2

≤

  X     n n n n + bt t − (t − 1) 2 t t−1 t=3

  ⌈n/2⌉ X n t − 1  n  n + − t t t−1 2 t=3

  ⌈n/2⌉ X n ⌈n/2⌉ X  n  ⌈n/2⌉ X n = + − + 2 t t−1 t=3 t=3 t=3
  ⌈n/2⌉ n X t−1 n = + t ⌈n/2⌉ t=3

n t−1

t

       √ ⌈n/2⌉  n 1 X n+1 π 1 n + = 1+ √ +O , ⌊n/2⌋ n + 1 t=3 t n ⌊n/2⌋ 2n

 = as required.

As mentioned in the introduction, Kleitman proved the following upper bound on h(n), the maximum size of a union-free family of subsets of [n].

5

Theorem 3.6 ([Kle76]). Let h(n) be the size of the largest family F ⊂ [n], such that there does not exist distinct A, B, C ∈ F satisfying A = B ∪ C. Then,     n 2n n h(n) ≤ + +O . ⌊n/2⌋ n+1 ⌊n/4⌋ The following result shows that h(n) is essentially an upper bound on f (n), and in particular recovers asymptotically the same upper bound as Theorem 3.5. An improved upper bound on h(n) could also lead to a better upper bound on f (n). 
 n Proposition 3.7. f (n) ≤ h(n) + O ⌈n/3⌉ . Proof. Let Σ be a maximum non-redundant set of independence atoms on [n]. By repeated applications of Lemma 3.2, we may assume Σ is minimal. By Lemma 3.3, the map ϕ : Σ → P([n]) defined by ϕ(A ⊥ B) = A ∪ B is injective. Let F = ϕ(Σ), and note that |F| = |Σ| by injectivity. We claim that there are no distinct sets X, Y, Z in F with X = Y ∪ Z, and Y ∩ Z ̸= ∅. Suppose for a contradiction that such X, Y, Z exist, and suppose A ⊥ B is the atom in Σ satisfying ϕ(A ⊥ B) = X. Then, by Lemma 3.4, Y ⊂ A or Y ⊂ B, and Z ⊂ A or Z ⊂ B. Without loss of generality, suppose Y ⊂ A. Since Y ∩ Z = ̸ ∅ and A ∩ B = ∅, we must have Z ⊂ A as well. However, this implies that X = Y ∪ Z ⊂ A, a contradiction. S  ⌊2n/3⌋−1 [n]
Now let F ′ = F ∩ . If there exist distinct X, Y, Z in F ′ with X = Y ∪ Z, then we k=⌈n/3⌉ k must have Y ∩ Z = ∅ from above. However, this implies that 2 ⌈n/3⌉ ≤ |Y | + |Z| = |X| ≤ ⌊2n/3⌋ − 1, a contradiction. Thus, |F ′ | ≤ h(n), and so ′

⌈n/3⌉−1 

f (n) = |Σ| = |F| ≤ |F | +

X

k=0

 n + k

n X k=⌊2n/3⌋

    n n ≤ h(n) + O , k ⌈n/3⌉

as required.

4

Lower Bound

In this section we give two different lower bound constructions. The first one is a recursive partition-type construction as follows. Theorem 4.1. Let n = a+b, with a ≥ b ≥ 1. Let Σa be a non-redundant set on [a], and let Σb be a nonredundant set on [a + 1, n]. Let S = {A ⊥ B : ∅ = ̸ A ⊂ [a], ∅ ̸= B ⊂ [a + 1, n] with |A ∪ B| = ⌈n/2⌉}. Then, the following set is non-redundant. Σ := Σa ∪ Σb ∪ S. Consequently,  f (n) ≥ max

a+b=n a≥b≥1



     n a b f (a) + f (b) + − − . ⌈n/2⌉ ⌈n/2⌉ ⌈n/2⌉

(1)

Proof. For an atom X ⊥ Y in Σa , the projection of every atom in Σ \ Σa onto X ∪ Y is trivial, so X ⊥ Y cannot be derived from Σ \ {X ⊥ Y } by Theorem 2.4. Similarly, no atom in Σb can be derived from other atoms in Σ. Now let A ⊥ B ∈ S. For any atom in Σa ∪ Σb , its projection onto A ∪ B is trivial. For every atom A′ ⊥ B ′ ∈ S \ {A ⊥ B}, its projection onto A ∪ B is (A′ ∩ A) ⊥ (B ′ ∩ B). However, since |A ∪ B| = |A′ ∪ B ′ |, (A′ ∩ A) ∪ (B ′ ∩ B) ̸= A ∪ B, so by Theorem 2.4, A ⊥ B cannot be derived from Σ \ {A ⊥ B}. Thus, Σ is non-redundant. 6

We remark that the lower bound in [ASW25] is the special case when b = 1 is always chosen in (1), Pn−1 i
which leads to their lower bound f (n) ≥ i=1 ⌈i/2⌉ . They also conjectured that f (5) = 12, however this turns out to be incorrect, as Theorem 4.1 implies the following when we use a = 3 and b = 2 in (1). Corollary 4.2. f (5) ≥ 13.



Proof. f (5) ≥ f (3) + f (2) + 32 21 + 31 22 = 3 + 1 + 6 + 3 = 13. A non-redundant set of atoms is {1 ⊥ 2, 2 ⊥ 3, 1 ⊥ 3} ∪ {4 ⊥ 5} ∪ {12 ⊥ 4, 13 ⊥ 4, 23 ⊥ 4, 12 ⊥ 5, 13 ⊥ 5, 23 ⊥ 5} ∪ {1 ⊥ 45, 2 ⊥ 45, 3 ⊥ 45}. Define a function fe(n) by fe(n) = f (n) for n = 1, 2, 3, 4, and let fe(n) satisfy the recurrence (1) with equality for n ≥ 5. Then, Theorem 4.1 implies that f (n) ≥ fe(n) for every n. We used ChatGPT [Cha26] to solve this recurrence and obtain the following lower bound on f (n). In particular, it turns out that for n ≥ 8, the optimal splits are (a, b) = (n − 3, 3) if n is divisible by 4, (a, b) = (n − 1, 1) if n is congruent to 1 mod 4, (a, b) = (n−2, 2) and (n−3, 3) if n is congruent to 2 mod 4, and (a, b) = (n−1, 1) and (n − 2, 2) if n is congruent to 3 mod 4. Proposition 4.3. Let fe(n) be defined using the recurrence (1) with equality. Then, f (n) ≥ fe(n) =

n−1 X j=1

 j k j k j n n + + − 2, ⌊j/2⌋ 2 4

n ≥ 5.

Asymptotically,      2 1 n   1 + + O ,  3n n2 ⌊n/2⌋ e     f (n) ≥ f (n) =   1 4 n   1+ +O , 3n n2 ⌊n/2⌋

if n is even, if n is odd.

Our next result establishes a connection between f (n) and g2 (n), the size of a maximum “V”-free family of subsets of [n] that contains only sets of size ⌊n/2⌋ and ⌊n/2⌋ + 1. Proposition 4.4. f (n) ≥ g2 (n). Proof. Let F ′ be a maximum “V”-free family of subsets of [n] that only contains sets of size ⌊n/2⌋ and ⌊n/2⌋ + 1. Let F = {F c : F ∈ F ′ }, then |F| = |F ′ | and F contains only sets of size ⌈n/2⌉ and ⌈n/2⌉ − 1. Let F1 be the sets of size ⌈n/2⌉ in F and let A = F \ F1 . Since F ′ is “V”-free, every F ∈ F1 has at most one A ∈ A such that A ⊂ F . Let Σ consist of the following atoms. 1. For every F ∈ F1 that has a unique A ∈ A such that A ⊂ F , add A ⊥ (F \ A) to Σ. For every F ∈ F1 with no A ∈ A satisfying A ⊂ F , pick f ∈ F arbitrarily and add {f } ⊥ (F \ {f }) to Σ. 2. For every A ∈ A, pick a ∈ A arbitrarily, and add {a} ⊥ (A \ {a}) to Σ. Then, Σ is non-redundant by Lemma 3.4, so f (n) ≥ |F | = |F ′ | = g2 (n). Katona and Tarján [KT83, Theorem 6] studied the maximum size of “V”-free families and proved that         1 1 n 2 n 1+ +O ≤ g(n) ≤ 1 + . n n2 ⌊n/2⌋ n ⌊n/2⌋ Their lower bound construction for g(n) uses only sets of size ⌊n/2⌋ or ⌊n/2⌋ + 1, so the same lower bound holds for g2 (n). This implies that the lower bound of Proposition 4.4 is better for odd n than the partition-type one. Let us note, that the family of 13 subsets of [5] without a “V ” constructed in [KT83] corresponds to the non-redundant family of 13 independence atoms of Corollary 4.2. Recently, Zhan, Lu, and Zhao [ZLZ26] obtained the correct second-order term in for g(n). 7

Theorem 4.5 ([ZLZ26, Theorem 1.4]).  g(n) =

1+

2 +o n

    1 n . n ⌊n/2⌋

Again, their new lower bound construction for g(n) uses only sets of size ⌊n/2⌋ or ⌊n/2⌋ + 1, so the same bound also holds for g2 (n). By Proposition 4.4, this immediately gives the following lower bound on f (n) as a corollary, which for large n is asymptotically better than the bound from the recursive partition-type construction above. Corollary 4.6.  f (n) ≥

2 1+ +o n

    1 n . n ⌊n/2⌋

n Finally, we note that since Katona and Tarján proved that g2 (n) ≤ g(n) ≤ (1 + 2/n) ⌊n/2⌋ , this is essentially the best lower bound on f (n) that can be obtained using Proposition 4.4.

5

AI statements

Proposition 4.3 was obtained using ChatGPT. Their proofs are properly validated and are included in [Cha26].

References [ASW25] Lucas Alland, Attila Sali, and Nicole Wu. Non-redundant systems of independence atoms in relational databases. In Proceedings of the 28th International Multiconference, Volume N, pages 27–29. 2025. https://matcos.iam.upr.si/en/resources/files//published-material/ is2025volume-n.pdf. [Cha26]

ChatGPT. An exact recurrence and asymptotics for f (n). https://users.renyi.hu/ ~sali/indep/correctedaiproof.pdf, 2026.

[Daw79] Alexander P. Dawid. Conditional independence in statistical theory. Journal of the Royal Statistical Society, Series B (Methodological), 41(1):1–31, 1979. [GS80]

Ronald L. Graham and Neil J. A. Sloane. Lower bounds for constant weight codes. IEEE Transactions on Information Theory, 26(1):37–43, 1980.

[GV13]

Erich Grädel and Jouko Väänänen. Dependence and independence. Studia Logica, An International Journal for Symbolic Logic, 101(2):399–410, 2013.

[Hal17]

Joseph Y. Halpern. Reasoning about uncertainty. MIT Press, 2017.

[Kle76]

Daniel J. Kleitman. Extremal properties of collections of subsets containing no two sets and their union. Journal of Combinatorial Theory, Series A, 20(3):390–392, 1976.

[KLV13] Juha Kontinen, Sebastian Link, and Jouko Väänänen. Independence in database relations. In Logic, Language, Information, and Computation, pages 179–193. Springer, 2013. [KT83]

Gyula O. H. Katona and Tamás G. Tarján. Extremal problems with excluded subgraphs in the n-cube. In Graph theory (Lagów, 1981), pages 84–93. Springer, 1983.

[Lin24]

Sebastian Link. Personal communication, 2024.

[Pea88]

Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988. 8

[ZLZ26] Yiyan Zhan, Mei Lu, and Xiamiao Zhao. The second-order term for the largest r-fork-free families. arXiv:2609.30336, 2026.

9

Related documents

• On the Stability of the Independence Number in Random Distance Graphs#986522
• On the OpenAI whole-cube bound#1061955
• The Hidden Topology of Network Entanglement#1144428
• Optimal support and condensation in random allocations#1051247
• Counting Admissible Sets of Integers: A Proof of the Erdős--Nicolas--Sárközy Conjecture#1457526