Linea ly dependen ec o ial decomposi ion o
clu e s
J. Ma ´ı-Fa ´e⋆
Depa amen de Ma em`a ica Aplicada IV, Uni e si a Poli `ecnica de Ca alunya,
Ba celonaTech, Ba celona, Spain. [email p o ec ed]
Abs ac . This pape deals wi h he ques ion o comple ing a mono one inc eas-
ing amily o subse s Γo a ini e se Ω o ob ain he linea ly dependen subse s
o a amily o ec o s o a ec o space. Speci ically, we demons a e ha such ec-
o ial comple ions o he amily o subse s Γexis and, in addi ion, we show ha
he minimal ec o ial comple ions o he amily Γp o ide a decomposi ion o he
clu e Λo he inclusion-minimal elemen s o Γ. The compu a ion o such ec o ial
decomposi ion o clu e s is also discussed in some cases.
Key wo ds: Clu e , An ichain, Hype g aph, Ma oid, Decomposi ion.
1 In oduc ion
Amono one inc easing amily o subse s Γo a ini e se Ωis a collec ion
o subse s o Ωsuch ha any supe se o a se in he amily Γmus be in
Γ. All he inclusion-minimal elemen s o Γde e mine a clu e Λ, ha is, a
collec ion o subse s o Ωnone o which is a p ope subse o ano he . Clu e s
a e also known as an ichains,Spe ne sys ems o simple hype g aphs.
A wide a ie y o examples o mono one inc easing amilies exis , among
which we ind he collec ion o he linea ly dependen subse s o ec o s in a
ec o space. We say ha a clu e Λis LD- ec o ial i i s elemen s a e he
inclusion-minimal linea ly dependen subse s o an indexed amily o ec o s
o a ec o space. In o he wo ds, he LD- ec o ial clu e s a e exac ely hose
co esponding o he se o ci cui s o ep esen able ma oids.
In some cases i is con enien o use clu e s ha a e ei he LD- ec o ial
o a e closed o be LD- ec o ial. Examples o his si ua ion can be ound in
he con ex o sec e -sha ing schemes [3,5], o in he amewo k o algeb aic
combina o ics and commu a i e algeb a [1,6]. Fo ins ance, in he con ex
o sec e -sha ing schemes, he LD- ec o ial clu e s become a c ucial issue
⋆Resea ch suppo ed by he Minis e io de Educaci´on y Ciencia (Spain) and he Eu opean
Regional De elopmen Fund unde p ojec MTM2011-28800-C02-01.
408 J. Ma ´ı-Fa ´e
o p o iding gene al bounds on he op imal in o ma ion a e o he scheme,
while in he amewo k o algeb aic combina o ics and commu a i e algeb a,
hey a e use ul o con olling ce ain a i hme ic p ope ies o ei he monomial
ideals o he ace ings o simplicial complexes.
In gene al, a clu e is a om being LD- ec o ial. The e o e i is o in e es
o de e mine how i can be ans o med in o an LD- ec o ial clu e . This
pape deals wi h his issue; ha is, wi h he ques ion o inding LD- ec o ial
comple ions o a clu e . Speci ically, he goal o his pape is o p o e ha
hese comple ions exis and ha he minimal ones p o ide a decomposi ion
o he clu e .
The ou line o he pape is as ollows. In Sec ion 2 we ecall some de ini ions
and basic ac s abou clu e s and p esen he p oblem o he LD- ec o ial
comple ion o a clu e . Ou main esul s a e ga he ed in Sec ion 3; namely,
we p esen wo heo ems conce ning LD- ec o ial decomposi ion o clu e s
(Theo em 1 and Theo em 2). Finally, Sec ion 4 is de o ed o analyzing he
compu a ion o such decomposi ions (P oposi ion 1). Due o limi a ions o
space, he p oo s a e omi ed.
2 LD- ec o ial clu e s and LD- ec o ial comple ions
In his sec ion we p esen he de ini ions and basic ac s conce ning amilies
o subse s, clu e s and LD- ec o ial clu e s ha a e used in he pape .
Le Ωbe a ini e se . A amily o subse s Γo Ωis mono one inc easing i
any supe se o a se in Γmus be in Γ; ha is, i A∈Γand A⊆A′⊆Ω,
hen A′∈Γ. A clu e o Ωis a collec ion o subse s Λo Ω, none o which is
a p ope subse o ano he ; ha is, i A, A′∈Λand A⊆A′ hen A=A′.
Obse e ha i Γis a mono one inc easing amily o subse s o Ω, hen
he collec ion min(Γ) o i s inclusion-minimal elemen s is a clu e ; while i
Λis a clu e on Ω, hen he amily Λ+={A⊆Ω:A0⊆A o some
A0∈Λ}is a mono one inc easing amily o subse s. Clea ly Γ= (min(Γ))+
and Λ= min $Λ+. So a mono one inc easing amily o subse s Γis de e mined
uniquely by he clu e min(Γ), while a clu e Λis de e mined uniquely by
he mono one inc easing amily Λ+.
Le Λ1, Λ2be wo clu e s on Ω. I is clea ha i Λ1⊆Λ2 hen Λ+
1⊆Λ+
2.
Howe e , he con e se is no ue; ha is, he e exis clu e s wi h Λ16⊆ Λ2
and Λ+
1⊆Λ+
2. Fo ins ance, on he ini e se Ω={1,2,3}, le us conside he
clu e s Λ1={{1,2},{2,3}} and Λ2={{1},{2,3}}. Then Λ16⊆ Λ2, while
Λ+
1={{1,2},{2,3},{1,2,3}} ⊆ {{1},{1,2},{1,3},{2,3},{1,2,3}} =Λ+
2.
This ac leads us o conside a bina y ela ion ≤de ined on he se o
clu e s on Ω. Namely, i Λ1and Λ2a e wo clu e s on Ω, hen we say ha
Λ1≤Λ2i and only i Λ+
1⊆Λ+
2. The ollowing lemma will be used se e al
imes h oughou he pape .
Lemma 1. Le Ωbe a ini e se . The ollowing s a emen s hold:
Linea ly dependen ec o ial decomposi ion o clu e s 409
1. I Λ1, Λ2a e wo clu e s on Ω hen, Λ1≤Λ2i and only i o all A1∈Λ1
he e exis s A2∈Λ2such ha A2⊆A1.
2. The bina y ela ion ≤is a pa ial o de on he se o clu e s o Ω.
The e a e many in e es ing amilies o clu e s ha can be conside ed.
Howe e , because o hei applica ions, we a e in e es ed in hose clu e s
ha a e LD- ec o ial.
Le Ω={x1, . . . , xn}be a ini e se o nelemen s. A mono one inc easing
amily Γo subse s o Ωis said o be an LD- ec o ial amily i he e exis s an
indexed amily o ec o s 1, . . . , no a K- ec o space ( ha can be i= j)
such ha {xi1, . . . , xi } ∈ Γi and only i { i1, . . . , i }is a linea ly dependen
se o ec o s. A clu e Λon Ωis said o be an LD- ec o ial clu e i he
mono one inc easing amily Λ+is an LD- ec o ial amily.
In o he wo ds, a mono one inc easing amily o subse s Γis LD- ec o ial
i Γis he amily o he dependen se s o a ep esen able ma oid Mwi h
g ound se Ω; whe eas a clu e Λis LD- ec o ial i he clu e Λis he se
o ci cui s o a ep esen able ma oid Mwi h g ound se Ω. (The eade is
e e ed o [4,7] o gene al e e ences on ma oid heo y). Obse e ha since
he bina y ela ion ≤is a pa ial o de on he se o clu e s o Ω, i is also a
pa ial o de on he se o LD- ec o ial clu e s, and he e o e ≤is a pa ial
o de on he se o ep esen able ma oids. In ma oid heo y, his is equi alen
o he weak o de (see [4, P oposi ion 7.3.11]).
The e a e clu e s on a ini e se Ω ha a e no LD- ec o ial (in ac , he e
a e ma oids ha a e no ep esen able ma oids). So, a na u al ques ion ha
a ises a his poin is o de e mine how o comple e a clu e Λ o ob ain
an LD- ec o ial clu e . In o de o look o LD- ec o ial comple ions, i is
impo an o ake in o accoun he bina y ela ion ≤ a he han he inclusion
⊆. This is due o he ac ha , as he ollowing example shows, he e exis
clu e s Λsuch ha Λ6⊆ Λ′ o any LD- ec o ial clu e Λ′.
Example 1. Le us conside he clu e Λ={{1,2},{1,3},{2,3,4}} on he
ini e se Ω={1,2,3,4}. Obse e ha ${1,2} ∪ {1,3} {1}={2,3} ⊂
{2,3,4}. Hence i ollows ha Λis no an LD- ec o ial clu e and, mo eo e ,
Λ6⊆ Λ′ o any LD- ec o ial clu e Λ′. Howe e , we ha e ha Λ≤Λ′, whe e
Λ′is he LD- ec o ial clu e Λ′={{1},{2,3,4}} (an LD- ec o ial ealiza ion
o Λ′is gi en by he se o ec o s { 1, 2, 3, 4}whe e 1= (0,0,0), 2=
(1,0,0), 3= (0,1,0) and 4= (0,0,1)). Fu he mo e, i Λ′′ is he clu e on Ω
de ined by Λ′′ ={{1,2},{1,3},{2,3}}, hen we ha e ha Λ≤Λ′′ and ha he
clu e Λ′′ is also an LD- ec o ial clu e (an LD- ec o ial ealiza ion o Λ′′
is gi en by he se o ec o s {w1, w2, w3, w4}whe e w1= (1,1), w2= (1,1),
w3= (1,1) and w4= (0,1)). No ice ha now he clu e Λcan be ob ained
om he LD- ec o ial clu e s Λ′and Λ′′. Indeed, i is easy o check ha
Λ= min A′∪A′′ whe e A′∈Λ′and A′′ ∈Λ′′}. The e o e, he clu e s Λ′and
Λ′′ in some way p o ide a decomposi ion o Λ.
410 J. Ma ´ı-Fa ´e
The abo e example leads us o he ollowing de ini ion. Le Λbe a clu e on
a ini e se Ω. An LD- ec o ial comple ion o he clu e Λis an LD- ec o ial
clu e Λ′on he ini e se Ωsuch ha Λ≤Λ′.
The se o all he LD- ec o ial comple ions o a clu e Λis deno ed by
LD-Vec (Λ). Obse e ha i ∅ ∈ Λ, hen Λ={∅}, and hus LD-Vec (Λ) = ∅.
So, om now on, h oughou he pape we assume ha ∅ 6∈ Λi Λis a clu e .
As shown in he nex sec ion, his assump ion gua an ees ha LD-Vec (Λ)6=∅
o all clu e s and, in addi ion, we demons a e ha sui able clu e s in he
non-emp y se LD-Vec (Λ) p o ide a decomposi ion o he clu e Λin he
same way as in Example 1.
3 Two esul s on LD- ec o ial decomposi ions
The aim o his sec ion is o p esen wo heo e ical esul s conce ning he
“decomposi ion” o a clu e Λin o LD- ec o ial clu e s Λ1, . . . , Λ , (Theo-
em 1 and Theo em 2). The gene al case is conside ed in he i s heo em,
while he second deals wi h hose “decomposi ions” o Λwhose LD- ec o ial
componen s Λ1, . . . , Λ admi ec o ial ealiza ions o e a ixed ield K.
Le Λbe a clu e on a ini e se Ω. Ou i s esul , Theo em 1, s a es
ha he se LD-Vec (Λ) o i s LD- ec o ial comple ions is a non-emp y se
and ha i s minimal elemen s p o ide a decomposi ion o Λ(in he sense ha
he elemen s Ao he clu e Λcan be ob ained om he elemen s Aio i s
minimal LD- ec o ial comple ions Λ1, . . . , Λ ).
Theo em 1. Le Λbe a clu e on a ini e se Ω. Then, LD-Vec (Λ)6=∅and
Λ= min A1∪ · · · ∪ A whe e Ai∈Λiwhe e Λ1, . . . , Λ a e he minimal
elemen s o he pose LD-Vec (Λ),≤o he LD- ec o ial comple ions o Λ.
In pa icula , he clu e Λhas a unique minimal LD- ec o ial comple ion i ,
and only i , Λis an LD- ec o ial clu e .
Obse e ha he p e ious heo em, Theo em 1, deals wi h LD- ec o ial
comple ions and decomposi ions in he case whe e no ield es ic ions a e
assumed. The nex heo em, Theo em 2, s a es ha a simila esul occu s
i we conside only he case in which he ec o spaces o he LD- ec o ial
comple ions a e o e a ixed ield K. Be o e s a ing he heo em, we in oduce
some no a ions.
Le Λbe a clu e on a ini e se Ωand le Kbe a ield. Le us deno e by
LD-Vec K(Λ) he se whose elemen s a e he LD- ec o ial comple ions o Λ
o e K; ha is, he elemen s o LD-Vec K(Λ) a e he LD- ec o ial clu e s Λ′
o e Kwi h Λ≤Λ′. The e o e, LD-Vec (Λ) = SKLD-Vec K(Λ).
The nex heo em s a es ha he se LD-Vec K(Λ) is a non-emp y se and
ha i s minimal elemen s p o ides a decomposi ion o he clu e Λ(in he
sense ha he elemen s o Λcan be ob ained om he elemen s o i s minimal
LD- ec o ial comple ions o e K).
Linea ly dependen ec o ial decomposi ion o clu e s 411
Theo em 2. Le Λbe a clu e on a ini e se Ωand le Kbe a ield. Then,
LD-Vec K(Λ)6=∅and Λ= min A1∪· · ·∪A whe e Ai∈Λiwhe e Λ1, . . . , Λ
a e he minimal elemen s o he pose LD-Vec K(Λ),≤. In pa icula , he
clu e Λhas a unique minimal LD- ec o ial comple ion o e Ki , and only
i , Λis an LD- ec o ial clu e o e K.
4 Compu ing LD- ec o ial decomposi ions
This sec ion is de o ed o he compu a ion o he LD- ec o ial decomposi ion
o clu e s. Fi s we p esen a pa ial esul (P oposi ion 1). A e his, se e al
examples a e gi en in o de o illus a e his p oposi ion (Example 2 and
Example 3). Finally, an example whe e he p oposi ion canno be applied is
analyzed (Example 4).
Ou esul , P oposi ion 1, p o ides a comple e desc ip ion o he minimal
LD- ec o ial comple ion o a clu e Λon a ini e se Ωo size a mos se en.
In o de o s a e his p oposi ion, we need o in oduce wo ans o ma ions
o clu e s, he I- ans o ma ion and he T- ans o ma ion (see [2]).
Le Λbe a clu e on a ini e se Ω. Fo a subse X⊆Ω, we deno e
by IΛ(X) he in e sec ion o he subse s Ain Λcon ained in X, ha is,
IΛ(X) = TAAwhe e A∈Λand A⊆X, ( his in e sec ion is he one in ol ed
in he cha ac e iza ion o he se o ci cui s in connec ed ma oids, see [4,
Theo em 4.3.2]). We say ha a clu e Λ′is an I- ans o ma ion o he clu e
Λi Λ′= min Λ∪{A1∩A2}whe e A1, A2∈Λa e wo di e en subse s wi h
IΛ(A1∪A2)6=∅.
The de ini ion o T- ans o ma ion is mo e in ol ed. Le Λbe a clu e . We
de ine he elemen a y ans o ma ions T(1)(Λ) and T(2)(Λ) o he clu e Λas
he clu e s T(1)(Λ) = min Λ∪(A1∪A2) {x}, whe e A1, A2∈Λa e di e en
and x∈A1∩A2 and T(2)(Λ) = min Λ∪(A1∪A2) IΛ(A1∪A2), whe e
A1, A2∈Λa e di e en }. Since T(1)(Λ) and T(2)(Λ) a e clu e s, we can
apply he elemen a y ans o ma ions again. Hence, o (i1, i2)∈ {1,2}×{1,2}
we can conside he clu e T(i2)(T(i1)(Λ)). A his poin we p oceed in a
ecu si e way. Le ≥2 be a non-nega i e in ege and le (i1, . . . , i )∈
{1,2} be an - uple. Then we de ine he clu e T(i1,...,i )(Λ) by he ecu sion
o mula T(i1,...,i )(Λ) = T(i )(T(i1,...,i −1)(Λ)); ha is, T(i1,...,i )(Λ) is he i
elemen a y ans o ma ion o T(i1,...,i −1)(Λ). We say ha a clu e Λ′is a
T- ans o ma ion o he clu e Λi i is ob ained om Λin his way, ha is,
i Λ′=T(i1,...,i )(Λ) o some - uple (i1, . . . , i ).
P oposi ion 1. Le Λbe a non-LD- ec o ial clu e on a ini e se Ωo size
|Ω|=n≤7. Le Λ′be a clu e such ha Λ≤Λ′. Then he ollowing s a e-
men s hold:
412 J. Ma ´ı-Fa ´e
1. The clu e Λ′is an LD- ec o ial comple ion o Λi , and only i , Λ′is he
unique clu e which can be ob ained om Λ′by applying I- ans o ma ions
o T- ans o ma ions.
2. I he clu e Λ′is a minimal elemen o he pose $LD-Vec (Λ),≤, hen
he e is a mono one inc easing sequence o clu e s Λ=Λ0< Λ1< . . . <
Λ =Λ′such ha o i≥1, ei he Λiis an I- ans o ma ion o Λi−1, o
Λiis a T- ans o ma ion o Λi−1.
We now gi e wo examples o illus a e he abo e p oposi ion.
Example 2. Fi s , le us conside he clu e Λ={{1,2},{1,3},{2,3,4}} on
he ini e se Ω={1,2,3,4}. In his case only wo clu e s a e ob ained by
using o by combining I- ans o ma ions and T- ans o ma ions; namely, he
clu e s Λ1={{1},{2,3,4}} and Λ2={{1,2},{1,3},{2,3}}. The e o e, om
P oposi ion 1 i ollows ha he minimal LD- ec o ial comple ions o he
clu e Λa e he minimal elemen s o {Λ1, Λ2}. In his case, Λ16≤ Λ2and
Λ26≤ Λ1, and so min $LD-Vec (Λ)={Λ1, Λ2}. Obse e ha now he LD-
ec o ial decomposi ion o Λgi en in Example 1 can be s a ed by applying
Theo em 1.
Example 3. Now, on he ini e se Ω={1,2,3,4,5}, we conside he clu e
Λ={{1,2,3},{1,2,4},{1,5},{4,5}}. In such a case, i is a s aigh o wa d
calcula ion o check ha by using o by combining I- ans o ma ions and
T- ans o ma ions, ele en clu e s Λ1, . . . , Λ11 can be ob ained. Speci ically,
by using only I- ans o ma ions we ob ain he clu e s Λ1={{5},{1,2}} and
Λ2={{1},{4,5}}. The clu e s ob ained by using only T- ans o ma ions a e
he clu e s Λ3={{1,4},{1,5},{4,5},{1,2,3},{2,3,4},{2,3,5}} and Λ4=
{{1,3},{1,4},{1,5},{3,4},{3,5},{4,5}}, whe eas he clu e s ob ained by
combining he I- ans o ma ions and he T- ans o ma ions a e he clu e s
Λ5={{1},{5}},Λ6={{1},{2,4},{2,5},{4,5}},Λ7={{5},{1,2},{1,4},
{2,4}},Λ8={{1,2},{1,4},{1,5},{2,4},{2,5},{4,5}},Λ9={{5},{1,2,3},
{1,2,4},{1,3,4},{2,3,4}},Λ10 ={{5},{3,4},{1,2,3},{1,2,4}}, and Λ11 =
{{4},{1,5},{1,2,3},{2,3,5}}. The e o e, by applying P oposi ion 1 we ob-
ain ha he se o he minimal LD- ec o ial comple ions o he clu e Λ
is min $LD-Vec (Λ)= min{Λ1, . . . , Λ11}={Λ1, Λ2, Λ3, Λ9}. So, om The-
o em 1 we conclude ha Λadmi s an LD- ec o ial decomposi ion wi h ou
componen s.
To conclude we gi e an example whe e P oposi ion 1 canno be applied. In
addi ion, he clu e in his example e eals he di e ence be ween Theo em 1
and Theo em 2.
Example 4. On he ini e se Ω={1,2,3,4}o ou poin s, we conside he
clu e Λ={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}. I is easy o p o e ha he
clu e Λis an LD- ec o ial clu e o e any ield K6=Z/(2). The e o e, by
Linea ly dependen ec o ial decomposi ion o clu e s 413
applying Theo em 1 and Theo em 2 we ob ain ha min $LD-Vec (Λ)={Λ};
ha min $LD-Vec K(Λ)={Λ}i K6=Z/(2), and ha min $LD-Vec Z/(2) (Λ)
has a leas wo elemen s. In his example, by an ex ensi e explo a ion i
is no ha d o show ha min $LD-Vec Z/(2) (Λ)has six elemen s; namely
min $LD-Vec Z/(2) (Λ)={Λ1,2, Λ1,3, Λ1,4, Λ2,3, Λ2,4, Λ3,4}, whe e i 1 ≤i1<
i2≤4 and i {i3, i4}={1,2,3,4} {i1, i2}, hen Λi1,i2={{i1, i2},{i1, i3, i4},
{i2, i3, i4}}. Now, om Theo em 2 i ollows ha he clu e Λadmi s an
LD- ec o ial decomposi ion o e Z/(2) wi h six componen s.
Re e ences
[1] He zog, J., and T. Hibi, “Monomial Ideals,” G ad. Tex s in Ma h. 260, Sp inge ,
London, 2010.
[2] Ma ´ı-Fa ´e, J., F om clu e s o ma oids, Elec onic Jou nal o Combina o ics,
21(1) (2014), P1.11 (14 pag.).
[3] Ma ´ı-Fa ´e, J., and C. Pad ´o, On sec e -sha ing schemes, ma oids and polyma-
oids, Jou nal o Ma hema ical C yp ology, 4(2010), 95–120.
[4] Oxley, J.G., “Ma oid Theo y,” Ox o d G adua e Tex in Ma hema ics. Ox o d
Science Publica ions. The Cla endon P ess, Ox o d Uni e si y P ess, New Yo k,
1992.
[5] Seymou , P.D., On sec e -sha ing ma oids, J. Combin. Theo y Se . B, 56 (1992),
69–73.
[6] S anley, R.P., “Combina o ics and Commu a i e Algeb a,” P og ess in Ma he-
ma ics 41. Second Edi ion. Bi kh¨ause , 1995.
[7] Welsh, D.J.A., “Ma oid Theo y,” Academic P ess, London, 1976.
