Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2005). pp. 84 – 91
c© Journal “Algebra and Discrete Mathematics”
Color-detectors of hypergraphs
I. V. Protasov, O. I. Protasova
Communicated by V. M. Usenko
Dedicated to Yu.A. Drozd on the occasion of his 60th birthday
Abstract. Let X be a set of cardinality k, F be a family of
subsets of X. We say that a cardinal λ, λ < k, is a color-detector of
the hypergraph H = (X,F) if card χ(X) ≤ λ for every coloring χ :
X → k such that card χ(F ) ≤ λ for every F ∈ F . We show that the
color-detectors of H are tightly connected with the covering number
cov (H) = sup{α : any αpoints of X are contained in some F ∈
F}. In some cases we determine all of the color-detectors of H and
their asymptotic counterparts. We put also some open questions.
Let X be a set, F be a family of subsets of X. The pair H = (X,F)
is called a hypergraph with the set of vertices X and the set of edges F .
We suppose that ⋃F = X.
Let λ be a cardinal such that 0 < λ < k = card X. A coloring
χ : X → k is called λ-admissible if card χ(F ) ≤ λ for every F ∈ F . We
put
æ(H,λ) = sup{card χ(X) : χ is a λ− admissible coloring of X}.
Clearly, æ(H,λ) ≥ λ. If æ(H,λ) = λ, we say that λ is a detector of H.
If λ is a detector of H, then there exists F ∈ F such that card F > λ
(because, otherwise, a bijective coloring χ : X → k is λ-admissible and
χ(X) = k > λ).
Proposition 1. A cardinal λ is a detector of H if and only if, for every
surjective coloring χ : X → λ+, were λ+ is the cardinal-successor of λ,
there exists F ∈ F such that card χ(F ) = λ+.
2000 Mathematics Subject Classification: 05C15.
Key words and phrases: hypergraph, color-detector, covering number.
I. V. Protasov, O. I. Protasova 85
Proof. Let æ(H,λ) = λ and let χ : X → λ+ be a surjective coloring.
Then χ is not λ-admissible, so there exists F ∈ F such that card F = λ+.
Assume that æ(H,λ) > λ and choose a λ-admissible coloring χ :
X → k such that card χ(X) > λ. Identifying some colors, we get a
surjective λ-admissible coloring χ′ : X → λ+, so card χ′(F ) ≤ λ for every
F ∈ F .
We define the covering number of H as
cov(H) = sup{γ : for every Y ⊆ X with card Y ≤ γ
there exists F ∈ F such that Y ⊆ F}.
Proposition 2. If cov (H) ≥ λ+, then λ is a detector of H.
Proof. Let χ : X → λ+ be a surjective coloring. Choose Y ⊆ X such
that card Y = card χ(Y ) = λ+. Since cov(H) ≥ λ+, we can choose
F ∈ F such that Y ⊆ F . Then card χ(F ) = λ+. By Proposition 1, λ is
a detector of H.
Proposition 3. If a natural number m is a detector of H, then cov
(H) ≥ m.
Proof. We fix an arbitrary m-subset Y = {y0, ..., ym−1} of X and put
χ(yi) = i and χ(x) = m for every x ∈ X \ Y . Since m is a detector,
by Proposition 1, there exists F ∈ F such that card χ(F ) = m + 1. It
follows that Y ⊆ F , so cov (H) ≥ m.
Proposition 4. If a natural number m is a detector of H and m′ < m,
then m′ is a detector of H.
Proof. Assume, otherwise, and fix a surjective coloring χ : X → m′ + 1
such that card χ(F ) ≤ m′ for every F ∈ F (see Proposition 1). Since
m′ + 1 < k, there exist two elements a, b ∈ X such that χ(a) = χ(b).
We define the new coloring χ′ : X → m′ + 2 such that χ′(x) = χ(x) for
every x ∈ X \ {a}, and χ′(a) = m′ + 1. Then card χ′(F ) ≤ m′ + 1 for
every F ∈ F , but card χ′(X) = m′ + 2, so m′ + 1 is not a detector of
H. Repeating the arguments, we conclude that m is not a detector of H,
whence a contradiction.
The following example shows that the finiteness assumption for m can
not be omitted in Propositions 3 and 4.
Example 1. Let Y, Z be disjoint infinite sets, card Y = k, card Z = λ
and λ < k. We put X = Y ⋃Z and Fz = Y
⋃{z} for every z ∈ Z.
Then we consider the hypergraph H = (X,F), where F = {Fz : z ∈ Z}.
86 Color-detectors of hypergraphs
Clearly, cov (H) = 1, λ is a detector of H, but every cardinal λ′ such
that 1 < λ′ < λ is not a detector of H.
For every hypergraph H = (X,F), we consider the graph Γ(H) of
intersections of H with the set of vertices X and the set of edges defined
by the rule: (x1, x2) ∈ X ×X is an edge if and only if x1 6= x2 and there
exist F1, F2 ∈ F such that x1 ∈ F1, x2 ∈ F2 and F1
⋂F2 6= ∅.
Proposition 5. For every hypergraph H = (X,F), 1 is a detector of H
if and only if the graph Γ(H) is connected.
Proof. Assume that Γ(H) is connected and take an arbitrary coloring
χ : X → k such that card χ(F ) = 1 for every F ∈ F . Given any x, y ∈ X,
we choose a path x1, x2, ..., xn in Γ(H) such that x = x1, y = xn. Then
χ(x1) = χ(x2) = ... = χ(xn), so χ(x) = χ(y).
If Γ(H) is not connected, we take a connected component Y of Γ(H)
and, for every x ∈ X, we put
χ(x) =
{
0, if x ∈ Y ;
1, if x ∈ X \ Y ;
Then the coloring χ is 1-admissible, but card χ(X) > 1.
Proposition 6. If H = (X,F) is a graph and card X > 1, then the only
possible detector of H is 1, and 1 is a detector of H if and only if H is
connected.
Proof. We fix a bijection χ : X → k. Since card χ(F ) = 2 for every
F ∈ F , χ is λ-admissible for every λ ≥ 2. It follows that if 1 < λ < k,
then λ is not a detector of H. On the other hand, by Proposition 5, 1 is
a detector of H if and only if Γ(H) is connected. It is easy to see that
Γ(H) is connected if and only if H is connected.
Let Γ = (V,E) be a connected graph with the set of vertices V and
the set of edges E. For any u, v ∈ V , we denote by d(u, v) the length
of a shortest path between u and v. Given any u ∈ V , r ∈ N, we put
Bd(u, r) = {v ∈ V : d(u, v) ≤ r}. Let B be the family of all unit balls in
Γ. Call the hypergraph H = (V,B) to be the ball hypergraph of Γ. By
Proposition 5, 1 is a detector of H.
Problem 1. Given a natural number n > 1, characterize the class τn of
connected graphs such that Γ ∈ τn if and only if n is a detector of the ball
hypergraph of Γ.
I. V. Protasov, O. I. Protasova 87
For every natural number n > 1, we denote by Cn the class of all
connected graphs such that Γ ∈ Cn if and only if V (Γ) ≥ n + 1 and any
≤ n vertices of Γ are contained in some unit ball in Γ. Note that C2 is the
class of graphs of diameter ≤ 2, where diam Γ = sup{d(u, v) : u, v ∈ V }.
By Propositions 2 and 3, we have
C2 ⊇ τ2 ⊇ C3 ⊇ τ3 ⊇ ...
The next two examples show that C2 ⊃ τ2 and C2n−1 ⊃ τ2n−1 for
every n ≥ 2.
Example 2. We consider a pentagone Γ with the set of vertices {a1, a2,
a3, a4, a5} and the set of edges {(a1, a2), (a2, a3), (a3, a4), (a4, a5), (a5, a1)}.
Since diam Γ = 2, we have Γ ∈ C2. On the other hand, a coloring χ, de-
fined by the rule
χ(a1) = 1, χ(a2) = 2, χ(a3) = 2, χ(a4) = 3, χ(a5) = 2,
is 2-admissible, so Γ /∈ τ2.
Example 3. Let n be a natural number > 1, A = {a1, ..., an}, B =
{b1, ..., bn} be disjoint sets. We consider the graph Γ with the set of ver-
tices V = A
⋃
B and the set of edges
E = (A×B) \ {(ai, bi) : i ∈ {1, ..., n}}.
Let V ′ be a subset of V such that card V ′ ≤ 2n − 1. Then there exists
i ∈ {1, ..., n} such that either ai /∈ V ′ or bi /∈ V ′. If ai /∈ V ′, then
V ′ ⊆ B(bi, 1). If bi /∈ V ′, then V ′ ⊆ B(ai, 1). Hence, Γ ∈ C2n−1. On the
other hand, a coloring χ, defined by the rule
χ(a1) = 1, ..., χ(an) = n, χ(b1) = n + 1, ..., χ(bn) = 2n,
is (2n− 1)-admissible, so Γ /∈ τ2n−1.
Question 1. Is C2n ⊃ τ2n for every n ≥ 2?
Question 2. Is τn ⊃ Cn+1 for every n ≥ 2?
Proposition 7. Let G be a group with the unit e, Y ⊆ G, e ∈ Y . Then
1 is a detector of the hypergraph GY = (G, {gY : g ∈ G}) if and only if
G =< Y >, where < Y > is the smallest subgroup of G containing Y .
Proof. Let Γ be the intersection graph of GY . In view of Proposition 5,
it suffices to show that Γ is connected if and only if G =< Y >.
88 Color-detectors of hypergraphs
Assume that Γ is connected and let g be an arbitrary element of G.
Then there exist the elements x1, ..., xn of G such that x1 = e, xn = g
and xiY
⋂xi+1Y 6= ∅ for every i ∈ {1, ..., n − 1}. It follows that x1 ∈
Y Y −1, x2 ∈ Y Y −1Y Y −1, ..., xn ∈ (Y Y −1)n, so g ∈< Y >.
Assume that G =< Y > and let g be an arbitrary element of G.
It suffices to show that the vertices e and g of Γ are connected. Let
g = yi11 yi22 ...yinn , where i1, ..., in ∈ {±1}. We put x0 = e, x1 = yi11 , xk+1 =
xkyik+1k+1 , k ∈ {1, ..., n− 1}. Since either xk+1 ∈ xkY or xk ∈ xk+1Y , then
xk, xk+1 are incident in Γ.
Problem 2. Let G be a group, Y ⊆ G, e ∈ Y and let n be a natural
number. Find necessary and sufficient conditions on Y under which n is
a detector of GY ?
Proposition 8. Let V be a vector space over some field F , γ be a cardinal
such that 1 ≤ γ < dimV,A(V, γ) be the family of all γ-dimensional affine
subspaces of V . Let H(V, γ) be the hypergraph (V,A(V, γ)) and let λ be
a cardinal such that λ ≤ dimV if dim V is finite and λ < dimV if V is
infinite. If γ is finite, then λ is a detector of H(V, γ) if and only if λ ≤ γ.
If γ is infinite, then λ is a detector of H(V, γ) if and only if λ < γ.
Proof. If γ is finite, then cov (H(V, γ)) = γ +1. If λ ≤ γ, by Proposition
2, λ is a detector of H(V, γ). If γ is infinite, then cov (H(V, γ)) = γ. If
λ < γ, by Proposition 2, λ is a detector of H(V, γ).
Let dim V = δ. We fix some basis {vα : α < δ} of V and put
χ(vα) = α and χ(v) = δ for every v ∈ V \{vα : α < δ}. If γ is finite, then
|card χ(S)| ≤ γ + 1 for every S ∈ A(V, γ). Hence, if λ > γ, then λ is
not a detector of H(V, γ). If γ is infinite, then |card χ(S)| ≤ γ for every
S ∈ A(V, γ). Hence, if λ ≥ γ, then λ is not a detector of H(V, γ).
Problem 3. Detect æ(H(V, γ), λ) for every vector space V and any car-
dinals γ, λ.
For example, if n,m are natural numbers, then
æ(H(Rn, 1),m) =



1, if m = 1;
n + 1, if m = 2;
2ℵ0 , if m ≥ 3.
A ball structure is a triple B = (X,P,B), where X,P are non-empty
sets and, for all x ∈ X and α ∈ P , B(x, α) is a subset of X which is
called a ball of radius α around x. It is supposed that x ∈ B(x, α) for all
x ∈ X, α ∈ P . The set X is called the support of B, P is called the set of
radiuses.
I. V. Protasov, O. I. Protasova 89
Given any x ∈ X, A ⊆ X, α ∈ P , we put
B∗(x, α) = {y ∈ X : x ∈ B(y, α)}, B(A,α) =
⋃
a∈A
B(a, α).
A ball structure B is called a ballean if
• for any α, β ∈ P , there exist α′, β′ ∈ P such that, for every x ∈ X,
B(x, α) ⊆ B∗(x, α′), B∗(x, β) ⊆ B(x, β′);
• for any α, β ∈ P there exists γ ∈ P such that, for every x ∈ X,
B(B(x, α), β) ⊆ B(x, γ).
• for any x, y ∈ X there exists α ∈ P such that y ∈ B(x, α).
We note that the balleans arouse independently in asymptotic topol-
ogy [2] and in combinatorics [3].
Let B = (X,P,B) be a ballean. A subset A ⊆ X is called bounded if
there exist x ∈ X,α ∈ P such that A ⊆ B(x, α).
Let Y be an arbitrary set, f : X → Y . We define the asymptotic
cardinality of f(X) as
ascard f(X) = min{card f(X \ V ) : V is a bounded subset of X}.
If Y = X and f is the indentity mapping, we write ascard X instead
of ascard id X.
Let H = (X,F) be a hypergraph such that every subset F ∈ F is
bounded in B, λ be a cardinal, λ < ascardX. A coloring χ : X →
ascardX is called asymptotically λ-admissible, if ascard χ(F ) ≤ λ for
every F ∈ F . We put
æas(H,λ) = sup{ascard χ(X) : χ is asymptotically λ− admissible}
and say that λ is an asymptotic detector of H if æas(H,λ) = λ.
We define a graph AΓ(H) of asymptotic intersections of hypergraph
H = (X,F) as a graph with the set of vertices F and the set of edges
{(F, F ′) : F, F ′ ∈ F , F 6= F ′ and F ⋂F ′ is unbounded}.
Proposition 9. Let B = (X,P,B) be a ballean such that X is a union
of some family {Bn : n ∈ ω} of bounded subsets. Let F = {Fn : n ∈ ω}
be a family of unbounded subset of X. Then 1 is an asymptotic detector
of H = (X,F) if and only if there exists a finite subset F ′ ⊂ F such that
G \⋃F ′ is bounded and AΓ(H) is connected.
90 Color-detectors of hypergraphs
Proof. Assume that 1 is an asymptotic detector of H, but X \ ⋃F ′
is unbounded for every finite subset F ′ ⊂ F . Then we can choose an
injective sequence (xn)n∈ω in X such that
xn ∈ Fn \ (B0
⋃
...
⋃
Bn
⋃
F0
⋃
...
⋃
Fn−1).
We put χ(xn) = 1 for every n ∈ ω, and χ(x) = 0 if x 6= {xn : n ∈ ω}.
Clearly, the coloring χ is asymptotically 1-admissible, but ascard χ(X) =
2. Hence, X = F0
⋃ ...⋃Fn
⋃V for some n ∈ ω and some bounded
subset V . Assume that AΓ(H) is not connected and let C be a connected
component of AΓ(H). Put X0 = V
⋃{Fi : Fi ∈ C}, X1 = X \ X0, and
let χ be the coloring of X, defined by the partition X = X0
⋃X1. If
F ∈ F , then either F ⋂X0 is bounded or F
⋂X1 is bounded, so χ is
1-asymptotically admissible, but ascard χ(X) = 2.
Assume that X \ {F0, ..., Fn} is bounded for some n ∈ ω and AΓ(H)
is connected, but 1 is not an asymptotical detector of H. Then there
exist an asymptotically 1-admissible coloring χ : X → {0, 1} and i, j ∈
{0, ..., n}, i 6= j such that χ|Fi\V ≡ 0, χ|Fj\V ≡ 1 for some bounded subset
V of G. Then Fi, Fj are not distinct connected components of AΓ(H),
so AΓ(H) is not connected.
Let B = (X,P,B) be a ballean, f : X → R, Y ⊆ X. We say that
r ∈ R is a limit of f(Y ) with respect to B if r is the limit of the filter with
the base {f(Y \ V ) : V is bounded subset of X}. The next definition
is inspired by [2]. A hypergraph H = (X,F) is called limit-detecting if,
given f : X → R, f(X) has a limit provided that every f(F ), F ∈ F has
a limit.
Proposition 10. Let B = (X,P,B) be a ballean, F be a family of un-
bounded subsets of X. If H = (X,F) is limit-detecting, then 1 is an
asymptotic detector of H.
Proof. Assume that H is limit detecting, but 1 is not an asymptotic
detector of H. Then there exist an asymptotically 1-admissible coloring
χ : X → ascard X, the ordinals α, β, α < β < ascard X and F, F ′ ∈ F
such that
χ|F\V = α, χ|F ′\V = β
for some bounded subset V of X. We consider a mapping f : X → {0, 1},
defined by the rule f(x) = 0 if x ∈ χ−1(α), f(x) = 1 if x /∈ χ−1(α). Then
f(Y ) has a limit for every Y ∈ F , but f(X) has not a limit.
Proposition 11. Let B = (X,P,B) be a ballean, F be a family of un-
bounded subsets of X such that X \⋃F ′ is bounded for some finite subset
F ′ ⊆ F . If 1 is an asymptotic detector of H, then H is limit-detecting.
I. V. Protasov, O. I. Protasova 91
Proof. Let F ′ = {F0, ..., Fn}. Assume that 1 is a detector of H, but H is
not limit-detecting. Then there exists a mapping f : X → R such that
every subset f(Fi) has some limit ri with respect to B, but f(X) has
no limit. We may suppose that r0, ..., rm are all distinct numbers from
{r0, ..., rn}. Clearly, m > 1. Choose ε > 0 such that
(r0 − ε, r1 + ε)
⋂
(ri − ε, ri + ε) = ∅
for every i ∈ {1, .., n}. Put χ(x) = 0 if f(x) ∈ (r0 − ε, r0 + ε), and
χ(x) = 1 otherwise. Clearly, χ is an asymptotically 1-admissible, but
ascard χ(X) = m > 1, a contradiction.
Question 3. Let B = (X,P,B) be a ballean, F be a family of unbounded
subsets of X, H = (X,F). Let 1 is an asymptotic detector of H. Is H
limit detecting?
References
[1] T.Banakh, S.Pidkuyko. A game characterization of limit-detecting sequences in
locally compact G spaces, Matem. Stud. (to appear)
[2] A.Dranishnikov. Asymptotic topology, Russian Math. Survey, 55 (2000), 71-116
[3] I.Protasov, T.Banakh, Ball Structures and Colorings of Groups and Graphs , Mat.
Stud. Monogr. Ser., V.11, 2003.
Contact information
I. V. Protasov,
O. I. Protasova
Department of Cybernetics, Kyiv Univer-
sity, Volodimirska 64, Kyiv GSP, Ukraine
E-Mail: protasov@unicyb.kiev.ua
Received by the editors: 18.10.2004
and in final form 24.03.2005.