数理解析研究所講究録
第 1790 巻 2012 年 31-44

31On reflection and non-reflectionofcountable list-chromatic number of graphs*

神戸大学大学院・システム情報学研究科

酒井 拓史 (Hiroshi Sakai) \dager

渕野 昌 (Sakae Fuchino) \dager

Graduate School of System Informatics
Kobe University
Rokko-dai 1-1, Nada, Kobe 657-8501 Japanfuchino@diamond.kobe-u.ac.jp

hsakai@people.kobe-u.ac.jp

Abstract
It is known that the reflection cardinal of countable chromatic numberof graphs is fairly large. This stands in contrast with the situation of thecountable coloring number whose reflection cardinal is less or equal tothat of the Fodor-type Reflection Principle and hence can be consistently$\aleph_{2}$.

Applying a theorem of Peter Komj\’ath, it can be shown that the reflection of countable list-chromatic number behaves consistently similarly
to the reflection of countable chromatic number but it can also behave
consistently like the reflection of countable coloring number. Moreover,the Fodor-type Reflection Principle does not decide in which way thereflection of countable list-chromatic number behaves.
Date: March 7, 2012 (02:44 JST)2010 Mathematical Subject Classification: $03E04,05C10,05C15,05C63$
Keywords: chromatic number, list-chromatic number, coloring number, Fodor-type Reflection Principle\dag er The first author is supported by Grant-in-Aid for Scientific Research (C) No. 19540152 of
the Ministry of Education, Culture, Sports, Science and Technology Japan (MEXT).
\d ag er The second author is supported by Grant-in-Aid for Grant-in-Aid for Young Scientists (B)No. 23740076 of the Ministry of Education, Culture, Sports, Science and Technology Japan(MEXT).

32
1

Introduction

