Combinatorica 21 (2) (2001) 233 238
COMBINATORICA
Bolyai Society  Springer-Verlag
SOME REMARKS ON OBLIGATORY SUBSYTEMS OF
UNCOUNTABLY CHROMATIC TRIPLE SYSTEMS
PÉTER KOMJÁTH*
Dedicated to the memory of Paul ErdQ
s
Received January 13, 2000
An obligatory triple system is one that embeds into every triple system of uncountable
chromatic number. It is proved that a triple system is obligatory iff every 2-connected
component of it is. Obligatory triple systems are tripartite but not vice versa.
A famous example on uncountably chromatic graphs was given in [6]
where it was shown that for every uncountable cardinal º there exists a
triangle-free º-chromatic graph of cardinality º. In [3] those finite graphs
which necessarily appear in uncountably chromatic graphs are described;
these are the finite bipartite graphs. Already in [3] ErdQ
s and Hajnal ob-
served that interesting results can be obtained on uncountably chromatic
triple systems (say), for example, if the set system is of cardinality 5!1 then
it necessarily contains two triples with two common elements. This is not
true, however, if the system is allowed to have cardinality (25!0)+ (see [5]).
ErdQ
s, Galvin, and Hajnal in their monumental work ([2]) investigated
the army of problems that arose, but despite their efforts there are only a
handful of results on obligatory triple systems.
In this note we prove some general results on finite obligatory triple
systems. We show that this class is closed under some operations, namely,
taking disjoint unions and taking unions with one vertex identified. These
results reduce the problem of describing those finite obligatory triple systems
to that of 2-connected ones. We also showthat every obligatory triple system
Mathematics Subject Classification (2000): 05C15, 03E05
* Research partially supported by Hungarian National Research Grant T 19367.
0209 9683/101/$6.00 ©2001 János Bolyai Mathematical Society
234 PÉTER KOMJÁTH
is tripartite, i.e., it can be 3-colored in such a way that every triple gets
every color. Under CH it is easy to show that there is a finite tripartite
triple system F that is not obligatory; F even has the stronger property
that there is a system H omitting F with |H| =Chr(H) =5!1 (there are
examples in [2]). We include a ZFC example given by Saharon Shelah.
We notice that similar results can be formulated for n-tuple systems in
place of triple systems. The easy modifications are left to the reader.
Acknowledgment. My thanks go to two anonymous referees. Their sug-
gestions greatly improved the exposition.
Definitions. We use the standard axiomatic set theory notation and no-
tions. {x0,...,xn}< denotes that the set {x0,...,xn} is enumerated increas-
ingly, i.e., x0 < ··· f[C]={f(x):x"C}. If S is a set, º a cardinal then we let
[S]º = {x Ä…" S : |x| = º}, [S]<º = {x Ä…" S : |x| <º}.
H is a triple system iff it is of the form H =(S,H) w here H Ä…" [S]3.
S is the set of vertices. If H =(S,H) is a triple system and T Ä…" S then
H|T =(T,H )" [T ]3). The triple system H =(S,H) is disconnected if there
is a partition S = S0 *" S1 with H = H|S0 *"H|S1. If no such partition exists,
H is connected. The connected triple system H =(S,H) is 2-connected if
H|(S -{x}) is connected for every x " S. If H =(S,H) is a triple system,
then if T Ä…" S is a maximal (with respect to inclusion) set such that H|T is
2-connected, then H|T is a 2-connected component. The chromatic number
of H =(S,H), Chr(H) is the minimal cardinal µ for which there is a function
f : S µ with the property that |f[a]| e"2 holds for every a " H. A triple
system F =(V,F ) is tripartite if there is a partition V = V0 *" V1 *" V2 such
that |a)" Vi| =1 holds for a " F and i<3. Notice that a tripartite system is
2-chromatic, as well. If F =(S,F ) and H =(V,H) are triple systems then
Fd"Hif there is an injective function f : S V such that f[a] " H holds
for every a"F . Clearly, if F and F are isomorphic and Fd"H then F d"H
holds as well. F is obligatory iff Fd"His true for every triple system H with
Chr(H) >É. With this terminology, the main problem in [2] is to describe
all finite obligatory triple systems.
If F0 =(F0,S0) andF1 =(F1,S1) are triple systems on the disjoint sets S0
and S1 then F =(S0*"S1,F0*"F1) is the disjoint union of F0 and F1. Clearly, we
can create (the isomorphism type of) the disjoint union of arbitrary systems,
as well, by considering isomorphic copies on disjoint sets. If F0 =(S0,F0) and
F1 =(S1,F1) are triple systems and S0 )"S1 ={x} then F =(S0 *"S1,F0 *"F1)
is the one-point amalgamation of F0 and F1. Clearly, we can create (the
UNCOUNTABLY CHROMATIC TRIPLE SYSTEMS 235
isomorphism type of) the one-point amalgamation of arbitrary systems F0 =
(S0,F0) andF1 =(S1,F1) with some elements xi "Si specified by considering
isomorphic copies on sets with the images of x0 and x1 identified, otherwise
disjoint.
Lemma 1. Let F =(S,F ) be a finite obligatory triple system, x " S an
arbitrary element, and assume that H =(V,H) is an uncountably chromatic

