ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.02
https://doi.org/10.26493/1855-3974.2616.4a9
(Also available at http://amc-journal.eu)
Factorizing the Rado graph and
infinite complete graphs*
Simone Costa † , Tommaso Traetta
DICATAM - Sez. Matematica, Università degli Studi di Brescia,
Via Valotti 9, I-25123 Brescia, Italy
Received 30 April 2021, accepted 18 January 2023, published online 1 August 2023
Abstract
Let F = {Fα : α ∈ A} be a family of infinite graphs, together with Λ. The Factor-
ization Problem FP (F ,Λ) asks whether F can be realized as a factorization of Λ, namely,
whether there is a factorization G = {Γα : α ∈ A} of Λ such that each Γα is a copy of Fα.
We study this problem when Λ is either the Rado graph R or the complete graph Kℵ
of infinite order ℵ. When F is a countably infinite family, we show that FP (F , R) is
solvable if and only if each graph in F has no finite dominating set. We also prove that
FP (F ,Kℵ) admits a solution whenever the cardinality of F coincides with the order and
the domination numbers of its graphs.
For countable complete graphs, we show some non existence results when the dom-
ination numbers of the graphs in F are finite. More precisely, we show that there is no
factorization of KN into copies of a k-star (that is, the vertex disjoint union of k countable
stars) when k = 1, 2, whereas it exists when k ≥ 4, leaving the problem open for k = 3.
Finally, we determine sufficient conditions for the graphs of a decomposition to be
arranged into resolution classes.
Keywords: Factorization problem, resolution problem, Rado graph, infinite graphs.
Math. Subj. Class. (2020): 05C63, 05C70
1 Introduction
We assume that the reader is familiar with the basic concepts in (infinite) graph theory, and
refer to [10] for further details.
*The authors gratefully acknowledge support from GNSAGA of Istituto Nazionale di Alta Matematica.
†Corresponding author.
E-mail addresses: simone.costa@unibs.it (Simone Costa), tommaso.traetta@unibs.it (Tommaso Traetta)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P1.02
In this paper all graphs will be simple, namely, without multiple edges or loops. As
usual, we denote by V (Λ) and E(Λ) the vertex set and the edge set of a simple graph Λ,
respectively. We say that Λ is finite (resp. infinite) if its vertex set is so, and refer to the
cardinality of V (Λ) and E(Λ) as the order and the size of Λ, respectively. Note that in the
finite case |E(Λ)| ≤
(|V (Λ)|
2
)
, whereas if Λ is infinite, then its order, which is a cardinal
number, is greater than or equal to its size. We use the notation Kv for any complete graph
of order v, and denote by KV the complete graph whose vertex set is V .
Given a subgraph Γ of a simple graph Λ, we denote by Λ \ Γ the graph obtained from
Λ by deleting the edges of Γ. If Γ contains all possible edges of Λ joining any two of its
vertices, then Γ is called an induced subgraph of Λ (in other words, an induced subgraph is
obtained by vertex deletions only). Instead, if V (Γ) = V (Λ), then Γ is called a spanning
subgraph or a factor of Λ (hence, a factor is obtained by edge deletions only). If Γ is also h-
regular, then we speak of an h-factor. We recall that a set D of vertices of Λ is dominating if
all other vertices of Λ are adjacent to some vertex of D. The minimum size of a dominating
set of Λ is called the domination number of Λ. Finally, we say that Λ is locally finite if its
vertex degrees are all finite.
A decomposition of Λ is a set G = {Γ1,Γ2, . . .} of subgraphs of Λ whose edge-sets
partition E(Λ). If the graphs Γi are all isomorphic to a given subgraph Γ of Λ, then we
speak of a Γ-decomposition of Λ. When Γ and Λ are both complete graphs, we obtain
2-designs. More precisely, a Kk-decomposition of Kv is equivalent to a 2-(v, k, 1) design.
Classically, the graphs Γi and Λ are taken to be finite, and the same usually holds for the
parameters v and k of a 2-design. However, there has been considerable interest in designs
on a infinite set of v points, mainly when k = 3. In this case, we obtain infinite Steiner
triple systems whose first explicit constructions were given in [12, 13]. Further results
concerning the existence of rigid, sparse, and perfect countably Steiner triple systems can
be found in [6, 7, 11]. Results showing that any Steiner system can be extended are given
in [1, 15]. The existence of large sets of Steiner triple systems for every infinite v (and
more generally, of infinite Steiner systems) can be found in [4]. Also, infinite versions of
topics in finite geometry, including infinite Steiner triple systems and infinite perfect codes
are considered in [3]. A more comprehensive list of results on infinite designs can be found
in [9].
When each graph of a decomposition G of Λ is a factor (resp. h-factor), we speak of a
factorization (resp. h-factorization) of Λ. Also, when the factors of G are all isomorphic to
Γ, we speak of a Γ-factorization of Λ. A factorization of Kv into factors whose components
are copies of Kk is equivalent to a resolvable 2-(v, k, 1) design.
In this paper, we consider the Factorization Problem for infinite graphs, which is here
stated in its most general version.
Problem 1.1. Let Λ be a graph of order ℵ and let F = {Fα : α ∈ A} be a family
of (non-empty) infinite graphs, not necessarily distinct, each of which has order ℵ, with
ℵ ≥ |A|.
The Factorization Problem FP (F ,Λ) asks for a factorization G = {Γα : α ∈ A} of Λ
such that Γα is isomorphic to Fα, for every α ∈ A. If Λ is the complete graph of order ℵ,
we simply write FP (F). If in addition to this each Fα is isomorphic to a given graph F
and |A| = ℵ, we write FP (F ). 1
1Since in this case the factorization problem can be seen as a generalization of the Oberwolfach problem, in
[8] the problem FP (F ) was denoted by OP (F ).
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 3
Note that the graphs of F are allowed to have zero degree vertices. This means that if
Fα contains isolated vertices, then Γα is a copy of Fα covering all vertices of Kℵ (hence a
factor of Kℵ) and having the same number of isolated vertices as Fα. Otherwise, Fα has
no zero degree vertices, hence Γα is a factor of Kα in the usual sense, that is, a spanning
subgraph without isolated vertices.
As far as we know, there are only four papers dealing with the Factorization Problem
for infinite complete graphs, and two of them, concern classic designs. In [14] it is shown
that there exists a resolvable 2-design whenever v = |N| and k is finite; these designs have,
in addition, a cyclic automorphism group G acting sharply transitively on the vertex set;
briefly they are G-regular. In [9] it is shown that every infinite 2-design with k < v is
necessarily resolvable, and when k = v, both resolvable and non-resolvable designs exist.
We point out that in [9, 14] both these results are proven more generally for t-designs
whenever t ≥ 2 is finite.
Furthermore, in [2] the authors construct a G-regular 1-factorization of a countably
infinite complete graph for every finitely generated abelian infinite group G. Finally, [8]
proves the following.
Theorem 1.2. Let F be a graph whose order is the cardinal number ℵ. FP (F ) has a
G-regular solution whenever the following two conditions hold:
(1) F is locally finite,
(2) G is an involution free group of order ℵ.
Note that this result generalizes the one obtained in [14] to any complete graph of
infinite order ℵ, blocks of any size less than ℵ, and groups G not necessarily cyclic. Fur-
thermore, Theorem 1.2 can also be seen as a generalization of the result in [2] to complete
graphs of any infinite order.
When dealing with infinite graphs, a central role is played by the Rado graph R (see [16]),
named after Richard Rado who gave one of its first explicit constructions. Indeed, R is the
unique countably infinite random graph, and it can be constructed as follows: V (R) = N
and a pair {i, j} with i < j is an edge of R if and only if the i-th bit of the binary repre-
sentation of j is one. R shows many interesting properties, such as the universal property:
every finite or countable graph can be embedded as an induced subgraph of R.
When replacing the concept of induced subgraph with the dual one of factor, a weaker
result holds. Indeed, in [5] it is pointed out that a countable graph F can be embedded as
a factor of R if and only if the domination number of F is infinite. In the same paper, it is
further shown that FP (F , R) has a solution whenever F is infinite and each of its graphs is
locally finite. Note that a locally finite countable graph has infinite domination number, but
the converse is not true: for example, the Rado graph is not locally finite and it has no finite
dominating set (indeed, for every D = {i1, . . . , it} ⊂ N, there exists an integer j ∈ N
whose binary representation has 0 in positions i1, . . . , it, which means that j is adjacent
with no vertex of D).
In this paper, we extend this result to any countable family F of admissible graphs.
More precisely, we prove the following. We point out that throughout the paper, any count-
able family (or graph) is understood to be infinite.
Theorem 1.3. Let F be a countable family of countable graphs. Then, FP (F , R) has a
solution if and only if the domination number of each graph of F is infinite.
4 Ars Math. Contemp. 24 (2024) #P1.02
Furthermore, we prove the solvability of FP (F) whenever the size of F coincides with
the order and the domination number of its graphs.
Theorem 1.4. Let F be a family of graphs, each of which has order ℵ. FP (F) has a
solution whenever the following two conditions hold:
(1) |F| = ℵ, and
(2) the domination number of each graph in F is ℵ.
When F contains only copies of a given graph F satisfying condition (1) of Theo-
rem 1.2 (i.e., F is locally finite), then F satisfies both conditions (1) and (2) of Theo-
rem 1.4. Therefore, Theorem 1.4 can be seen as a generalization of Theorem 1.2, even
though it does not provide any information on the automorphisms of a solution to FP.
Note that if we just require that the domination number of each graph of F is ℵ, there
may exist factorizations with fewer factors than ℵ; this means that the two conditions in
Theorem 1.4 are independent. Indeed, the Rado graph R has no finite dominating set and
Corollary 2.4 shows that for every n ≥ 2 there exists a factorization of KN into n copies
of R. We point out that Theorem 1.4 constructs instead factorizations of KN into infinite
copies of R.
The paper is organized as follows. In Sections 2 and 3, we prove the main results
of this paper, Theorems 1.3 and 1.4. In Section 4, we deal with F -factorizations of KN
when F belongs to a special class of graphs with finite domination number (and hence not
satisfying condition (2) of Theorem 1.4): the countable k-stars (briefly, Sk), that is, the
vertex disjoint union of k countable stars. We prove that FP (Sk) has a solution whenever
k > 3, and there is no solution for k ∈ {1, 2}. This shows that there are families F of
graphs for which FP (F) is not solvable. We leave open the problem when k = 3. In the
last section, inspired by [9], we provide a sufficient condition for a decomposition F of Kℵ
to be resolvable (i.e., the graphs of F can be partitioned into factors of Kℵ).
2 Factorizing the Rado graph
In this section, we prove Theorem 1.3. Also, since the Rado graph R is self-complementary,
that is, KN \ R is isomorphic to R, we obtain as a corollary the countable version of
Theorem 1.4.
We start by recalling an important characterization of the Rado graph (see, for example,
[5]).
Theorem 2.1. A countable graph is isomorphic to the Rado graph if and only if it satisfies
the following property:
⋆ for every disjoint finite sets of vertices U and W , there exists a vertex z adjacent to
all the vertices of U and non-adjacent to all the vertices of V .
Property ⋆ is usually referred to as the existentially closed property. Therefore, Theo-
rem 2.1 states that, up to isomorphism, there is exactly one existentially closed countable
graph: the Rado graph.
Now we slightly generalize the construction of the Rado graph given in the introduction.
Definition 2.2. Given a set I ⊂ {0, . . . , q − 1}, with 1 ≤ |I| < q, we denote by RqI the
following graph: V (RqI) = N, and {x, y}, with x < y, is an edge of R
q
I whenever the x-th
digit of y in the base q expansion of y belongs to I .
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 5
Cleraly, when q = 2 and I = {1} we obtain our initial description of the Rado graph
(i.e. R = R2{1}).
Proposition 2.3. Every graph RqI is isomorphic to the Rado graph.
Proof. By Theorem 2.1, it is enough to show RqI is existentially closed. We assume, with-
out loss of generality, that 0 ∈ I while 1 ̸∈ I , and let U and V be two disjoint finite subsets
of N. Then there are infinitely many positive integers whose base q expansion has 0 in each
position u ∈ U and 1 in each position v ∈ V . Denoting by z one of these integers larger
than max(U ∪ V ), we have that z is adjacent to all the vertices of U but to none in V .
Note that KN =
⋃q−1
i=0 R
q
{i} and R
q
{0,...,q−2} =
⋃q−2
i=0 R
q
i . Considering that the R
q
{i}s
are pairwise edge-disjoint and isomorphic to the Rado graph, by taking n = q−1 we obtain
the following.
Corollary 2.4. For every positive integer n, the graphs R and KN can be factorized into n
and n+ 1 copies of R, respectively.
The following result is crucial to prove Theorem 1.3. It strengthens a result given in
[5] and allows us to suitably embed in the Rado graph R any countable graph with infinite
domination number.
Proposition 2.5. Let F be a countable graph with no finite dominating set. For every edge
e ∈ E(R), there exists an embedding σe of F in R such that:
(1) σe(F ) is a spanning subgraph of R containing the edge e;
(2) R \ σe(F ) is isomorphic to R.
Proof. By Proposition 2.3, the graphs R3{0,1}, R
3
{0} and R
3
{1} are isomoprhic to R. There-
fore, we can take R = R3{0,1}.
Let e be an edge of R = R3{0} ∪R
3
{1}. We can assume without loss of generality that e
lies in R3{0}. In [5, Proposition 8], it is shown that there exists an embedding σe of F into
the Rado graph R3{0} ⊂ R satisfying condition (1). It is then left to prove that condition (2)
holds. By Theorem 2.1, this is equivalent to saying that R \ σe(F ) satisfies ⋆.
Let U and V be two finite disjoint subsets of N. Clearly, there are infinitely many
positive integers whose base 3 expansion has 1 in each position u ∈ U and 2 in each
position v ∈ V . Let z be one of these integers larger than max(U ∪ V ). Since R \ σe(F )
contains R3{1} and it is edge-disjoint from R
3
{2}, it follows that z is adjacent in R\σe(F ) to
all the vertices of U and is non-adjacent to all the vertices of V . This means that R \σe(F )
is existentially closed.
We are now ready to prove Theorem 1.3, whose statement is recalled here, for clarity.
Theorem 1.3. Let F be a countable family of countable graphs. Then, FP (F , R) has a
solution if and only if the domination number of each graph of F is infinite.
Proof. Since the Rado graph has no finite dominating set, the same holds for its spanning
subgraphs. Hence, each graph of F must have infinite domination number. Under this
assumption, we are going to show that FP (F , R) has a solution.
6 Ars Math. Contemp. 24 (2024) #P1.02
By definition of Rado graph, it is easy to see that |E(R)| = ℵ0, which is also the car-
dinality of F . Let E(R) = {e1, . . . , en, . . .} and F = {F1, . . . , Fn, . . .}. By recursively
applying Proposition 2.5, we obtain a sequence of isomorphisms σei : Fi → Γi satisfying
for each i ∈ N the following properties:
• Γi is a spanning subgraph of R;
• R \ (Γ1 ∪ Γ2 ∪ · · · ∪ Γi−1) is isomorphic to R and contains Γi;
• ei lies in Γ1 ∪ Γ2 ∪ · · · ∪ Γi.
It follows that the Γis are pairwise edge-disjoint factors of R which partition E(R). There-
fore, {Γi : i ∈ N} is a solution to FP (F , R).
The proof of Theorem 1.3 allows us to construct solutions to FP (F , R) even when
the cardinality of F is finite, provided that F contains a copy of the Rado graph. In other
words, we have the following.
Corollary 2.6. Let F be a finite family of countable graphs such that
(1) F contains at least one graph isomorphic to the Rado graph;
(2) the domination number of each graph in F is infinite.
Then, FP (F , R) has a solution.
Recalling that R is self complementary, the countable version of Theorem 1.4 can be
easily obtained as a corollary to Theorem 1.3.
Corollary 2.7. Let F be a countable family of countable graphs. FP (F) has a solution
whenever the domination number of each graph in F is infinite.
Proof. Recall that R2{0} and R
2
{1} are copies of R which together factorize KN. Therefore,
it is enough to partition F into two countable families F1 and F2, and then apply Theo-
rem 1.3 to get a solution Gi to FP (Fi, R2{i}), for i = 0, 1. Clearly, G1 ∪ G2 provides a
solution to FP (F).
The natural generalization of property ⋆ to a generic cardinality ℵ is the following one:
⋆ℵ for every disjoint sets of vertices U and W whose cardinality is smaller than ℵ, there
exists a vertex z adjacent to all the vertices of U and non-adjacent to all the vertices
of V .
Then, using the transfinite induction (see Theorem 3.5 below), one could also prove the
following generalization of Proposition 2.1:
Proposition 2.8. Any two graphs of order ℵ that satisfy property ⋆ℵ are pairwise isomor-
phic.
Therefore, we can refer to any graph of order ℵ and satisfying property ⋆ℵ as the ℵ-
Rado graph Rℵ. Its existence is guaranteed under the Generalized Continuum Hypothesis
(GCH) which states that if ℵ′ ≺ ℵ then 2ℵ′ ⪯ ℵ. Under GCH, one can see that the set S of
all q-ary sequences of length ≺ ℵ has size ℵ. Indeed, for every ℵ′ ≺ ℵ, the set of all q-ary
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 7
sequences of length ℵ′ has cardinality 2ℵ′ , and by GCH we have that 2ℵ′ ⪯ ℵ; therefore,
|S| has size at most ℵ. Clearly, ℵ′ ≺ 2ℵ′ ⪯ |S| for every ℵ′ ≺ ℵ. It then follows that
|S| = ℵ.
This means that the construction of the countable Rado graph (Definition 2.2) based on
representing every natural number with a finite q-ary sequence (its base q expansion) can
be generalized to any order.
By assuming that GCH holds, we will prove as a corollary to Theorem 1.4 the following
generalization of Theorem 1.3.
Theorem 2.9. Let F be a family of graphs of order ℵ and assume that |F| = ℵ. Then
FP (F , Rℵ) has a solution if and only if the domination number of each graph in F is ℵ.
3 Factorizing infinite complete graphs
We say that a graph or a set of vertices is ℵ-small (resp. ℵ-bounded) if their order or
cardinality is smaller than ℵ (resp. smaller than or equal to ℵ). Given two graphs F and
Λ of order ℵ, we denote by Σℵ(F,Λ) the set of all graph embeddings between an induced
ℵ-small subgraph of F and a subgraph of Λ. A partial order on Σℵ(F,Λ) can be easily
defined as follows: if σ : G → Γ and σ′ : G′ → Γ′ are embeddings of Σℵ(F,Λ), we say
that σ ≤ σ′ whenever σ′ is an extension of σ, namely, G and Γ are subgraphs of G′ and Γ′,
respectively, and σ′|G = σ (where σ′|G is the restriction of σ′ to G).
Lemma 3.1. Let F be a graph of order ℵ and with no ℵ-small dominating set. Also, let Θ
be an ℵ-small subgraph of Kℵ, and let σ ∈ Σℵ(F,Kℵ \Θ).
(1) If v ∈ V (F ), then there is an embedding σ′ : G′ → Γ′ in Σℵ(F,Kℵ \Θ) such that
|V (G′)| ≤ |V (G)|+ 1, σ ≤ σ′ and v ∈ V (G′);
(2) If x ∈ V (Kℵ), then there is an embedding σ′′ : G′′ → Γ′′ in Σℵ(F,Kℵ \ Θ) such
that
|V (G′′)| ≤ |V (G)|+ 1, σ ≤ σ′′ and x ∈ V (Γ′′).
Proof. Let σ : G → Γ be an embedding in Σℵ(F,KN \ Θ), and let v ∈ V (F ) and
x ∈ V (Kℵ). Clearly, when v ∈ V (G) or x ∈ V (Γ), we can take σ′ = σ or σ′′ = σ,
respectively. Therefore, we can assume v ̸∈ V (G) and x ̸∈ V (Γ).
1. Let G′ be the subgraph of F induced by v and V (G). Since V (Θ) is ℵ-small, we
can choose a ∈ V (Kℵ) \ V (Θ) and let σ′ : V (G) ∪ {v} → V (Γ) ∪ {a} be the
extension of σ such that σ′(v) = a. Setting Γ′ = σ′(G′), we have that σ′ is the
required embedding of Σℵ(F,Kℵ \Θ).
2. Since F has no ℵ-small dominating set, V (G) (which is an ℵ-small set) cannot be
a dominating set for F . Hence, there is a vertex a ∈ V (F ) that is not adjacent to
any of the vertices of G. We denote by G′′ (resp., Γ′′) the graph obtained by adding
a to G (resp., x to Γ) as an isolated vertex. Clearly, G′′ is an induced subgraph of
F ; also, Γ′′ and Θ have no edge in common, since E(Γ′′) = E(Γ). Therefore, the
extension σ′′ : G′′ → Γ′′ of σ such that σ′′(a) = x is the required embedding of
Σℵ(F,Kℵ \Θ).
8 Ars Math. Contemp. 24 (2024) #P1.02
From now on, we will work within the Zermelo-Frankel axiomatic system with the
Axiom of Choice in the form of the Well-Ordering Theorem. We recall the definition of a
well-order.
Definition 3.2. A well-order ≺ on a set X is a total order on X with the property that every
non-empty subset of X has a least element.
The following theorem is equivalent to the Axiom of Choice.
Theorem 3.3 (Well-Ordering). Every set X admits a well-order ≺.
Given an element x ∈ X , we define the section X≺x associated to it:
X≺x = {y ∈ X : y ≺ x}.
Corollary 3.4. Every set X admits a well-order ≺ such that the cardinality of any section
is smaller than |X|.
Proof. Let us consider a well-order ≺ on X . Let x be the smallest element such that X≺x
has the same cardinality as X . The set Y = X≺x is such that all its sections with respect
to the order ≺ have smaller cardinality. Since Y instead has the same cardinality as X , the
order ≺ on Y induces an order ≺′ on X with the required property.
We recall now that well-orderings allow proofs by induction.
Theorem 3.5 (Transfinite induction). Let X be a set with a well-order ≺ and let Px denote
a property for each x ∈ X . Set 0 = minX and assume that:
• P0 is true, and
• for every x ∈ X , if Py holds for every y ∈ X≺x, then Px holds.
Then Px is true for every x ∈ X .
We are now ready to prove Theorem 1.4. The idea behind the proof can be better under-
stood by restricting our attention to the countable case, ℵ = N. To solve
FP ({Fα : α ∈ N}), we first order the edges of KN : {e0, e1, . . . , eγ , . . .}. Then, we define
embeddings σβα : G
β
α → Γβα where Gβα is an induced subgraph of Fα, and Γβα is a subgraph
of KN. These embeddings are obtained by recursively applying Lemma 3.1 which adds, at
each step, a vertex to Gβα and a vertex to Γ
β
α and makes sure that the vertex β belongs to
both these graphs (this procedure can be seen as a variation of Cantor’s “back-and-forth”
method). We also make sure that, for every γ, the graphs Γγ0 ,Γ
γ
1 , . . . ,Γ
γ
γ are pairwise edge-
disjoint and contain between them the edge eγ . The solution to FP ({Fα : α ∈ N}) will
be represented by G = {Γα : α ∈ N} where Γα =
⋃
β Γ
β
α.
Theorem 1.4 Let F be a family of graphs, each of which has order ℵ. FP (F) has a
solution whenever the following two conditions hold:
1. |F| = ℵ, and
2. the domination number of each graph in F is ℵ.
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 9
Proof. Let F = {Fα : α ∈ A}. We consider a well-order ≺ on A satisfying Corollary 3.4.
Since by assumption |V (Fα)| = |A| = ℵ, for every α ∈ A, we can take V (Fα) =
V (Kℵ) = A and index the edges of Kℵ over A: E(Kℵ) = {eα : α ∈ A}.
To prove the assertion, we construct a chain of families (Eγ)γ∈A, where
Eγ := {σβα : Gβα → Γβα | σβα ∈ Σℵ(Fα,Kℵ), (α, β) ∈ A⪯γ ×A⪯γ},
which satisfy the ascending property, that is, Eγ′ ⊆ Eγ if γ′ ⪯ γ, and the following three
conditions:
(1γ) for every (α, β) ∈ A⪯γ × A⪯γ and β′ ≺ β we have that σβ
′
α ≤ σβα and
β ∈ V (Gβα) ∩ V (Γβα);
(2γ) for every β ∈ A⪯γ , the graphs Γβα : α ⪯ β are pairwise edge-disjoint, and the edge
eβ belongs to their union;
(3γ) for every α, β ∈ A⪯γ , the graph Γβα is either finite or |A⪯γ |-bounded.
The desired factorization of Kℵ is then G = {Γα : α ∈ A}, where Γα =
⋃
β∈A Γ
β
α for
every α ∈ A. Indeed, property (1γ) guarantees that each Γα is a factor of Kℵ isomorphic
to Fα. Also, property (2γ) ensures that the Γαs are pairwise edge-disjoint and between
them contain all the edges of Kℵ.
We proceed by transfinite induction on γ.
BASE CASE. Let 0 = minA, choose an edge e ∈ E(F0) and let σ ∈ Σℵ(F0,Kℵ) be
the embedding that maps e to e0. By Lemma 3.1, there exists an embedding σ00 : G
0
0 → Γ00
in Σℵ(F0,Kℵ) such that Γ00 is a finite graph and
σ ≤ σ00 and 0 ∈ V (G00) ∩ V (Γ00).
Clearly, E0 := {σ00} satisfies properties (10), (20) and (30).
TRANSFINITE INDUCTIVE STEP. We assume that, for any γ′ ≺ γ, there is a family
Eγ′ satisfying properties (1γ′), (2γ′ ) and (3γ′ ), and prove that it can be extended to a family
Eγ that satisfies properties (1γ), (2γ) and (3γ). Clearly it is enough to provide the maps σβα
where either α = γ or β = γ.
We start by constructing the maps σγα for every α ≺ γ. We proceed by transfinite
induction on α.
• Base case. Set Θ0 :=
⋃
α,β≺γ Γ
β
α and note that, by property (3γ′ ), Θ0 is ℵ-small.
We also set σ≺γ0 :
⋃
β≺γ G
β
0 →
⋃
β≺γ Γ
β
0 to be the map of Σℵ(F0,Kℵ \Θ0) whose
restriction to Gβ0 is σ
β
0 . We note that property (3γ′ ) guarantees that the order of⋃
β≺γ G
β
0 is either finite or |A⪯γ |-bounded, hence ℵ-small.
Therefore, we can apply Lemma 3.1 (with σ = σ≺γ0 ) to obtain the map σ
γ
0 : G
γ
0 →
Γγ0 in Σℵ(F0,Kℵ \ Θ0) such that |V (Γ
γ
0)| ≤ |V (
⋃
β≺γ Γ
β
0 )| + 2 and, for every
γ′ ≺ γ,
σγ
′
0 ≤ σ
γ
0 and γ ∈ V (G
γ
0) ∩ V (Γ
γ
0).
10 Ars Math. Contemp. 24 (2024) #P1.02
• Inductive step. Assume we have defined the maps σγα′ for every α
′ ≺ α, and set
Θα :=
⋃
α′≺α
Γγα′ ∪
⋃
α≺α′≺γ,β≺γ
Γβα′ .
As before, by Lemma 3.1 there exists σγα : G
γ
α → Γγα in Σℵ(Fα,Kℵ \Θα) such that
|V (Γγα)| ≤ |V (
⋃
β≺γ Γ
β
α)|+ 2 and, for every γ′ ≺ γ,
σγ
′
α ≤ σγα and γ ∈ V (Gγα) ∩ V (Γγα).
Finally, we define the maps σβγ when β ⪯ γ. We set Θ :=
⋃
α≺γ Γ
γ
α and proceed by
transfinite induction on β.
• Base case. If eγ ∈ Θ, let σ be the empty map of Σℵ(Fγ ,Kℵ \Θ). Otherwise, chose
an edge e ∈ E(Fγ), and let σ ∈ Σℵ(Fγ ,Kℵ \ Θ) be the embedding that maps e to
eγ . By Lemma 3.1, there exists σ0γ : G
0
γ → Γ0γ in Σℵ(Fγ ,Kℵ \Θ) such that Γ0γ is a
finite graph and
σ ≤ σ0γ and 0 ∈ V (G0γ) ∩ V (Γ0γ).
• Inductive step. Assume we have defined the maps σβ
′
γ for any β
′ ≺ β. Again by
Lemma 3.1, there exists σβγ : G
β
γ → Γβγ in Σℵ(Fγ ,Kℵ \ Θ) such that |V (Γβγ )| ≤
|V (
⋃
β′≺β Γ
β′
γ )|+ 2 and, for any β′ ≺ β,
σβ
′
γ ≤ σβγ and β ∈ V (Gβγ ) ∩ V (Γβγ ).
It follows from the construction that the family
Eγ := {σβα : Gαβ → Γβα | σβα ∈ Σℵ(Fα,Kℵ), α, β ⪯ γ}
satisfies properties (1γ), (2γ) and (3γ).
Assuming that GCH holds, we obtain Theorem 2.9 as a corollary to Theorem 1.4.
Theorem 2.9. Let F be a family of graphs of order ℵ and assume that |F| = ℵ. Then
FP (F , Rℵ) has a solution if and only if the domination number of each graph in F is ℵ.
Proof. By property ⋆ℵ, one can easily check that Rℵ is self-complementary, that is Kℵ\Rℵ
is isomorphic to Rℵ, and the domination number of the ℵ-Rado graph is ℵ. Therefore, the
domination number of each graph of F must be ℵ.
To prove sufficiency, note that F ′ := F∪{Rℵ} satisfies the hypothesis of Theorem 1.4.
Therefore FP (F ′) admits a solution. This means that F factorizes Kℵ \Rℵ ≃ Rℵ.
4 The factorization problem for k-stars
Theorem 1.4 does not provide solutions to FP (F ) whenever the graph F has a dominating
set of cardinality less than its order. In particular, if F is countable with a finite dominating
set, then the existence of a solution to FP (F ) is an open problem. In this section, we
consider a special class of such graphs, the k-stars Sk. More precisely,
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 11
• the star S1, which we also call a 1-star, is the graph with vertex-set N whose edges
are of the form {0, i} for every i ∈ N \ {0};
• the k-star Sk is the vertex-disjoint union of k stars.
Note that Sk contains exactly k vertices of infinite degree, which we call centers and form
a finite dominating set of Sk.
In the following, we show that FP (Sk) has no solution whenever k ∈ {1, 2}, while it
admits a solution for every k > 3. Unfortunately, we leave open the problem for 3-stars.
4.1 The case k ∈ {1, 2}
Proposition 4.1. FP (S1) has no solution.
Proof. Assume for a contradiction that there is a factorization G of KN into 1-stars. Choose
any star Γ ∈ G and let g denote its center. Note that all the edges of KN incident with g
belong Γ. By recalling that G is a factorization of KN (and that a 1-star has no isolated
vertices), it follows that g cannot be a vertex in any other star of G. Therefore, every star of
G \ {Γ} is not spanning, contradicting the assumption.
With essentially the same proof, one obtains the following.
Remark 4.2. Let F be the vertex-disjoint union of S1 with a finite set of isolated vertices.
Then FP (F ) has no solution.
To prove the non-existence of a solution to FP (S2) it will be useful the following
lemma.
Lemma 4.3. If G is a factorization of KN into k-stars, then there is at most one vertex of
KN that is never a center in any k-star of G. It follows that |G| = |N|.
Proof. It is enough to notice that every pair {a, b} of vertices of KN is the edge of some
2-star Γ of G; hence, either a or b is a center of Γ.
Proposition 4.4. FP (S2) has no solution.
Proof. Assume for a contradiction that there is a factorization G of KN into 2-stars. For
every Γ ∈ G, letting c be a center of Γ, we denote by Γ(c) the set of vertices adjacent with
c in Γ (i.e., the neighborhood of c in Γ).
Choose any 2-star Γ ∈ G and let a and b denote its centers. Also, let Γ′ be the 2-star of
G \ {Γ} containing the edge {a, b}. Without loss of generality, we can assume that a is a
center of Γ′. Finally, by Lemma 4.3, we can choose x ∈ Γ′(a) \ {b} such that there exists
a 2-star Γ′′ ∈ G having x as one of its centers.
Since Γ is a factor of KN, it follows that x ∈ Γ(b). In other words, Γ ∪ Γ′ contains the
edges {x, a} and {x, b}. Therefore, a, b ̸∈ Γ′′(x). Since Γ′′ is a factor of KN and {a, b}
is an edge of Γ, it follows a, b ∈ Γ′′(y), where y is the other center of Γ′′. In other words,
{y, a} and {y, b} belong to Γ′′, hence y cannot lie in Γ, contradicting the fact that Γ is a
factor.
12 Ars Math. Contemp. 24 (2024) #P1.02
4.2 The case k ≥ 4
In this section we prove the solvability of FP (Sk) whenever k ≥ 4. For our constructions
we need to introduce the following notation.
Let D be an integral domain and set V = D × {0, 1, . . . , h}, for h ≥ 0. For the sake
of brevity, we will denote each pair (a, i) ∈ V by ai. Given a graph Γ with vertices in V ,
for every a, b ∈ D we denote by aΓ + b the graph obtained by replacing each vertex xi of
Γ with (ax+ b)i; further, if {xi, yi} is an edge of Γ, then {(ax+ b)i, (ay+ b)i} is an edge
of aΓ + b. Also, we denote by OrbD(Γ) = {Γ + d : d ∈ D} the D-orbit of Γ, that is, the
set of all translates of Γ by the elements of D.
Proposition 4.5. For every k ≥ 4, there exists a k-star Γ with vertex set V = Z × {0, 1}
such that OrbZ(Γ) is a factorization of KV into k-stars.
Proof. We first deal with the case k = 4. Set Γ =
⋃4
i=1 Γi, where each Γi is the 1-star
with vertices in V = Z× {0, 1} and center xi defined as follows (see Figure 1):
• x1 = 00 and Γ1(x1) = {i0 : i ≥ 1};
• x2 = −11 and Γ2(x2) = {i1 : i ≥ 0} ∪ {−10};
• x3 = −20 and Γ2(x3) = {i1 : i ≤ −3};
• x4 = −21 and Γ4(x4) = {i0 : i ≤ −3}.
−61
−60
−51
−50
−41
−40
−31
−30
−21
−20
01
00
11
10
21
20
31
30
41
40
−11
−10
Γ1
Γ2
Γ3 ∪ Γ4
Figure 1: The graph Γ when k = 4.
We claim that G := OrbZ(Γ) is a factorization of KV into 4-stars. Denote by KU,W the
complete bipartite graph whose parts are U = Z × {0} and W = Z × {1}, and consider
the 1-factor I = {{i0, i1} : i ∈ Z} of KU,W . Clearly, KV decomposed into KU , KW ∪ I
and KU,W \ I . One can check that
• OrbZ(Γ1) decomposes KU ,
• OrbZ(Γ2) decomposes KW ∪ I , and
• OrbZ(Γ3 ∪ Γ4) decomposes KU,W \ I .
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 13
Γ1
Γ′1,2
∆0
∆∗1
00 10 20 30 40 50 60 70 80
00 10 20 40 60 80
30 50 70
Figure 2: Replacing Γ1 with Γ′1,2 produces Γ when k = 5.
Hence, G is a decomposition of KV . Considering that the Γis are pairwise vertex-
disjoint and their vertex-sets partition V , we have that Γ and each of its translates (under
the action of Z) are factors of KV isomorphic to a 4-star. Therefore, G is a factorization of
KV into 4-stars.
To deal with the case k ≥ 5, it is enough to replace the component Γ1 of Γ with a
(k − 3)-star Γ′1 satisfying the following conditions:
V (Γ′1) = V (Γ1), and (4.1)
OrbZ(Γ
′
1) decomposes KU . (4.2)
Indeed, letting Γ′ = (Γ \ Γ1) ∪ Γ′1, by condition (4.1) we have that Γ′ is a k-star with
vertex-set V . Recalling that OrbZ(Γ1) decomposes KU , by condition (4.2) it follows that
OrbZ(Γ
′) and OrbZ(Γ) decompose the same graph, that is, KV . Hence, OrbZ(Γ′) is a
factorization of KV into k-stars.
Let k = h + 3 with h ≥ 2. It is left to construct an h-star Γ′1,h satisfying conditions
(4.1) and (4.2), for every h ≥ 2. For sake of clarity, in the rest of the proof we identify
U = Z× {0} with Z. Therefore, Γ1 is the 1-star centered in 0 with Γ1(0) = {i : i ≥ 1}.
Let ∆j and ∆∗j be the 1-stars centered in cj = 2(2
j − 1) such that
∆j(cj) = {cj + i : 0 < i ≡ 2j (mod 2j+1)},
∆∗j (cj) = {cj + i : 0 < i ≡ 0 (mod 2j)},
for j ≥ 0, and set Γ′1,h = ∆0 ∪ ∆1 ∪ . . . ∪ ∆h−2 ∪ ∆∗h−1 for h ≥ 2. It is not difficult
to check that {∆j − cj : 0 ≤ j ≤ h− 2} ∪ {∆∗h−1 − ch−1} decomposes Γ1. Therefore,
OrbZ(Γ
′
1,h) and OrbZ(Γ1) decompose the same graph, that is, KU . Hence, Γ
′
1,h satisfies
condition (4.2).
We show that Γ′1,h is an h-star satisfying condition (4.1) by induction on h. If h = 2,
then V (∆0) = {0, 1, 3, 5, . . .} and V (∆∗1) = {2, 4, 6, . . .}. Therefore, Γ′1,2 = ∆0 ∪ ∆∗1 is
14 Ars Math. Contemp. 24 (2024) #P1.02
a 2-star with the same vertex-set as Γ1. Now assume that Γ′1,h is an h-star satisfying condi-
tion (4.1) for some h ≥ 2. Recalling the definition of Γ′1,h and Γ′1,h+1, and considering that
the vertex-sets of ∆h−1 and ∆∗h partition V (∆
∗
h−1), we have that Γ
′
1,h+1 is an (h+1)-star
with the same vertex-set as Γ′1,h, that is, V (Γ1), and this concludes the proof.
Propositions 4.1, 4.4 and 4.5 leave open FP (Sk) only when k = 3. In this case, an
approach similar to Theorem 4.5 cannot work, as shown in the following.
Proposition 4.6. There is no 3-star Γ with vertex-set V = Z× {0, 1, . . . , k} such that the
Z-orbit of Γ is an S3-factorization of KV .
Proof. Assume for a contradiction that there exists a 3-star Γ with vertex-set V = Z ×
{0, 1, . . . , k} such that G = OrbZ(Γ) is a factorization of KV .
We first notice that Γ must have at least a center in Z×{i}, for every i ∈ {0, 1, . . . , k}.
Indeed, if Γ has no center in Z × {i} for some i ∈ {0, 1, . . . , k}, then no edge of KZ×{i}
can be covered by G. Since Γ has 3 centers, it follows that k ≤ 2. Note that if k = 2,
the centers of Γ must be x0, y1, z2 for some x, y, z ∈ Z, but in this case the edge {x0, y1}
cannot lie in any translate of Γ. Therefore k ≤ 1.
If k = 1, without loss of generality we can assume that the centers of Γ are 00, x1 and
y1 with x ̸= y. Since the edge {00, x1} does not belong to Γ, it lies in some of its translates,
say Γ + z with z ̸= 0. This is equivalent to saying that {(−z)0, (x− z)1} ∈ Γ. It follows
that x− z = y, hence {(y−x)0, y1} ∈ Γ. Similarly, we can show that {(x− y)0, x1} ∈ Γ.
It follows that Γ cannot contain the edges {00, (x− y)0} and {00, (y − x)0}. This implies
that no edge of the form {w0, (x− y + w)0} lies in any translate of Γ, contradicting again
the assumption that G is a factorization of KV . Therefore k = 0.
Let V = Z and denote by ∆Γ the multiset of all differences y − x between any two
adjcent vertices x and y of Γ, with x < y:
∆Γ = {y − x : {x, y} ∈ E(Γ), x < y}.
It is not difficult to see that G = OrbZ(Γ) is a factorization of KZ if and only if ∆Γ =
N \ {0}. Denoting by Γ + i the translate of Γ obtained by replacing each vertex x ∈ V (Γ)
with x + i, one can easily see that ∆(Γ + i) = ∆Γ for every i ∈ Z. Therefore, up to
a translation, we can assume that the centers of Γ are 0, x, n with 0 < x < n. Now,
for every i ≥ n, denote by Γi the induced subgraph of Γ with vertex-set {0, 1, . . . , i}.
Also, let Γ∗ be the induced subgraph of Γ on the vertices {−3,−2,−1, 0, x, n}. Clearly,
|∆Γ∗| = 3, |∆Γi| = i− 2 and ∆Γi ⊂ {1, 2, . . . , i}. Also, since the multiset ∆Γ contains
all positive integers with no repetition, it follows that ∆Γ∗ and ∆Γi are disjoint, hence
∆Γi ⊂ {1, 2, . . . , i} \ ∆Γ∗ for every i ≥ n. Then, for i = max(∆Γ∗), we obtain the
following contradiction: i− 2 = |∆Γi| ≤ |{1, 2, . . . , i} \∆Γ∗| = i− 3.
5 The resolvability problem
Theorem 1.4 allows us to construct decompositions of Kℵ into ℵ graphs of specified type.
More precisely, we have the following.
Corollary 5.1. Let F = {Fα : α ∈ A} be an infinite family of (non-empty) ℵ-bounded
graphs, where ℵ = |A|. Then there exists a decomposition G = {Γα : α ∈ A} of Kℵ such
that each Γα is isomorphic to Fα.
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 15
Furthermore, for any β ∈ A such that the domination number of Fβ is less than ℵ, we
have that |V (Kℵ) \ V (Γβ)| = ℵ. Otherwise, for every 0 ⪯ ℵ′ ⪯ ℵ, the decomposition G
can be constructed so that |V (Kℵ) \ V (Γβ)| = ℵ′.
Proof. For every α ∈ A, set ℵα = ℵ if the domination number of Fα is less than ℵ;
otherwise, let 0 ⪯ ℵα ⪯ ℵ. By adding to each graph Fα a set of ℵα isolated vertices we
obtain a graph F ′α whose order and domination number are ℵ. Since the assumptions of
Theorem 1.4 are satisfied, there exists a factorization G′ = {Γ′α : α ∈ A} of Kℵ such that
each Γ′α is isomorphic to F
′
α. By replacing Γ
′
α with the isomorphic copy of Fα, we obtain
the desired decomposition G.
Inspired by [9], we ask under which conditions a decomposition G of Kℵ is resolvable,
namely, its graphs can be partitioned into factors of Kℵ, also called resolution classes. It
follows that a resolvable decomposition G of Kℵ must satisfy the following two conditions:
N1. if Γ ∈ G is not a factor of Kℵ, then |V (Kℵ) \ V (Γ)| ≥ min{|Γ| : Γ ∈ G};
N2.
G(z) ⊆ G(x) ∪ G(y) ⇒ G(z) ⊇ G(x) ∩ G(y),
where G(v) = {Γ ∈ G : v ∈ V (Γ)} is the set of all graphs of G passing through v.
In the following, we easily construct decompositions of Kℵ that do not satisfy the above
conditions, and therefore they are non-resolvable.
Example 5.2. Let F = {Fα : α ∈ A} be an infinite family of (non-empty) ℵ-bounded
graphs, where ℵ = |A|. Also, assume that the domination number of at least one of its
graphs, say Fβ , is ℵ. Then, by applying Corollary 5.1 with ℵ′ ≺ min{|Γα| : α ∈ A}, we
construct a decomposition that does not satisfy condition N1.
For instance, if ℵ = |N|, each Fα is a countable locally finite graph (hence, its dom-
ination number is ℵ) and ℵ′ = 1 for every β ∈ N, then we construct a decomposition
G = {Gβ : β ∈ N} of KN into connected regular graphs where V (Gβ) = N \ {xβ} for
some xβ ∈ N. Clearly, no graph of G is a factor of KN, and any two graphs of G have
common vertices. Therefore, G is not resolvable.
Example 5.3. Let G be any decomposition of the infinite complete graph KV (for example,
one of those constructed by Corollary 5.1). Let y and z be vertices not belonging to KV
and set W = V ∪ {y, z}. We can easily extend G to a non-resolvable decomposition G′
of KW in the following way.
Choose x ∈ V and let C be the following family of paths of length 1 or 2:
C = {[y, v, z] : v ∈ V \ {x}} ∪ {[x, z, y], [x, y]}.
Clearly, C decomposes KW \KV , hence G′ = G ∪ C is a decomposition of KW . Also,
x, y and z do not satisfy condition N2, since G′(z) ⊆ G′(x) ∪ G′(y), while [x, y] belongs
to G′(x) ∩ G′(y), but not to G′(z). Therefore, G′ is non-resolvable. Indeed, any resolution
class of G′ could cover the vertex z only with graphs passing through x or y. This means
that the graph [x, y] cannot belong to any resolution class of G′.
The following result provides sufficient conditions for a decomposition G to be resolv-
able.
16 Ars Math. Contemp. 24 (2024) #P1.02
Theorem 5.4. Let G be a decomposition of the infinite complete graph Kℵ satisfying the
following properties for some ℵ′ ≺ ℵ:
R1. each graph in G is ℵ′-bounded;
R2. |G(x) ∩ G(y)| ⪯ ℵ′ for every distinct x, y ∈ V (Kℵ).
Then G is resolvable.
Proof. Let G = {Gα : α ∈ A}. We consider a well-order ≺ on A satisfying Corollary 3.4.
Since the graphs of G are ℵ′-bounded, we have that |A| = ℵ and we can assume V (Kℵ) =
A. Here we need to construct an ascending chain (Gγ)γ∈A of families Gγ := {Γγα :
α ∈ A⪯γ} (where Γγ
′
α is a subgraph of Γ
γ
α whenever γ
′ ⪯ γ) that satisfy the following
proprieties:
(1γ) each Γγα is a vertex-disjoint union of graphs of G;
(2γ) for every α ∈ A⪯γ , γ ∈ V (Γγα);
(3γ) Gγ is contained in exactly one Γγα where α ∈ A⪯γ ;
(4γ) for every α ∈ A⪯γ , Γγα is either a finite graph or (ℵ′ · |A⪯γ |)-bounded.
The desired resolution of Kℵ is then R = {Γα : α ∈ A}, where Γα =
⋃
γ∈A Γ
γ
α for
every α ∈ A. Indeed, due to properties (1γ) and (2γ), each Γα is a resolution class of G
and, by property (3γ), R is a partition of G into resolution classes.
We proceed by transfinite induction on γ.
BASE CASE. Let 0 = minX . By condition R2, if 0 is not a vertex of G0, |G(0) ∩
G(x)| ⪯ ℵ′ for any x ∈ V (G0). Since, due to condition R1, |G(0)| = ℵ, there exists
G ∈ G(0) disjoint from G0. Therefore we can define G0 = {Γ00} where Γ00 is either G0∪G
or, if 0 belongs to V (G0), G0.
TRANSFINITE INDUCTIVE STEP. For every γ′ ≺ γ, we assume there is a family
Gγ′ satisfying (iγ′) for 1 ≤ i ≤ 4. We show that Gγ′ can be extended to a family Gγ that
satisfies the same properties, (iγ) for 1 ≤ i ≤ 4.
We are going to define, recursively, the graphs Γγα whenever α ⪯ γ. First, we consider
the case α ≺ γ. We start by setting Γ≺γα :=
⋃
γ′≺γ Γ
γ′
α . Note that property (4γ′ ) guarantees
that Γ≺γα is either finite or |Γ≺γα | ⪯ ℵ′ · |A⪯γ |; hence, Γ≺γα is ℵ-small.
• Base case. If γ ∈ V (Γ≺γ0 ), set Γ
γ
0 = Γ
≺γ
0 .
If γ ̸∈ V (Γ≺γ0 ), by condition R2 we have |G(γ)∩G(x)| ⪯ ℵ′ for every x ∈ V (Γ
≺γ
0 ).
Since Γ≺γ0 is ℵ-small, this means that the family of graphs of G(γ) that intersect
V (Γ≺γ0 ) is ℵ-small.
Moreover, any Γ≺γα is either finite or (ℵ′ · |A⪯γ |)-bounded (note that ℵ′ · |A⪯γ | ≺ ℵ,
since |A⪯γ | ≺ ℵ). Hence, the set of graphs in G(γ) that are contained in some Γ≺γα
is ℵ-small.
Finally, by condition R1, we have that |G(γ)| = ℵ. Therefore, there exists a graph
G ∈ G(γ) that is not contained in any Γ≺γα and such that V (G) ∩ V (Γ
≺γ
0 ) = ∅.
Then, we set Γγ0 = Γ
≺γ
0 ∪G.
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 17
• Recursive step. Let α ≺ γ. If γ ∈ V (Γ≺γα ), set Γγα = Γ≺γα . Otherwise, by proceed-
ing as in the previous case, we obtain the existence of a graph G ∈ G(γ) that is not in
any Γ≺γα′ or any Γ
γ
α′′ (where α
′ ≺ γ and α′′ ≺ α), and such that V (G)∩V (Γ≺γα ) = ∅.
In this case, we set Γγα = Γ
≺γ
α ∪G.
It is left to define Γγγ . We proceed by constructing, recursively, an ascending chain of
graphs Γαγ , for α ∈ A⪯γ , that are either finite or (ℵ′ · |A⪯γ |)-bounded.
• Base case. Let us first suppose that Gγ is not contained in any Γ
γ
α′ (where α
′ ≺ γ).
Again, by conditions R1 and R2, there exists G ∈ G(0) that is also not contained in
any Γγα′ such that G is either Gγ or is disjoint from Gγ . We set Γ
0
γ to be Gγ ∪ G.
Otherwise, we set Γ0γ to be any graph G in G(0) that is not contained in any Γ
γ
α′ .
• Recursive step. Let us suppose that α ̸= 0 and that we have defined Γα′γ for every
α′ ≺ α. Here we set Γ≺αγ to be
⋃
α′≺α Γ
α′
γ . Note that, by construction, Γ
≺α
γ is
either a finite graph or |Γ≺αγ | ⪯ ℵ′ · |A⪯γ |. If α belongs to V (Γ≺αγ ), we set Γαγ to
be Γ≺αγ . Otherwise, proceeding as in the previous case, we obtain that there exists
G ∈ G(α) disjoint from Γ≺αγ that does not belong to any of the Γ
γ
α′ . Now we set Γ
α
γ
to be G ∪ Γ≺αγ .
Then the family Gγ = {Γγα : α ∈ A⪯γ} satisfies the properties (1γ), (2γ), (3γ) and (4γ) by
construction.
Remark 5.5. A cardinal ℵ is said to be regular if any ℵ-small union of ℵ-small sets (resp.
graphs) is still an ℵ-small set (resp. graph) otherwise it is said to be singular. It is easy to
see that, for regular cardinals, conditions R1 and R2 of Theorem 5.4 can be relaxed to:
R1’. each graph in G is ℵ-small;
R2’. |G(x) ∩ G(y)| ≺ ℵ for every distinct x, y ∈ V (Kℵ).
However, if ℵ is a singular cardinal, then conditions R1’ and R2’ are no longer sufficient.
Indeed, we can construct a decomposition G of Kℵ into ℵ-small graphs such that
a. |G| is ℵ-small,
b. G satisfies conditions R1’ and R2’,
c. there are two (possibly isolated) vertices x and y belonging to every graphs of G, that
is, G = G(x) ∩ G(y).
Then, choosing any vertex z such that G(z) ̸= G, we have that
G(z) ⊆ G(x) ∪ G(y) = G but G(z) ̸⊇ G(x) ∩ G(y) = G.
This means that condition N2 does not hold, therefore the decomposition G is not resolv-
able.
We conclude by showing that there is always a resolution for an ‘almost’ 2-design with
blocks that are ℵ′-bounded for some ℵ′ ≺ ℵ, that is, a decomposition of Kℵ whose graphs
are almost all ℵ′-bounded complete graphs. This extends some results on the resolvability
of 2-designs given in [9].
18 Ars Math. Contemp. 24 (2024) #P1.02
Proposition 5.6. Let G be a decomposition of the infinite complete graph Kℵ into ℵ′-
bounded graphs for some ℵ′ ≺ ℵ, where ℵ′ is not necessarily infinite. If the subset of G
consisting of all non-complete graphs is ℵ′-bounded, then G has a resolution.
Proof. By assumption, condition R1 of Theorem 5.4 holds. To prove that G satisfies con-
dition R2 for some ℵ′′ ≺ ℵ, we assume for a contradiction the existence of vertices x and y
such that |G(x) ∩ G(y)| ≻ ℵ′′ := (ℵ′ + 1). It follows that there are at least two complete
graphs in G(x) ∩ G(y), meaning that the edge {x, y} is covered more than once by graphs
in G, and this is a contradiction. The assertion follows from Theorem 5.4.
ORCID iDs
Simone Costa https://orcid.org/0000-0003-3880-6299
Tommaso Traetta https://orcid.org/0000-0001-8141-0535
References
[1] A. Beutelspacher and P. J. Cameron, Transfinite methods in geometry, volume 1, pp. 337–
347, 1994, doi:10.36045/bbms/1103408579, a tribute to J. A. Thas (Gent, 1994), https:
//doi.org/10.36045/bbms/1103408579.
[2] S. Bonvicini and G. Mazzuoccolo, Abelian 1-factorizations in infinite graphs, Eur. J. Comb.
31 (2010), 1847–1852, doi:10.1016/j.ejc.2010.01.012, https://doi.org/10.1016/j.
ejc.2010.01.012.
[3] P. J. Cameron, Infinite versions of some topics in finite geometry, in: Geometrical Combina-
torics, Pitman, Boston, MA, volume 114 of Res. Notes in Math., pp. 13–20, 1984.
[4] P. J. Cameron, Note on large sets of infinite Steiner systems, J. Comb. Des. 3 (1995), 307–311,
doi:10.1002/jcd.3180030408, https://doi.org/10.1002/jcd.3180030408.
[5] P. J. Cameron, The random graph, in: The Mathematics of Paul Erdős, II, Springer, Berlin,
volume 14 of Algorithms Combin., pp. 333–351, 1997, doi:10.1007/978-3-642-60406-5\ 32,
https://doi.org/10.1007/978-3-642-60406-5_32.
[6] P. J. Cameron and B. S. Webb, Perfect countably infinite Steiner triple systems, Australas.
J. Comb. 54 (2012), 273–278, https://ajc.maths.uq.edu.au/pdf/54/ajc_v54_
p273.pdf.
[7] K. M. Chicot, T. S. Griggs, M. J. Grannell and B. S. Webb, On sparse countable infinite steiner
triple systems, J. Comb. Des. 18 (2010), 115–122, doi:10.1002/jcd.20227, https://doi.
org/10.1002/jcd.20227.
[8] S. Costa, A complete solution to the infinite Oberwolfach problem, J. Comb. Des. 28 (2020),
366–383, doi:10.1002/jcd.21702, https://doi.org/10.1002/jcd.21702.
[9] P. Danziger, D. Horsley and B. S. Webb, Resolvability of infinite designs, J. Comb. Theory Ser.
A 123 (2014), 73–85, doi:10.1016/j.jcta.2013.11.005, https://doi.org/10.1016/j.
jcta.2013.11.005.
[10] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer, Berlin, 5th
edition, 2017.
[11] F. Franek, Isomorphisms of infinite Steiner triple systems, Ars Comb. 38 (1994), 7–25.
[12] M. J. Grannell, T. S. Griggs and J. S. Phelan, Countably infinite Steiner triple systems, Ars
Comb. 24 (1987), 189–216.
S. Costa and T. Traetta: Factorizing the Rado graph and infinite complete graphs 19
[13] M. J. Grannell, T. S. Griggs and J. S. Phelan, On infinite Steiner systems, Discrete Math. 97
(1991), 199–202, doi:10.1016/0012-365X(91)90435-5, https://doi.org/10.1016/
0012-365X(91)90435-5.
[14] E. Köhler, Unendliche gefaserte Steiner systeme, J. Geom. 9 (1977), 73–77, doi:10.1007/
bf01918060, https://doi.org/10.1007/bf01918060.
[15] R. W. Quackenbush, Algebraic speculations about Steiner systems, Ann. Discrete Math.
7 (1980), 25–35, doi:10.1016/S0167-5060(08)70168-7, https://doi.org/10.1016/
S0167-5060(08)70168-7.
[16] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340, doi:10.4064/
aa-9-4-331-340, https://doi.org/10.4064/aa-9-4-331-340.