For a class of structures and a property the reflection cardinal ofis the minimal cardinal such that, for any $M\in C$ , if there are club many
substructures $N\in C$ of $M$ of cardinality
with the property then $M$ also
has the property $P(1)$ . If is the reflection cardinal of, we shall write$\kappa=\Re_{C}f^{[}(C, P)$ .
In some cases non-existence of reflection cardinal for certain pairs
canbe proved already in ZFC. We shall denote the non-existence of the reflection
cardinal for and by $\Re ef[(C, P)=\infty$ . (1) of the next examples is one ofsuch instances.
$P$

$C$

$\{C,$$P\rangle$$\kappa$$P$$<\kappa$$\langle C,$$\kappa$$P\}$$\langle C,$

$P\}$

$P$

$C$

Examples 1. (1) (Hajnal and Juh\’asz [9])Let be a cardinal of uncountable cofinality. Let $X=\{X,$be the topologicalspace defined by $X=\kappa+1$ with the open base for:. All subspaces $ofX$ of cardinality
are discrete and hence$X$
metrtzable. But
itself is not metrizable since the chamcter of the point is. Thus ZFC proves that $\Re ef[(C, P)$ does not exist for $C=$ topological“spaces and “
metrizable “.
$\kappa$$\mathcal{O}\rangle$$\mathcal{O}:\{\{\alpha\} :$u\subseteq\kappa,$$|\kappa\backslash u|<\kappa\}$\alpha<\kappa\}\cup\{u\cup\{\kappa\}$$<\kappa$$\kappa$$\kappa>\aleph_{0}$$P\equiv$(2) (Dow [1])For $C=compact$ spaces” and “ $P\equiv metr’izable$ ”, ZFC proves $\Re ef[(C, P)=\aleph_{2}$ .
(3) (Fuchino, Juh\’asz, Soukup, Szentmikl\’ossy and Usuba [5],Fuchino, Sakai, Soukup and Usuba [6]For $C=$ locally compact spaces” andmetrizable “,isconsistent with ZFC (modulo some fairly large. cardinal) and it is equivalent to
the Fodor-type Reflection Principle.
$)$$P\equiv$$\Re ef^{\mathfrak{l}}(C, P)=\aleph_{2}$$\square$In the following, we survey known facts and check some of the proofs inconnection with reflection of countability of some of the characteristics aboutcoloring of infinite graphs; namely, chromatic number, coloring number andlist-chromatic number (see the next section for definition).
It is known that the reflection cardinal of countable chromatic number ofgraphs is fairly large (Erd\’o’s and Hajnal, see Theorem 3.1 below). This stands
in contrast with the situation of the countable coloring number whose reflection
cardinal is less or equal to that of the Fodor-type Reflection Principle (seeCorollary 4.4) and hence in particular it can be consistently(Fuchino, Sakai,$\aleph_{2}$(1)

We are mainly considering porperties $P$ which transfer to arbitrary substructures. For
such , “club many” may be simply replaced by “all“.
$P$33
Soukup and Usuba [6] . In Section 4 we give an upper bound for this reflection
cardinal.
Applying a theorem of Peter Komj\’ath, it can be shown that the reflection ofcountable list-chromatic number behaves consistently similarly to the reflectionof countable chromatic number but it can also behave consistently like thereflection of countable coloring number. Moreover, the Fodor-type Reflection
Principle does not decide in which way the reflection of countable list-chromatic
number behaves (see Theorem 5.1).
This note is intended as a preliminary work toward [7]. More results including some more details of Theorem 5.1 and more related discussions should befound there.
$)$

2

Graph coloringFirst, let us recall some basic notions about graphs and the cardinal characteristics in terms of coloring of graphs we are going to discuss.
A gmph is a structure $G=\langle G,$
such that is a non empty set and $K$ abinary relation which is non-reflective and symmetric. Intuitively $E$ is a set ofvertices and a pair $\{x, y\}$ of vertices with $K(x, y)$ represents an edge connecting
and . If $K(x, y)$ we say that and are adjacent or and are connectedin .
We sometimes identify $K$ with $\{\{x, y\}$ : $\{x, y\rangle\in K\}$ and write $\{x, y\}\in K$
instead of $K(x, y)$ .
A subgmph $H$ of a graphis always an induced subgraph, that is, $H=$$\{H,$$G=\langle
G,$is a subgraph ofif
and $L=K\cap H^{2}$ . If is a subsetof (the underlying set of)then $Gr$ denotes the subgraph $\{I, K\cap I^{2}\}$ of$G=\langle G,$. We often misuse the notation deliberately and write $G[I=\{I, K\}$
instead of $GrI=\{I,$.
For a graph $G=\{G,$, a mapping :is said to be a good coloringfor if $\phi(x)\neq\phi(y)$ holds whenever and are adjacent in . The chromatic
number of is defined as:$G$$K\rangle$

$x$

$y$

$x$

$x$

$y$

$y$

$G$

$G$

$L\rangle$$H\subseteq G$$K\rangle$

$G$

$I$

$I$

$K\}$

$K\cap I^{2}\rangle$$K\rangle$$\phi$$G$$x$$Garrow\kappa$

$G$

$y$

$G$

$chr(G)= \min$ {$\kappa\in$

Card : there is a good coloring

The list-chromatic number of

$G$

$f$

:

$Garrow\kappa$}.

is defined by:list-chr $(G)= \min\{\kappa\in$ Card : for $\mu=|G|$ and for any $l:Garrow[\mu]^{\kappa}$
there is a good coloring : $Garrow\mu$such that $f(x)\in l(x)$ for all $x\in G$ }.
$f$

34
The following notation is convenient in connection with coloring number we$x\in G$ and, letintroduce next. For a graph$I\subseteq G$$G=\langle G,$ $K\rangle,$$K_{I}^{x}=\{y\in I:K(x, y)\}$For an ordering$\Subset$on$G$$K_{\Subset}^{x}=\{y\in G$.

and $x\in G$: $K(x,$

$y)$

and

$y\Subset x\}$.

.
Thus if $I=\{y\in I : y\Subset x\}$ we have
Using this notation, coloring number of a graph $G=\{G,$$K_{\Subset}^{x}=K_{I}^{x}$$K\rangle$

is defined as:ofcol $(G)= \min\{\kappa\in$ Card : there is a well-ordering
for all $x\in G$ }such that$G$$\Subset$$|K_{\Subset}^{x}|<\kappa$

It is easy to see that $chr(G)\leq list-chr(G)\leq col(G)$ for any graph .
The inequality can be also rigid (for both finite and infinite graphs). Coloring
number of graphs enjoys several quite useful characterizations. For a graph$b\in G$, a mapping: $Garrow[G]^{<\kappa}$ is a -coloring mapping if for any
with $K(a, b)$ , at least one of $a\in f(b)$ and $b\in f(a)$ holds. A subgraph $H$ of a
we have) if for any
is a -subgmph (notation:
graph
.
$G$

$\langle G,$$f$$K\rangle$$\langle G,$$K\rangle$$a,$$\kappa$$a\in G\backslash H$$H\subseteq_{\kappa}G$$\kappa$$|K_{H}^{a}|<\kappa$

Theorem 2.1 (Erd\’os and Hajnal [2], see also [6] and [4]).
For any infinite cardinal and any gmph the following are equivalent:$\kappa$$G$(a) col $(G)\leq\kappa$ ;(b) There is a -coloring mapping on $G$ ;$\kappa$(c) There is a continuously increasing sequence:
for all$\langle G_{\alpha}$$\alpha<\delta\}$of subalgebras.
andsuch that col
to denote $\Re ef[(C, P)$ for $C=$ graphs” andWe shall writeof countable coloring number”. We have a relatively good picture of what
can be. For the definition of the Fodor-type Reflection Principle andthe reflection cardinal $\Re ef1_{FRP}$ see Section 4.

of

$G$

$(G_{\alpha})\leq\kappa$$G_{\alpha}_{\kappa}G$$\alpha<\kappa$$\square$$P\equiv$$\Re_{t}f1_{col}$$\Re \mathfrak{e}f\mathfrak{l}_{\omega l}$

Theorem 2.2. (1) (Fuchino, Sakai, Soukup and Usuba [6])-type Reflection Principle holds.
$\Re ef1_{\omega l}=\aleph_{2}\Leftrightarrow Fodor$(2) $\Re ef1_{col}=\infty$ is consistent.
(3) $\Re ef1_{col}\leq\Re ef1_{FRP}$ .

Proof. For (1) see [6]. (3) will be proved in Section 4 (see Corollary 4.4).
(2): The next lemma shows that, for example, $V=L$ implies$\Re ef\mathfrak{l}_{col}=\infty$$\square$.

(Theorem 2.2)

35
Lemma 2.3. For a regular cardinal , suppose that there exists a non-reflecting
stationary set. Then there is a gmphof cardinality such that$(G)>\aleph_{0}$$(H)=\aleph_{0}$colbut col.
for all subgmphs $H$ of of cardinality$\kappa$$G$$E\subseteq E_{\omega}^{\kappa}$$\kappa$$G$$<\kappa$

Proof. Suppose thatis a non-reflecting stationary set. Let $g:Earrow$$E$be any ladder system on and let
where$E\subseteq E_{\omega}^{\kappa}$$[E]^{N_{0}}$$G=\langle\kappa,$(2.1)$\{\alpha, \beta\}\in K$

for$\alpha<\beta<\kappa$

if

The next two claims show that this$\beta\in E$

$G$

and

$K\rangle$$\alpha\in g(\beta)$.

is as desired.

Claim 2.3.1. col $(G)>\aleph_{0}$ .
If col, then, by Theorem 2.1, there is a filtration:$E$such thatfor all. Sinceis stationary, there is an$G_{\alpha}=Gr\alpha$such that. But
is infinite. This is a contradiction.
$(G)\leq\aleph_{0}$$\vdash$$\langle G_{\alpha}$$G_{\alpha}\subseteq_{\omega}G$$\alpha<\kappa\rangle$$\alpha\in E$$\alpha<\kappa$$K_{\alpha}^{\alpha}=g(\alpha)$(Claim 2.3.1)$\dashv$

Claim 2.3.2. colfor all$(G[\alpha)\leq\aleph_{0}$$\alpha<\kappa$.

We prove the assertion by induction on .
If
the claim is trivial. Successor steps are also trivial. So assume thatis a limit and we have shown col. Sinceis not stationary
in , there is a continuously increasing sequence:of elements ofsuch that
cf
and
and
for all. Then it is easy
to see thatfor all. By Theorem 2.1, (c) it follows that$\vdash$$\alpha$$\alpha<\omega_{1}$$E\cap\alpha$$(G[\beta)\leq\aleph_{0}$$\alpha$$\alpha$$\langle\alpha_{\xi}$$\delta=$$(\alpha)$$\alpha=\sup_{\xi<\delta}\alpha_{\xi}$$Gr\alpha_{\xi}_{\omega}Gr\alpha$$\alpha_{\xi}\not\in E$$\xi<\delta\rangle$$\alpha$$\xi<\delta$$\xi<\delta$

col $(G[\alpha)=\aleph_{0}.$$\dashv$$\square$For$C=$ graphs”

and$\Re ef((C, P)$ by.
The picture we have forthe following inequalities:$P\equiv$(Claim 2.3.2)(Lemma 2.3)

of countable chromatic number”, let us denote$\Re_{t}f\downarrow_{chr}$$\Re ef1_{chr}$

Theorem 2.4.
(1) (Erd\’os and Hajnal [3])(2) If$\kappa$

is a less satisfactory one as we only have$\Re ef\mathfrak{l}_{chr}\geq\supset_{\omega}$.

is a strongly compact cardinal then$\Re ef\iota_{chr}\leq\kappa$.

Proof. (1) follows $hom$ Theorem 3.1 in the next section.
(2) follows easily from the characterization of strongly compact cardinals interms of compactness of.
(Theorem 2.4)$\mathcal{L}_{\kappa,\kappa}$$\square$36
by the class of graphs
If we replace “graphs” in the definition of
whose vertices are intervals of a given linear ordering and two vertices are adjacent if and only if they intersect, we obtain the reflection cardinal
which is connected to Rado’s Conjecture: Rado’s Conjecture is characterized(for basic facts about Rado Conjecture see e.g. [12], [13]). In
by.
implies[7], we prove among other things thatwhich
In Section 5, we present a result on the reflection cardinalof countable list-chromatic number“.
for $C=$ graphs” andis$\Re eft_{chr}$$\Re ef1_{RC}$$\Re efl_{RC}=\aleph_{2}$$s$$\Re ef1_{col}=\aleph_{2}$$\Re ef\mathfrak{l}_{RC}=\aleph_{2}$$\Re\epsilon f1_{list-chr}$$P\equiv$$\Re\epsilon f[(C, P)$

3

Non-reflection of countable chromatic number

In this section, we reconstruct the details of a proof of the following theorem
following the sketch of a proof given in [14]:Theorem 3.1 (P. Erd\’os and Hajnal [3]).
, there is a gmph
For anyof cardinality
such that, for any subgmph $H$ ofcardinality
we have $chr(H)\leq\aleph_{0}$ while $chr(G)>\aleph_{0}$ .
$G$$n\in\omega\backslash 1$(actually of any$G$,of cardinality$\geq(\supset_{\eta})^{+}$$\geq(\supset_{m})^{+})$$\leq\supset_{\eta}$.
In the notation of the previous section, Theorem 3.1 implies
This theorem is well-known. For example, it is cited in recent papers by
Hajnal ([8]) and Todor\v{c}evi\v{c} ([14]). [8] contains a proof for the case $n=1$ and[14] a rough sketch of the whole proof. It seems however that the original paper[3] cited in [8] and [14] proves the theorem only under GCH.
Here, we identify the setof all n-tuples of elements of $X$ with$\Re ef\mathfrak{l}_{chr}\geq\supset_{u}$$X^{n}$

$nX=$

{ :
$f$

$f$

is a mapping from $n=\{0,$$\ldots,$$n-1\}$ to $X$}.

, we sayis such that
In particular, if
and $Dom(t)\prec=n$ . Also, for as above, we write $t(i)arrow=t_{i}$ . For a set $X$ and, defined by, let $shift_{n}$ be the binary relation on$t\inarrow X^{n}$$t=arrow\langle t_{0},$$\ldots,$$t_{n-1}\}$$Im(\overline{t})=\{t_{0}, \ldots, t_{n-1}\}$$tarrow$$X^{n}$$n\in\omega\backslash 2$(3.1)$shift_{n}(ti,\vec{v})\Leftrightarrow$(a)$\vec{u}\neq\vec{v}$and(b) $\overline{u}(i)=\vec{v}(i+1)$ for all $i<n-1$ or$\vec{v}(i+1)=\vec{u}(i)$for all $i<n-1$.
In the following we show that the graph $G=\{X^{n+1},$
is as in Theorem 3.1.
of cardinalityfor$\vec{u},\vec{v}\in X^{n}$$\geq(\supset_{\eta})^{+}$$shift_{n+1}\rangle$

for any set $X$

37Lemma 3.2. For$n\in\omega\backslash 1$$chr(\{X^{n+1},$ $shift_{n+1}\rangle)\leq\aleph_{0}$and for any set $X$ with$|X|\leq\supset_{\eta}$, we have.

Proof. We prove the lemma by induction on . First, let us prove the assertion
for $n=1$ . Let $F$ be a family of subsets of such that $|F|=\supset_{1}(=2^{N_{0}})$ andsuch that elements of $F$ are pairwise incomparable (with respect to ). For
, let
$n$

$\omega$$\subseteq$$t\in F^{2}arrow$(3.2)$n_{t} arrow=\min(\vec{t}(0)\backslash t(1))arrow$.

It is enough to prove the following:

Claim 3.2.1. The mapping.
$\{F^{2},$is a good coloring for the gmph

$sh\dot{\ovalbox{\tt\small REJECT}}ft_{2}\rangle$

Suppose that
Then, since$\vdash$$\phi:F^{2}arrow\omega;t\mapsto n_{\overline{t}}arrow$are such thatbut$\vec{u},\vec{v}\in F^{2}$$n_{\vec{u}}\not\in\vec{u}(1)$$shift_{2}(\vec{u},\vec{v})$, say, with $\vec{u}(1)=\vec{v}(O)$ .

by (3.2), we have$n_{\tilde{v}}\in\vec{v}(0)=\vec{u}(1)$$\dashv$$\phi(\vec{u})\neq\phi(\vec{v})$.

(Claim 3.2.1)

The next claim completes the induction proof of Lemma 3.2.

are infinite sets such that
Claim 3.2.2. For $n\geq 2$ , suppose that $X$ andand $|Y|\leq 2^{|X|}$ . Then we have $chr(\langle Y^{n+1}, shift_{n+1}\})\leq$$Y$$chr(\langle X^{n}, shift_{n}\rangle)\leq\aleph_{0}$$\aleph_{0}$.

We may assume that $X$ is a cardinal andpairwise incomparable (with respect to ). Let. For $v\in Y$ , letfor$\vdash$$\kappa$$Y\subseteq \mathcal{P}(\kappa)$

(3.3)

For

$u,$

$\alpha_{u,v}=\{\begin{array}{ll}\min(u\backslash v)+1, if u\neq v,0, otherwise.\end{array}$$\vec{u}\in Y^{n+1}$

(3.4)

$Y$

$\phi:X^{n}arrow\omega$$\subseteq$$\{X^{n},$ $shift_{n}\rangle$

and elements of are
be a good coloring, let$\vec{\alpha}_{\vec{u}}=\langle\alpha_{\vec{u}(0),\vec{u}(1)},$$\alpha_{\vec{u}(1),\vec{u}(2)},$$\alpha_{\vec{u}(n-1),\vec{u}(n)}\}$$\ldots,$.

Note that we have
. Note also that if is not a constantfor, then at least one
function then neither is . If
forof and is not constant. It follows that at least one ofandis notconstant. Since it is clear thatstill satisfy (3.1), (b) it follows thatand.
and hence we have
Now letbe defined by$\vec{\alpha}_{\vec{u}}\in X^{n}$$\vec{\alpha}_{\vec{u}}$$\vec{u}$$\vec{u}\in Y^{n+1}$$shift_{n+1}(\vec{u},\vec{v})$$\vec{v}$$\vec{u}$$\vec{u},\vec{v}\in Y^{n+1}$$\vec{\alpha}_{\vec{u}}$$\vec{\alpha}_{\vec{u}}$$\vec{\alpha}_{\vec{v}}$$shift_{n}(\vec{\alpha}_{\vec{u}},\vec{\alpha}_{\tilde{v}})$$\vec{\alpha}_{\vec{u}}\neq\vec{\alpha}_{\vec{v}}$$\phi^{*}:Y^{n+1}arrow\omega$$\vec{\alpha}_{\vec{v}}$

38
(3.5)

$\phi^{*}(\vec{u})=\phi(\vec{\alpha}_{\vec{u}})$.

is then a good coloring for. Then we have
andabove. Since is a good coloring, it follows thatfor$\vec{u}\in Y^{n+1}$$\langle Y^{n+1}$$\phi^{*}$$\vec{v}\in Y^{n+1}$$shift_{n+1}(\tilde{u},\vec{v})$, sh$shift_{n}(\vec{\alpha}_{\vec{u}},\vec{\alpha}_{\tilde{v}})$$\phi$: Suppose that ,as was already seen.
$\vec{u}$$\dot{\ovalbox{\tt\small REJECT}}ft_{n+1}\}$$\phi^{*}(\vec{u})=\phi(\vec{\alpha}_{\vec{u}})\neq\phi(\vec{\alpha}_{\vec{v}})=\phi^{*}(\vec{v})$$\dashv$$\square$.

(Claim 3.2.2)(Lemma 3.2)

Now, let. Together with Lemma 3.2, the next lemma completes
the proof of Theorem 3.1 by showing thatis as desired in Theorem 3.1.
$\lambda\geq(\supset_{\eta})^{+}$$\{\lambda^{n+1},$

Lemma 3.3.

$chr(\langle\lambda^{n+1}, shift_{n+1}\})>\aleph_{0}$$shift_{n+1}\rangle$.

Proof. Let

{

(3.6)

$\lambda\rangle^{n+1}=\{\vec{u}\in\lambda^{n+1}$:

is strictly increasing(as a mapping from $n+1$ to ) .

$\vec{u}$$\lambda$

Since$\langle\langle\lambda\rangle^{n+1},$$shift_{n+1}\}$is a subgraph of$\langle\lambda^{n+1},$$shift_{n+1}\rangle$$\}$, it is enough to to showthat.
Suppose otherwise. Then there is a good coloring :for thegraph {. By Erd\’o’s-Rado theorem there is a set
such
. If
that is constant on
are $n+2$ elements of $H$ ,then, letting, we haveand(Lemma 3.3)
. This is a contradiction.
but$chr(\langle\{\lambda\rangle^{n+1}, shift_{n+1}\})>\aleph_{0}$$\phi$$\{\lambda\rangle^{n+1},$$shift_{n+1}\rangle$$H\in[\lambda]^{N_{1}}$$\langle H\rangle^{n+1}$$\phi$$\vec{u}=\langle\alpha_{0},$$\alpha_{1},$$\alpha_{0}<\alpha_{1}<\cdots<\alpha_{n+1}$$\vec{v}=\langle\alpha_{1},$$\alpha_{n}\rangle$$\ldots,$$\alpha_{2},$$shif\mathfrak{t}_{n+1}(\vec{u},\vec{v})$$\alpha_{n+1}\rangle$$\ldots,$$\phi(\vec{u})=\phi(\vec{v})$4$\langle\lambda\}^{n+1}arrow\omega$$\square$

Reflection cardinal of Fodor-type Reflection

The Fodor-type Reflection Principle (FRP, [5], see [6] for the formulation wegive below) states that the following (4.1) holds for all regular:$\lambda>\aleph_{1}$$\lambda$$(4.1)_{\lambda}$

For any stationary
is a cofinal subset of$E\subseteq E_{\omega}^{\lambda}$$g(\alpha)$$\{x\in[\alpha^{*}]^{N_{0}} :is stationary in$[\alpha^{*}]^{N_{0}}$$\alpha$and a mapping $g:Earrow[\lambda]^{N_{0}}$ such that, there isfor allsuch that$\alpha\in E$$\alpha^{*}\in E_{\omega_{1}}^{\lambda}$\sup(x)\in E, g(\sup(x))\subseteq x\}$.

Let us consider here the following generalization. For any cardinallet FRP be the assertion stipulating that the following (4.2) holds for all
regular cardinal:$\kappa>\aleph_{1}$$<\kappa$$\lambda$$\lambda\geq\kappa$

39$(4.2)_{\lambda}$

For any stationary
is a cofinal subset ofcf
andand a mapping, there isfor all$E\subseteq E_{\omega}^{\lambda}$$g(\alpha)$$\omega_{1}\leq$$g:Earrow[\lambda]^{\aleph_{0}}$such that$\alpha^{*}\in\lambda$

such that$\alpha\in E$$\alpha$$(\alpha^{*})<\kappa$$\{x\in[\alpha^{*}]^{N_{0}} :is stationary in$[\alpha^{*}]^{N_{0}}$\sup(x)\in E, g(\sup(x))\subseteq x\}$.

Then FRP is equivalent to FRP
then FRP
holds.
Let$<\aleph_{2}$. For cardinals$\kappa<\kappa’$, if FRP$<\kappa$

holds,$<\kappa’$$\Re \mathfrak{e}f\mathfrak{l}_{FRP}=\min$

if {

{

$\kappa\in$

Card: FRP$<\kappa$

holds}

Card : FRP holds} is nonempty. Otherwise we let.
The following reformulation of FRP shows thatis actually areflection cardinal in line with the reflection cardinals of properties of classes ofstructures.
$\kappa\in$$\Re \mathfrak{e}f1_{FRP}=\infty$$<\kappa$$\Re ef\downarrow FRP$$<\kappa$

Proposition 4.1. For a cardinal, FRP
is equivalent to the assertion
that the following (4.3) holds for all regular cardinal:$\kappa>\aleph_{1}$$<\kappa$$\lambda\geq\kappa$$\lambda$$(4.3)_{\lambda}$

For any stationary
is a cofinal subset of
uncountable cardinality$E\subseteq E_{\omega}^{\lambda}$$g(\alpha)$$\alpha$and a mapping $g:Earrow[\lambda]^{N_{0}}$ such thatfor all $\alpha\in E$ , there is a set I of regular$\mu<\kappa$

respect to$g$such that cf $( \sup I)=\mu,$ I is closed with

and$\{x\in[I]^{N_{0}}:\sup(x)\in E, g(\sup(x))\subseteq x\}$is stationary in$[I]^{\aleph_{0}}$.

The proposition follows immediately from the next lemma:

Lemma 4.2. For regular uncountable cardinals, a stationary
with, a mapping
such thatis a cofinal subset of for all, andthe following are equivalent:$\lambda,$$g:Earrow[\lambda]^{N_{0}}$$E\subseteq E_{\omega}^{\lambda}$$\alpha\in E$$\mu$$\mu<\lambda$$g(\alpha)$$\alpha$$\alpha^{*}\in E_{\mu z}^{\kappa}$(a) There isand$I\in[\alpha^{*}]^{\mu}$such that $\sup(I)=\alpha^{*},$ I is closed with respect to$Z_{I}=\{x\in[I]^{\aleph_{0}}$$g$: $\sup(x)\in E$ and $g( \sup(x))\subseteq x\}$is stationary;$(a’)$For any
such that $\sup(I)=\alpha^{*}$ and I is closed with respect toas well as with respect to the order topology of , we have that
$I\in[\alpha^{*}]^{\mu}$$g$$\alpha^{*}$

40: $\sup(x)\in E$ and $g( \sup(x))\subseteq x\}$$Z_{I}=\{x\in[I]^{N_{0}}$is stationary;(b) The set$Z_{\alpha}*=\{x\in[\alpha^{*}]^{N_{0}}$: $\sup(x)\in E$ and $g( \sup(x))\subseteq x\}$is stationary.

Proof.

is clear.
: Suppose that. Let
disjoint fromrespect to . Let$(a’)\Rightarrow(a)$$(a)\Rightarrow(b)$$Z_{\alpha^{s}}$be a cluband closed with

$C\subseteq[\alpha^{*}]^{N_{0}}$$I$$I\in[\alpha^{*}]^{\mu}$$Z_{\alpha}*$is not stationary and let
be such that is cofinal in$\alpha^{*}$

$g$

(4.4)

$C’=\{x\cap I$: $x\in C$ and $\sup(x)=\sup(x\cap I)\}$ .

Then we can find aand hence also from. $C”$ is still disjoint fromwhich is a club in. Thusis not stationary.

$C”\subseteq C’$$Z_{\alpha^{*}}$$Z_{I}$$[I]^{\aleph_{0}}$.

$Z_{I}$: Assume thatis stationary. Letbe such that$\sup(I)=\alpha^{*}$ andis closed with respect to as well as with respect to theorder topology of . We have to show thatis stationary in. Supposethatis a club. Let$(b)\Rightarrow(a’)$$Z_{\alpha}$$I$$I\in[\alpha^{*}]^{\mu}$$g$$\alpha^{*}$$[I]^{N_{0}}$$Z_{I}$$C\subseteq[I]^{N_{0}}$(4.5)$\tilde{C}=\{x\cup y:x\in C, y\in[\alpha^{*}\backslash I]^{N_{0}}, \sup(x)\geq\sup(y)\}$.

. Hence, by the assumption, there isThen.
is a club in
Let $x=z\cap I$ . By (4.5) and since is closed with respect to the order topology
of , we have $\sup(z)=\sup(x)\in E\cap I$ . By closedness of with respect to, it follows that $g( \sup(x))\subseteq I$ . Hence $g( \sup(x))\subseteq z\cap I=x$ . Thus we have$x\in Z_{I}\cap C$ . This shows that
(Lemma 4.2)
is stationary.
$\tilde{C}$$z\in Z_{\alpha’}\cap\tilde{C}$$[\alpha^{*}]^{N_{0}}$

$I$

$I$

$\alpha^{*}$$g$$Z_{I}$

Theorem 4.3. Assuume FRP$\langle G,$$K\rangle$$\square$$<\kappa$

for a cardinal$>\aleph_{1}$. For any gmph $G=$

, if
col $(GrI)\leq\aleph_{0}$ holds for all $I\in[G]^{<\kappa}$ ,(4.6)

then col$(G)\leq\aleph_{0}$.

Proof. The proof is almost identical with the one given in [6] for the case$\kappa=\aleph_{2}$.

We prove by induction on
cardinals :$\lambda$that the following as sertion (4.7) holds for all$\lambda$$\lambda$(4.7)$\lambda$

For any graph $G=\{G,$.
col$(G)\leq\aleph_{0}$$K\rangle$of cardinality , if (4.6) holds, then$\lambda$

41
For
trivially holds.
Suppose thatand we have proved (4.7) for all.
If is singular, and is as in (4.7) , then we can conclude colby
the induction hypothesis and Shelah Singular Compactness Theorem ([11] see
also [6] .
Suppose now that is regular and assume, toward a contradiction, that there
is a graphof cardinality which satisfies (4.6) but col $(G)>\aleph_{0}$ . Without
loss of generality, we may assume that (the underlying set of) is . Note thatcolfor allby the induction hypothesis. Hence$\lambda<\kappa,$$(4.7)_{\lambda}$$\lambda\geq\kappa$$\lambda’<\lambda$$\lambda’$$G$$\lambda$$(G)\leq\aleph_{0}$$\lambda$

$s$

$)$

$\lambda$$G$$\lambda$$G$$(Gr\alpha)\leq\aleph_{0}$

(4.8)

{

$E=$

$\alpha<\lambda$$\alpha\in\lambda$: there is$\beta\in\lambda\backslash \alpha$is stationary by Theorem 2.1. Let

Claim 4.3.1.

$\lambda$$E^{*}$

such that$E^{*}=E\cap E_{\omega}^{\lambda}$$|K_{\alpha}^{\beta}|\geq\aleph_{0}$}.

.

is stationary in .
$\lambda$

Suppose otherwise. Thenmust be stationary. For each,letbe such thatis infinite. Let
and
.
Then
since cf.
andwitness that
. By
Fodor’s theorem, there are
and stationary
such thatfor all. We have. Thusisstationary. This is a contradiction to the assumption.
(Claim 4.3.1)$\vdash$$E\cap E_{>\omega}^{\lambda}$$\beta_{\alpha}\in\lambda\backslash \alpha$$\alpha\in E\cap E_{>\omega}^{\lambda}$$K_{\alpha^{\alpha}}^{\beta}$$\xi_{\alpha}<\alpha$$(\xi_{\alpha})\leq\omega$$c_{\alpha}\in[K_{\alpha^{\alpha}}^{\beta}]^{\aleph_{0}}$$[\xi_{\alpha}, \alpha)\cap E_{\omega}^{\lambda}\subseteq E^{*}$$\beta_{\alpha}$$c_{\alpha}$$\xi^{*}\in E_{\omega}^{\lambda}$$\alpha\in E^{\uparrow}$$\xi_{\alpha}=\xi^{*}$$\xi_{\alpha}=\sup(c_{\alpha})$$E^{\uparrow}\subseteq E\cap E_{>\omega}^{\lambda}$$E^{*}$$E_{\omega}^{\lambda} \backslash \xi^{*}=\bigcup_{\alpha\in E\dagger}[\xi^{*}, \alpha)\cap E_{\omega}^{\lambda}\subseteq E^{*}$$\dashv$For, let
be such thatand.
By thinning out
if necessary, we may assume that for any. Let
be such thatandis cofinal
in for all.
By FRP , there issuch that $\aleph_{1}\leq|I|=$ cf $( \sup(I))=\mu<\kappa,$
is closed with respect to and as in Lemma 4.2, (a) (with $E$ there replacedbyis stationary in. By blowing up if necessary without changing$\sup(I)$ , we may assume thatis also closed with respect to the order topology$\sup(I)$ofas well as closed with respect to the mapping.
Now, we have col $(G[I)\leq\aleph_{0}$ by the assumption (4.6). Hence there is a-coloring mapping : $Iarrow[I]^{<N_{0}}$ for $Gr$ by Theorem 2.1. Let$\alpha\in E^{*}$$\beta_{\alpha}\in\lambda\backslash \alpha$$|K_{\alpha^{\alpha}}^{\beta}|\geq\aleph_{0}$$E^{*}$$\min(E^{*}\backslash \alpha)$$c_{\alpha}\in[K_{\alpha^{\alpha}}^{\beta}]^{N_{0}}$$\alpha\in E^{*},$$g:E^{*}arrow[\lambda]^{N_{0}}$$c_{\alpha}\subseteq g(\alpha)\subseteq\alpha$$\beta_{\alpha}<$$g(\alpha)$$\alpha\in E^{*}$$\alpha$$I\in[\lambda]^{<\kappa}$$<\kappa$

$Z$

$g$

$E^{*})$$I$$I$$[I]^{N_{0}}$$I$$\alpha\mapsto\beta_{\alpha}$

(4.9)

Since

$I$

$f$

$\aleph_{0}$

$C=$

{

$x\in[I]^{N_{0}}$:$x$is closed with respect to

$f$

}.

is a club in, there is an $x\in Z\cap C$ . By the definition of and ,for. For any
, we haveas is closedwith respect to . Since
is finite,
is nonempty. But then, for$C$$|K_{x}^{\beta}|\geq\aleph_{0}$$Z$$[I]^{\aleph_{0}}$$\beta=\beta_{\sup(x)}$$f$$f(\beta)$$\gamma\in K_{x}^{\beta}$$K_{x}^{\beta}\backslash f(\beta)$$f(\gamma)\subseteq x$

$x$

$g$

42
any

$\gamma^{*}\in K_{x}^{\beta}\backslash f(\beta)$, we have$\gamma^{*}\not\in f(\beta)$

and$\beta\not\in f(\gamma^{*})$. This is a contradiction.
$\square$(Theorem 4.3)

Theorem 4.3 can be reformulated in the following inequality of reflection
cardinals:
Corollary 4.4.

$\Re_{C}f1_{\omega l}\leq\Re ef1_{FRP}$.

口This inequality can be further related to that of Theorem 2.4, (2) just by
is less or equal to the first strongly compact cardinalobserving that(that is, if such a cardinal ever exists).
$\Re\epsilon f1_{FRP}$

Reflection and Non-reflection of list-chromatic number

5

Theorem 5.1. The statement
FRP.

$\Re ef1_{list-chr}=\aleph_{2}$”is independent from ZFC$+$

For the proof of Theorem 5.1, we use the following reformulation of a theorem
by P. Komj\’ath:

Theorem 5.2 (Komj\’ath [10]).
(1) (MA(Cohen)) For any gmph.

$G$of cardinality$\aleph_{1}$, we have $\aleph_{0}<chr(G)$$\Leftrightarrow\aleph_{0}<list-chr(G)$(2) For any gmph $G$ of cardinality , if $\aleph_{0}<col(G)$ then, for the poset“$\aleph_{0}<list-chr(G)$ “.
, we haveFn$\aleph_{1}$$\mathbb{P}=$$\square$$(\omega_{2},2, <\aleph_{1})$$|\vdash_{\mathbb{P}}$We also need the following facts:, Soukup, Szentmikl\’ossy and Usuba [5])Facts 5.3. (1) (Fuchino,
FRP is preserwed by any $c.c.c$ . forcing.
$Juh\mathfrak{X}Z$(2) (Fuchino, Sakai, Soukup and Usuba [6])Suppose that is stmngly compact. Then we havecollapsing to .
Col
standard poset$\kappa$$\mathbb{P}=$$(\aleph_{1}, <\kappa)$$\kappa$$|\vdash_{\mathbb{P}}$FRP “ where“$\mathbb{P}$is the$\square$$\omega_{2}$of ZFCFRP and
Proof of Theorem 5.1: First, start from a model
be the generic extension. By
force MA(Cohen) by a c.c. . poset. Let. By Theorem 3.1, there is a graph
Fact 5.3, (1), we still have FRP in. By Theorem 5.2, (1), this witnesses also
inwitnessing.
inAssume now that is a strongly compact cardinal in and let $V[G]$ be the. Then webyCol
generic extension obtained by collapsing to
$V$

$+$

$V[\mathcal{G}]$

$c$

$G$

$V[\mathcal{G}]$$\Re ef1_{chr}>\aleph_{2}$$\Re ef1_{list-chr}>\aleph_{2}$$G$$V[\mathcal{G}]$$V[\mathcal{G}]$$V$$\kappa$$\kappa$$\aleph_{2}$$\mathbb{P}=$$(\aleph_{1}, <\kappa)$

43
have
FRP by Fact 5.3, (2). In
every graph $H$ of cardinality
iscontained in cofinally many intermediate models over each of which many Cohen
subsets ofare added. Hence, by Theorem 5.2, (2), if $H$ has countable listchromatic number inthen $H$ also has countable coloring number. Now,in
, if
is a graph such that all subgraphs $H$ of cardinality
have
countable list-chromatic number, then they all have countable coloring number.
By FRP in
it follows that col. Since list-chr $(G)\leq col(G)$ we
obtain list-chr. This shows thatin.
$V[\mathcal{G}]\models$$V[\mathcal{G}]$$\aleph_{1}$$\omega_{1}$$V[\mathcal{G}]$$V[\mathcal{G}]$$G$$\leq\aleph_{1}$$V[\mathcal{G}]$$(G)\leq\aleph_{0}$$(G)\leq\aleph_{0}$$\Re ef\mathfrak{l}_{list-chr}=\aleph_{2}$$V[\mathcal{G}]$$\square$(Theorem 5.1)

Note that by the same argument as in the first part of the proof of Theorem
5.1, we obtain that MM implies. This is quite unexpected
since it is usualy so that if we have certain reflection phenomena then we dohave it under MM or some weakening of it. Here we have consistently thereflection of countable list-chromatic number but MM refutes it! This mightsuggest that
underlies a new type of reflection phenomenon
still to be studied.
$\Re \mathfrak{e}f^{\mathfrak{l}_{list-chr}}>\aleph_{2}$$\Re \mathfrak{e}f\downarrow list-chr=\aleph_{2}$References[1] A. Dow, An introduction to applications of elementary submodels to topology, Topology Proceedings 13, No.1 (1988), 17-72.
[2] P. Erd\’os and A. Hajnal, On chromatic number of graphs and set-systems,

Acta Mathematica Academiae Scientiarum Hungaricae, Vol. 17, No. 1-2,
(1966), 61-99.
[3] P. Erd\’os and A. Hajnal, On chromatic number of graphs, Theory of Graphs(Proc. Colloq., Tihany, 1966), Academic Press, New York, (1968), 83-98.
[4] S. Fuchino, Remarks on the coloring number of graphs, RIMS K\^oky\^uroku,
No.1754, (2011), 6-16.
[5] S. Fuchino, I. Juh\’asz, L. Soukup, Z. Szentmik16ssy and T. Usuba, Fodortype Reflection Principle and reflection of metrizability and metaLindel\"ofness, Topology and its Applications Vol.157, 8 (June 2010), 1415-

1429.
[6] S. Fuchino, H. Sakai, L. Soukup and T. Usuba, More about the Fodor-type
Reflection Principle, preprint.

44[7] S. Fuchino, H. Sakai, V. Torres Perez and T. Usuba, Rado’s Conjecture andthe Fodor-type Reflection Principle, in preparation.

[8] A. Hajnal, On the chromatic number of graphs and set Systems, lecturenote of PIMS Distinguished Chair Lectures, University of Calgary, Calgary,
Canada (2004).
[9] A. Hajnal, I. Juh\’asz, On spaces in which every small subspace is metrizable,
Bulletin de 1‘Acad\’elmie Polonaise des Sciences, Serie des sciences math.
astr. et phys., Vol.24, No.9, (1976), 727-731.
[10] P. Komj\’ath, The list-chromatic number of infinite graphs, preprint.
[11] S. Shelah, A compactness theorem for singular cardinals, free algebras,
Whitehead problem and transversals, Israel Journal of Mathematics 21(1975), 319-349.
[12] Stevo Todor\v{c}evi\v{c}, On a conjecture of Rado, Journal London MathematicalSociety Vol.s2-27, (1) (1983), 1-8.

[13] Stevo Todor\v{c}evi\v{c}, Conjectures of Rado and Chang and Cardinal Arithmetic, in: Finite and Infinite Sets in Combinatorics (N. W. Sauer et al.,eds), Kluwer Acad. Publ. (1993) 385-398.
[14] Stevo Todor\v{c}evi\v{c}, Combinatorial dichotomies in set theory, The Bulletinof Symbolic Logic, Vol. 17, No. 1 (2011), 1-72.