Partitions of groups and matroids into independent subsets
Can the set R∖{0} be covered by countably many linearly (algebraically) independent subsets over the field Q? We use a matroid approach to show that an answer is ``Yes'' under the Continuum Hypothesis, and ``No'' under its negation.
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2010
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/154609 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Partitions of groups and matroids into independent subsets / T. Banakh, I. Protasov // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 1. — С. 1–7. — Бібліогр.: 4 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860112278094872576 |
|---|---|
| author | Banakh, T. Protasov, I. |
| author_facet | Banakh, T. Protasov, I. |
| citation_txt | Partitions of groups and matroids into independent subsets / T. Banakh, I. Protasov // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 1. — С. 1–7. — Бібліогр.: 4 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | Can the set R∖{0} be covered by countably many linearly (algebraically) independent subsets over the field Q? We use a matroid approach to show that an answer is ``Yes'' under the Continuum Hypothesis, and ``No'' under its negation.
|
| first_indexed | 2025-12-07T17:34:33Z |
| format | Article |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 10 (2010). Number 1. pp. 1 – 7
c© Journal “Algebra and Discrete Mathematics”
Partitions of groups and matroids
into independent subsets
Taras Banakh, Igor Protasov
Abstract. Can the set R \ {0} be covered by countably
many linearly (algebraically) independent subsets over the field Q?
We use a matroid approach to show that an answer is “Yes” under
the Continuum Hypothesis, and “No” under its negation.
In this paper we discuss partitions of groups and other algebraic objects
into independent subsets. The notion of an independent set can be defined
for any hull operator.
By a hull operator on a set X we understand any function 〈·〉 : PX →
PX defined on the power-set PX of X such that A ⊂ 〈A〉 ⊂ 〈B〉 for any
subsets A ⊂ B of X.
A subset A ⊂ X is called independent (with respect to the hull operator
〈·〉) if a /∈ 〈A \ {a}〉 for any point a ∈ A.
We shall say that a hull operator 〈·〉 : PX → PX on a set X
• is idempotent if 〈〈A〉〉 = 〈A〉 for each subset A ⊂ X;
• has finite supports if for each A ⊂ X and a ∈ 〈A〉 there is a finite
subset F ⊂ A with a ∈ 〈F 〉;
• has the MacLane-Steinitz exchange property if for any subset A ⊂ X
and points x, y ∈ X \ 〈A〉 the inclusion x ∈ 〈A ∪ {y}〉 is equivalent
to y ∈ 〈A ∪ {x}〉;
By a matroid we understand a pair (X, 〈·〉) consisting of a set X and
an idempotent hull operator 〈·〉 : PX → PX that has finite supports and
the MacLane-Steinitz exchange property. For finite X our definition of
matroid argees with the classical one, see [2, 1.4.4] or [4, p. 270].
2000 Mathematics Subject Classification: 05B35, 05A18.
Key words and phrases: matroid, partition, independent subset.
2 Partitions of matroids into independent subsets
Theorem 1. Let κ be an infinite cardinal, X be a set of cardinality
|X| = κ+ and 〈·〉 : PX → PX be a hull operator with finite supports and
the MacLane-Steinitz exchange property. If |〈F 〉 \ 〈∅〉| ≤ κ for each finite
subset F ⊂ X, then the set X \ 〈∅〉 can be covered by κ many independent
subsets.
Proof. If |X \ 〈∅〉| ≤ κ, then X \ 〈∅〉 can be decomposed into ≤ κ many
singletons (which are independent sets). So, we assume that |X\〈∅〉| = κ+.
The finite support property of the hull operator and Zorn’s Lemma
imply the existence of a maximal independent subset A ⊂ X. We claim
that X = 〈A〉. Assuming the opposite, we can find a point x ∈ X \〈A〉 and
consider the set A∪ {x} which is dependent as A is maximal independent.
Consequently, there is a point a ∈ A∪{x} such that a ∈ 〈(A∪{x}) \ {a}〉.
This point a is not equal to x as x /∈ 〈A〉. Let B = A \ {a}. Since A
is independent, a /∈ 〈A \ {a}〉 = 〈B〉. Since the hull operator 〈·〉 has
the MacLane-Steinitz exchange property and x, a /∈ 〈B〉, the inclusion
a ∈ 〈B ∪ {x}〉 implies x ∈ 〈B ∪ {a}〉 = 〈A〉, which contradicts the choice
of x. Therefore X = 〈A〉.
Claim 1. |〈B〉 \ 〈∅〉| ≤ max{|B|, κ} for any subset B ⊂ X.
Proof. Let [B]<ω denote the family of finite subsets of B. Since the hull
operator 〈·〉 has finite supports, 〈B〉 =
⋃
F∈[B]<ω〈F 〉. By our assumption,
|〈F 〉 \ 〈∅〉| ≤ κ for each finite subset F ⊂ X. Consequently,
|〈B〉 \ 〈∅〉| =
∣∣∣
⋃
F∈[B]<ω
〈F 〉 \ 〈∅〉
∣∣∣ ≤
∑
F∈[B]<ω
|〈F 〉 \ 〈∅〉| ≤ max{κ, |[B]<ω|} ≤ max{κ, |B|}.
By Claim 1, κ+ = |X \ 〈∅〉| = |〈A〉 \ 〈∅〉| ≤ max{κ, |A|} and thus
|A| = κ+. Fix an injective enumeration A = {aα : α < κ+}.
For every ordinal α < κ+, put
Aα = {aγ : γ < α} and Xα = 〈Aα+1〉 \ 〈Aα〉.
Then X \ 〈∅〉 =
⋃
α<κ+ Xα and for every α < κ+
|Xα| = |〈Aα+1〉 \ 〈Aα〉| ≤ |〈Aα+1〉 \ 〈∅〉| 6 κ
according to Claim 1. For every α < κ+ fix an injection χα : Xα → κ and
define a function χ : X \ 〈∅〉 → κ letting χ|Xα = χα for all α < κ+. For
every λ < κ consider the set Zλ = χ−1(λ). We claim that {Zλ : λ < κ} is
a desired partition into κ many independent subsets.
T. Banakh, I. Protasov 3
Assuming that some set Zλ is dependent, we can find a finite dependent
subset F ⊂ Zλ. We can assume that F is a minimal dependent subset.
Since F is dependent, there is an element a ∈ F such that a ∈ 〈F \ {a}〉.
We claim that x ∈ 〈F \ {x}〉 for any element x ∈ F . This is clear if
x = a. So, we assume that x 6= a. Consider the set E = F \ {x, a}.
Since F is minimal dependent, the subsets E ∪ {a} and E ∪ {x} are
independent and thus a, x /∈ 〈E〉. Since a ∈ 〈F \ {a}〉 = 〈E ∪ {x}〉 the
MacLane-Steinitz exchange property of the hull operator 〈·〉 guarantees
that x ∈ 〈E ∪ {a}〉 = 〈F \ {x}〉.
Since χ is injective on each subset Xα, there exist a numeration
F = {f1, . . . , fn} and ordinals α1 < α2 < . . . < αn < κ+ such that
f1 ∈ Yα1
, . . . , fn ∈ Yαn
. Then fn /∈ 〈{f1, . . . , fn−1}〉 = 〈F \ {fn}〉, which
is a desired contradiction.
Corollary 1. Let κ be an infinite cardinal, X \ {0} be a vector space
over a field F such that |F | 6 κ and dimX = κ+. Then X \ {0} can be
partitioned in κ linearly independent subsets.
Corollary 2. Let κ be an infinite cardinal, X \ {0} be an extension of a
field F such that |F | 6 κ and |X| = κ+. Then X \ {0} can be partitioned
in κ subsets algebraically independent over F .
Corollary 3. Let κ be an infinite cardinal, Kκ+ be a complete graph with
κ+ many vertices. Then there exists an edge coloring of Kκ+ in κ colors
with no monochrome cycles.
Now we consider independent subsets in groups. We define a subset A of
a group G to be independent if A contains no point a ∈ A with a ∈ 〈A\{a}〉
where 〈A\{a}〉 is the subgroup of G generated by the set A\{a}. Thus A
is independent with respect to the hull operator 〈·〉 : PG → PG assigning
to each subset B ⊂ G the subgroup 〈B〉 generated by B. This hull operator
is idempotent and has finite supports, but in general fails to have the
MacLane-Steinitz exchange property. Because of that, Theorem 1 is not
applicable to the following open problem.
Problem 1. Let G be an (abelian) group G of cardinality |G| = ℵ1 with
neutral element {e}. Can G\{e} be covered by countably many independent
subsets?
Let us prove that for groups of cardinality > ℵ1 this problem has a
negative solution.
Theorem 2. Let κ be an infinite cardinal and G be a group of cardinality
|G| > κ+. Then, for every coloring χ : G \ {e} → κ, there exists a
dependent monochrome subset A of G of cardinality |A| = 4.
4 Partitions of matroids into independent subsets
We shall need a simple combinatorial lemma.
Lemma 1. Let λ ≥ 1 be a cardinal and κ be an infinite cardinal. Let
X,Y be sets of cardinality |X| = κ+ and |Y | > (κ+)λ. For any κ-coloring
χ : X × Y → κ there are subsets A ⊂ X and Z ⊂ Y such that |A| = λ,
|Z| > (κ+)λ and the set A× Z is monochrome.
Proof. Since |X| > κ, for every y ∈ Y , there exist a subset A(y) ⊂ X of
cardinality |A(y)| = λ such that A(y) × {y} is monochrome and hence
χ(A(y)× {y}) = {χ̃(y)} for some color χ̃(y). Now consider the function
f : Y → [X]λ × κ defined by
f(y) = (A(y), χ̃(y)).
Since |[X]λ × κ| ≤ (κ+)λ < |Y | there exists a pair (A,α) ∈ [X]λ × κ
such that the preimage Z = f−1(A,α) has cardinality |Z| > (κ+)λ. Then
A× Z is a required monochrome rectangle.
Proof of Theorem 2. Since |G| > κ+, we can choose two sets X,Y ⊂
G \ {e} of cardinality |X| = κ+ and |Y | > κ+ such that Y ∩ X−1 = ∅.
Given any κ-coloring χ : G\{e} → κ, consider the coloring χ̃ : X×Y → κ
defined by χ̃(x, y) = χ(xy). By Lemma 1, there are a 2-element set
A = {a, b} ⊂ X and a subset Z ⊂ X of cardinality |Z| > κ+ such
that the set A × Z is monochrome. Choose any point x ∈ Z and any
point y ∈ Z \ {a−1bx, b−1ax}. Then the set B = {ax, bx, ay, by} ⊂ G has
cardinality |B| = 4 and is monochrome with respect to the coloring χ.
Since ax = ay(by)−1bx, the set B is dependent.
Next, we consider covers of abelian groups by linearly independent
subsets. Following [1, §16] or [3, §4.2], we call a subset A of an abelian group
G linearly independent if for any pairwise distinct points a1, . . . , an ∈ A
and integer numbers λ1, . . . , λn ∈ Z the equality
λ1a1 + · · ·+ λnan = 0
implies λ1a1 = · · · = λnan = 0.
Observe that a subset A of an abelian group G is linearly independent
if and only if it is independent with respect to the hull operator [ · ] : PG →
PG assigning to each subset B ⊂ G the subset
[B] = {0} ∪ {x ∈ G : ∃n ∈ N nx ∈ 〈B〉 \ {0}}.
The hull operator [ · ] is idempotent and has finite supports and the
MacLane-Steinitz exchange property. So, the pair (G, [ · ]) is a matroid.
T. Banakh, I. Protasov 5
Since 〈A〉 ⊂ [A] for any A ⊂ X, each independent subset of G is
linearly independent. On the other hand, the subset {2, 3} of the group of
integers Z is independent but not linearly independent.
For an abelian group G and a natural number n ∈ N consider the
subgroup
G[n] = {x ∈ G : nx = 0}.
The union G[N] =
⋃
n∈NG[n] is called the torsion part of G.
Theorem 3. Let κ be an infinite cardinal and G be an abelian group.
The set G \ {0} can be covered by κ many linearly independent subsets if
and only if |G| ≤ κ+ and either |G[N]| ≤ κ or G = G[p] for some prime
number p.
Proof. First we prove the “if” part. Assume that |G| ≤ κ+ and either
|G[N]| ≤ κ or G[p] = G for some prime number p.
If |G| ≤ κ, then G\{0} decomposes into |G\{0}| ≤ κ many singletons,
which are linearly independent. So, we assume that |G| = κ+.
Consider the hull operator [ · ] : PG → PG turning G into a matroid
whose independent sets coincide with linearly indepenent subsets of G.
Theorem 1 will imply that G \ {0} can be covered by κ many linearly
independent subsets as soon as we prove that for each finite subset F ⊂ G
the hull [F ] has cardinality |[F ]| ≤ κ.
First we consider the case |G[N]| ≤ κ. For every n ∈ N consider the
homomorphism n : G → G, n : x 7→ nx, whose kernel coincides with
the subgroup G[n] that has cardinality |G[n]| ≤ |G[N]| ≤ κ. Taking into
account that |〈F 〉| ≤ ℵ0 and
[F ] = {0} ∪
⋃
n∈N
n−1(〈F 〉 \ {0}) ⊂
⋃
n∈N
n−1(〈F 〉),
we conclude that
|[F ]| ≤
∑
n∈N
|n−1(〈F 〉)| ≤
∑
n∈N
|G[n]| · |〈F 〉| ≤ κ.
Next, assume that G = G[p] for a prime number p. Then G is a linear
space over the p-element field Fp and by Corollary 1, G can be covered by
κ many linearly independent subsets.
To prove the “only if” part, assume that G \ {0} can be covered by κ
many linearly independent subsets. By Theorem 2, |G| ≤ κ+. It remains
to prove that |G[N]| > κ implies G[p] = G for a prime number p. For
every prime number p, consider the subgroup G[p∞] =
⋃
k∈NG[pk]. By [3,
4.1.1], G[N] = ⊕
p∈Π
G[p∞] where Π denotes the set of all prime numbers.
6 Partitions of matroids into independent subsets
Since |G[N]| = κ+, there exists a prime number p such that |G[p∞]| = κ+
and hence |G[pn]| = κ+ for some n ∈ N. We can assume that n is the
smallest number with this property, i.e., |G[pn−1]| < κ+.
We claim that G = G[pn]. Otherwise, we can choose a point a ∈
G \G[pn]. By our assumption, G \ {0} can be covered by κ many linearly
independent subsets. The coset a+G[pn] has cardinality κ+ and hence
contains two distinct points a+ x, a+ y that lie in a linearly independent
subset of G. On the other hand, the set {a+x, a+y} is linearly dependent
since pn(a + x) − pn(a + y) = 0 but pn(a + x) = pna 6= 0 6= pn(a + y).
This contradiction shows that G = G[pn], which means that the group
G has bounded height and then by Prüfer-Baer Theorem 4.3.5 in [3], G
is a direct sum ⊕α<κ+Hα of cyclic p-groups of order |Hα| ≤ pk. Each
group Hα contains a cyclic subgroup Cα of order p. Then the subgroup
⊕α<κ+Cα ⊂ G[p] has cardinality κ+ and hence pn = p by the choice of n.
Therefore, G = G[pk] = G[p].
Theorem 3 implies that for the direct sum G = ⊕ℵ1C4 ℵ1 many
cyclic groups of order 4 the set G \ {0} cannot be covered by countably
many linearly independent sets. The same concerns the group ⊕ℵ1C6 =
(⊕ℵ1C2)⊕ (⊕ℵ1C3).
Problem 2. Can the groups ⊕ℵ1C4 and ⊕ℵ1C6 with removed zeros be
covered by countably many independent sets.
Corollaries 1, 2 and Theorem 2 imply the following interesting equiva-
lence.
Theorem 4. The following statements are equivalent:
1. For the linear space R over the field Q there is a partition of R \ {0}
into countably many linearly independent subsets over Q.
2. For the extension R of the field Q there is a partition of R \ {0} into
countably many algebraically independent subsets over Q.
3. For the abelian group R there is a partition of R \ {0} into countably
many independent subsets.
4. The Continuum Hypothesis is true.
Remark 1. Let κ, µ be infinite cardinals such that κ+ < µ. It follows from
Lemma 1 that for every κ-coloring of the set of edges of the complete graph
Kµ, there exists a monochrome cycle of length 4. Moreover, S. Slobodianyuk
observed that the proof of Lemma 1 gives a monochrome complete bipartite
T. Banakh, I. Protasov 7
subgraph Kλ,µ provided that λ 6 κ+ and (κ+)λ < cfµ. In particular, there
exists a monochrome cycle of any even length.
On the other hand, for the complete graph K2κ its set of vertice V = 2κ
can be identified with the set of all functions f : κ → {0, 1}, which allows
us to define a coloring χ : [V ]2 → κ by the rule
χ({f, g}) = min{α : f(α) 6= g(α)}.
For this coloring, K2κ has no monochrome cycles of odd length.
Acknowledgement. We would like to thank Sergiy Slobodianuyk for
stimulating questions and remarks.
References
[1] L. Fuchs, Infinite abelian groups. I, Academic Press, New York-London, 1970.
[2] J. Oxley, Matroid Theory, Oxford Univ. Press., Oxford, 1992.
[3] D. Robinson, A course in the theory of groups, Springer-Verlag, New York, 1996.
[4] K. A. Rybnikov, Introduction to Combinatorial Analysis, Moskow University Press,
1985.
Contact information
T. Banakh Department of Mathematics, Ivan Franko
National University of Lviv, Universytetska
1, 79000 Lviv, Ukraine
E-Mail: t.o.banakh@gmail.com
I. Protasov Department of Cybernetics, Kyiv National
University, Volodymyrska 64, 01033 Kyiv,
Ukraine
E-Mail: i.v.protasov@gmail.com
Received by the editors: 04.10.2010
and in final form 04.10.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-154609 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T17:34:33Z |
| publishDate | 2010 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Banakh, T. Protasov, I. 2019-06-15T16:50:24Z 2019-06-15T16:50:24Z 2010 Partitions of groups and matroids into independent subsets / T. Banakh, I. Protasov // Algebra and Discrete Mathematics. — 2010. — Vol. 10, № 1. — С. 1–7. — Бібліогр.: 4 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:05B35, 05A18. https://nasplib.isofts.kiev.ua/handle/123456789/154609 Can the set R∖{0} be covered by countably many linearly (algebraically) independent subsets over the field Q? We use a matroid approach to show that an answer is ``Yes'' under the Continuum Hypothesis, and ``No'' under its negation. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Partitions of groups and matroids into independent subsets Article published earlier |
| spellingShingle | Partitions of groups and matroids into independent subsets Banakh, T. Protasov, I. |
| title | Partitions of groups and matroids into independent subsets |
| title_full | Partitions of groups and matroids into independent subsets |
| title_fullStr | Partitions of groups and matroids into independent subsets |
| title_full_unstemmed | Partitions of groups and matroids into independent subsets |
| title_short | Partitions of groups and matroids into independent subsets |
| title_sort | partitions of groups and matroids into independent subsets |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/154609 |
| work_keys_str_mv | AT banakht partitionsofgroupsandmatroidsintoindependentsubsets AT protasovi partitionsofgroupsandmatroidsintoindependentsubsets |