triple system. For y " V set y " V iff there is a finite set g(y) Ä…" V -{y}
with the property that for every embedding f :FHwith f(x)=y one has

f[S])"g(y)=". Then Chr(H|V )d"É.


Proof. Set g (y)=g(y))"V for y "V . g is a function assigning a finite subset

of V to every element of V , that is, a set mapping, so Fodor s theorem ([7],

see also [4]) applies, claiming that there is a decomposition V =V0 *"V1 *"···
such that every Vi is free for g , that is, for y "Vi, g (y))"Vi =" holds. But then
F cannot be embedded in H|Vi as with a supposed embedding f :S Vi the
image f(x) cannot be any element y of Vi. As F is obligatory, this implies

that Chr(H|Vi)d"É, and so Chr(H|V )d"É.
Lemma 2. Assume that F0, F1 are finite obligatory systems. Then so is
their disjoint union.
Proof. Let H =(V,H) be an uncountably chromatic triple system. As F0 =
(S0,F0) is obligatory, there is an embedding f0 : S0 V of it. Clearly, the
triple system H|(V - f[S0]) is still uncountably chromatic so there is an
embedding f1 of F1 into it. Now f0 *"f1 embeds F0 *"F1 into H.
Lemma 3. Assume that F0, F1 are finite obligatory systems. Then so are
their one-point amalgamations.
Proof. Let F0 =(S0,F0) and F1 =(S1,F1) be obligatory triple systems
with S0 )" S1 = {x}. Assume that H =(V,H) is an uncountably chromatic
triple system. Let V0 , V1 Ä…"V be the sets described in Lemma 1 appropriate
to F0, F1, respectively. By that Lemma, Chr(H|(V0 *" V1 )) d" É, so there
is a point y " V - (V0 *" V1 ). There is an embedding f0 of F0 into H with
f0(x) =y. Further, there is an embedding f1 of F1 into H with f1(x) =y
and f1[S1 -{x}] )" f0[S0 -{x}] =" as otherwise y would be in V1 with the
set g(y) = f0[S0 -{x}]. Then, f0 *" f1 is an embedding of the one-point
amalgamation.
Theorem 1. Afinite triple system is obligatory iff every 2-connected com-
ponent of it is.
Proof. Obvious from Lemmas 2 and 3.
236 PÉTER KOMJÁTH
Theorem 2. Every obligatory triple system is tripartite.
Proof. Let F be an obligatory triple system. By the de Bruijn-ErdQ
s the-
orem ([1]) it suffices to show that every finite subsystem of F is tripartite.
The following result suffices for this.
Theorem 3. For every natural number n and infinite cardinal º there is a
º-chromatic triple system H of cardinality º such that every subsystem H
of H with |H |d"n is tripartite.
Proof. We are going to construct a Specker-type hypergraph. The vertex
2
set of our H will be [º]8n +1. We make
x = {x0, . . . , x8n2}<, y = {y0, . . . , y8n2}<, and z = {z0, . . . , z8n2}<
form a triple of our system H just in case
x0 -2n -4n
First we notice that it suffices to show Chr(H)=º for uncountable, regular
º. In this case the well known argument with chains of elementary submodels
used for Specker graphs works (see, for example, [3] or [8]).
Assume that we are given a subsystem H on the vertices {x0,...,xn-1}.
We can as well assume that H is connected. We use the increasing enumer-
ation
xi = {xi , . . . , xi }.
0 8n2
We also assume (by connectivity) that every xi (for i >0) is contained in
some triple containing some element xj with j¾ = x0 ,
4n2
the middle element of x0. For every 0d"ixi d" ¾ Ä(i) Ä(i)+1
holds. We remark that if {xi,xj,xk} form a triple in H then
Ä(j) =Ä(i) Ä… 2n (Ä…1)
Ä(k) =Ä(i) Ä… 4n (Ä…1)
hold (or some permutation of {i,j,k} satisfies them). From this, by induction
w e get that for every 0d"i|Ä(i) - 4n2 - 2·(i)n| d"i.
UNCOUNTABLY CHROMATIC TRIPLE SYSTEMS 237
Now, if {xi,xj,xk} is a triple in H then ·(j)=·(i)+1, ·(k)=·(i)+2, (or
this holds for some permutation of {i,j,k}) and so the coloring xi ·(i)
(mod 3) gives the required tripartition of H .
The following example is due to Saharon Shelah. It is included with his
kind permission.
Theorem 4. There is a finite tripartite system F and there is a triple system
H omitting F with |H|=Chr(H)=5!1.
Proof. F is the following system. The underlying set is {x0,x1,y0,y1,z0,z1}
and the triples are those of the form {xi,yj,zk}. So we have a system of
8 triples on 6 vertices. We define the F-omitting system H as follows. Let
f : [É1]2 É1 be a function as defined in Todorcevic s paper [9]. It has
the property that if A " [É1]É1 then f assumes every value on [A]2. Let
{Ä…,²,Å‚}< be in H iff Ä…=f(²,Å‚). We showthat this H works. Assume that
{x0,x1,y0,y1,z0,z1} formed an F. Without loss of generality we can assume
that x0 which is absurd. To show that Chr(H) =5!1 we show that no uncountable
AÄ…"É1 is independent. Indeed, if Ä…=min(A) then we can find by the above-
mentioned property elements ², Å‚ " A with Ä… = f(²,Å‚) so {Ä…,²,Å‚}"[A]3
and we are done.
References
[1] N. G. de Bruijn, P. ErdQ
s: A colour problem for infinite graphs and a problem in the
theory of relations, Proc. Konink. Nederl. Akad. Wetensch. Amsterdam, 54(1951),
369 373.
[2] P. ErdQ
s, F. Galvin, A. Hajnal: On set-systems having large chromatic number and
not containing prescribed subsystems, Infinite and finite sets (Colloq. Keszthely 1973;
dedicated to P. ErdQ
s on his 60th birthday), Vol. I. Colloq. Math. Soc. J. Bolyai, Vol.
10, North Holland, Amsterdam, 1975, 425 513.
[3] P. ErdQ
s, A. Hajnal: On chromatic number of graphs and set-systems, Acta Mathe-
matica Acad. Sci. Hung., 17(1966), 61 99.
[4] P. ErdQ
s, A. Hajnal, A. Máté, R. Rado: Combinatorial Set Theory: Partition Relations
for Cardinals. Studies in Logic and the Foundations of Mathematics, 106., North-
Holland Publishing Co., Amsterdam-New York, 1984.
[5] P. ErdQ
s, A. Hajnal, B. L. Rothschild: On chromatic number of graphs and set-
systems, Cambridge School in Mathematical Logic (Cambridge, England, 1971), Lec-
ture Notes in Mathematics, Vol. 337, Springer, Berlin, 1973, 531 538.
[6] P. ErdQ
s, R. Rado: A construction of graphs without triangles having pre-assigned
order and chromatic number, J. London Math. Soc. 35(1960), 445 448.
[7] G. Fodor: Proof of a conjecture of P. ErdQ
s, Acta Sci. Math., 14(1952), 219 227.
238 PÉTER KOMJÁTH: UNCOUNTABLY CHROMATIC TRIPLE SYSTEMS
[8] P. Komjáth: A Ramsey-style extension of a theorem of ErdQ
s and Hajnal, manuscript.
[9] S. Todorcevic: Partitioning pairs of countable ordinals, Acta Math. 159 (1987), 261-
294.
Péter Komjáth
Department of Computer Science
Eötvös University
Budapest, Hungary
[e-mail]