format: text

text:
# Spontaneous magnetization of the Ising model on the Sierpinski carpet fractal, a rigorous result

## 1 Introduction

The study of the physical models on the Sierpinski carpet  has been the focus of several works in the last two decades. However, most of these papers are based on approximate renormalization group techniques , on perturbative expansions  or on numerical simulations . Thus, very few rigorous results are known for this self-similar structure. Indeed, the Sierpinski carpet is an infinitely ramified fractal, where it is not possible to apply the exact decimation techniques, which allow to solve many models, defined on finitely ramified fractals, such as the Sierpinski gasket .

A relevant theorem is given by an upper and a lower bound on the return probability of a simple random walk . These bounds prove that the spectral dimension  of the Sierpinski carpet is smaller than two. Hence, from the generalized Mermin-Wagner theorem , the continuous symmetry spin models do not present spontaneous magnetization. On the other hand, there are no general criteria relating the behaviour of the discrete symmetry models, in particular Ising, with a simple parameter, describing the topology of the space where the model is defined. The main known results regard the euclidean lattices, where spontaneous magnetization is present if the dimension is $`2`$, and the exactly decimable fractals, which never present spontaneous magnetization .

However, the approximate calculations  and the numerical simulations  suggest that an Ising spin system on the Sierpinski carpet is spontaneously magnetized at finite temperature. Recently, this property has been proved in , where it is shown that it follows from the behaviour of percolation on the Sierpinski carpet. Here we give an alternative proof inspired by the classical Peierls argument  for the Ising model on the two-dimensional lattice and, in particular, by the version given in . These theorems are the first exact results showing the existence of Ising transition in a low dimensional structure, i.e. in a structure with spectral dimension smaller than 2.

We will consider the Sierpinski carpet graph illustrated in Figure 1, even if the proof can be generalized to different infinitely ramified carpets. To each site of the graph we associate an Ising spin and to each link a ferromagnetic interaction. We call $`p_i^{}`$ the probability for the magnetization of the spin $`i`$ to be smaller than one and we show that, at low enough temperature, $`p_i^{}<ϵ<1/2`$ for each site $`i`$. The theorem is based on a low temperature loop expansion of this probability and on an estimate of the number of the self-avoiding on the sites (SOS) loops.

The main difference from the two-dimensional case is that now the space, called dual graph, where the loops are defined, has unbounded connectivity, namely, the coordination (number of nearest neighbours) of a site is finite but not bounded. Hence the proof requires more complicated mathematical techniques. Notice that the standard Peierls argument results rather simple, as the dual of the two-dimensional lattice is again a two-dimensional lattice. In spite of the unbounded connectivity, here we will be able to estimate the number of SOS loops because of an important property of the dual graph, which will be called sparse high connectivity, i.e. sites with large coordination are far apart. In particular, when the coordination is greater than $`43^m`$, the sites are distant at least $`2^{m+1}`$ in the intrinsic metric of the dual graph.

Peierls argument is valuable because of the insight it gives into why the Ising model is magnetized. Hence, we believe that this proof could be useful to find a general criterion for the existence of spontaneous magnetization on a generic discrete structure. Notice that Peierls argument has been already used to show the existence of Ising transition in an inhomogeneous systems, in particular in the case of diluted random graphs above the percolation tresholds . We start introducing some definitions and notations.

## 2 Definitions and notations

Let us consider the $`N`$ generation of a Sierpinski carpet. On each site $`i`$ we define an Ising spin $`s_i=\pm 1`$ and we fix the spins on the boundary to the value $`+1`$ (see Figure 2). The energy of the spin system is given by:

$$\frac{1}{2}\underset{ij}{}s_is_j$$
(1)
where the sum runs over all the pairs $`ij`$ of nearest neighbour sites, i.e. sites connected by a link. In the canonical ensemble the probability for the magnetization of the spin $`i`$ to be smaller than $`1`$ is:

$$p_i^{}=\frac{{\displaystyle \underset{\{s_1,\mathrm{}s_N\}}{\overset{s_i=1}{}}}e^{\beta /2_{ij}s_is_j}}{{\displaystyle \underset{\{s_1,\mathrm{}s_N\}}{}}e^{\beta /2_{ij}s_is_j}}$$
(2)
In the denominator we sum over all possible spin configurations with $`+1`$ boundary conditions. In the numerator over all configurations with $`+1`$ boundary conditions and the spin $`i`$ fixed to $`1`$. We will prove the spontaneous magnetization of the system by showing the existence of a temperature $`\overline{\beta }`$ such that, in the thermodynamic limit, $`\beta >\overline{\beta }`$ $`p_i^{}<ϵ<1/2`$.

The theorem will be proved in the following steps. In Section III we introduce the dual space and the loop expansion of equation (2). With this expansion, we prove that $`p_i^{}`$ can be overestimated by the sum of $`\mathrm{exp}(\beta |l|)`$ over all SOS loops enclosing $`i`$ ($`|l|`$ is the length of the loop $`l`$).

In section IV we introduce a tree representation of the SOS loops of length $`|l|`$ enclosing $`i`$ and passing the site $`\alpha `$. This representation allows us to overestimate the number of the loops as $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }_{\alpha \overline{l^{}}_i^\alpha }\stackrel{~}{z}_\alpha `$. $`\overline{l}_i^\alpha `$ is a SOS loop. The product runs over the sites belonging to $`\overline{l}_i^\alpha `$ excluding the site of highest coordination. $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$ is the coordination number of the site representing, in the tree, the site of highest coordination in $`\overline{l}_i^\alpha `$.

In section V we define the sparse high connectivity property and, using this property, we show that $`_{\alpha \overline{l^{}}_i^\alpha }\stackrel{~}{z}_\alpha \mathrm{exp}(K|l|)`$ where $`K`$ is a suitable real constant.

In section VI we prove that $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }10|l|^{\mathrm{log}_2(3)}`$. In particular we exploit the fact that $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$ is smaller than the number of the nearest neighbours, of the site of highest coordination, which can be crossed by a loop of length $`|l|`$ and surrounding $`i`$.

In section VII we show that the number of sites, which can be crossed by a SOS loop of length $`|l|`$ and surrounding $`i`$, is smaller than $`\pi (8|l|)^{2\mathrm{log}_2(3)}`$. This last estimate is proved by evaluating the maximum euclidean distance that can be covered in the dual lattice by a loop of $`|l|`$ steps. Finally we will obtain

$$p_i^{}\underset{|l|=0}{\overset{\mathrm{}}{}}C|l|^{3\mathrm{log}_2(3)}e^{(K\beta )|l|}$$
(3)
where $`C`$ is a suitable positive constant. From equation (3) we have that $`p_i^{}<ϵ<1/2`$, for small enough temperature.

Beside the sparse high coordination property, in the proof we strongly use the fact that the dual lattice is embedded in a two dimensional euclidean space and the fact that the plaquettes of the carpet are convex sets of this space.

## 3 Loop expansion

In analogy with Peierls argument, we write the Hamiltonian of the system in terms of a loop expansion. These loops belong to the dual graph of the discrete structure where the model is defined. In particular, the dual graph of the Sierpinski carpet is obtained by introducing a site $`\alpha `$ for each plaquette of the carpet. Then, two sites are connected if and only if it exists a link of the carpet separating the plaquettes relevant to the sites we are considering. Hence, there is a one to one correspondence between the links of the carpet and the links of the dual. We will call $`V_d`$ the set of the sites of the dual graph and $`E_d`$ the set of the links. Notice that the dual graph has unbounded connectivity; hence, it must be studied with a certain caution. The length (number of links) of the shortest walk connecting two sites $`V_d`$ will be called the chemical distance between them. In Figure 3 we illustrate the Sierpinski carpet and its dual graph.

Let us introduce a one-to-one correspondence between the spin configurations and the self-avoiding loops of the dual graph (self-avoiding on the links). A spin configuration with $`+1`$ boundary conditions is identified by the links of the carpet which separate the spins with $`+1`$ magnetization and the spins with $`1`$ magnetization. Since, by definition, each link of the dual graph corresponds exactly to a link of the carpet, we obtain a relation between the spin configuration and a subset $`LE_d`$. It is easy to show that the number of links in $`L`$ adjacent to the same site $`\alpha `$ is even. Therefore, $`L`$ can always be obtained as a superposition of self-avoiding (on the links) loops. If in $`L`$ there are more than two links adjacent to the same site, the decomposition of $`L`$ into loops is not unique.

On the other hand, let us call $`L`$ any subset $`E_d`$ such that for any $`\alpha V_d`$ the number of links in $`L`$ adjacent to $`\alpha `$ is even, i.e. $`L`$ can be decomposed into loops (we will call $`\overline{E}_L`$ the set of all possible $`L`$). In a unique way we can associate to $`L`$ a spin configuration with $`+1`$ boundary conditions, by fixing to $`+1`$ the spins enclosed by an even number of loops and to $`1`$ the spins enclosed by an odd number of loops. In Figure 4 we illustrate a spin configuration and its corresponding $`LE_d`$.

The energy of the spin configuration can be written in terms of the corresponding set of links $`L`$. Indeed

$$H=\frac{1}{2}\underset{ij}{}s_is_j=|E_d|+\frac{1}{4}\underset{ij}{}(s_is_j)^2$$
(4)
where $`|E_d|`$ is the total number of links of the dual graph. A link gives a contribution $`1`$ to the Hamiltonian (4), if it connects opposite spins, and zero, if it connects parallel spins. Dropping the irrelevant additive constant $`|E_d|`$, we obtain $`H=|L|`$, where $`|L|`$ is the number of links in the set $`L\overline{E}_L`$ corresponding to the spin configuration of energy $`H`$. If we consider a decomposition of $`L`$ into loops $`l`$ we obtain

$$H=|L|=\underset{l}{}|l|$$
(5)
where $`|l|`$ is the length of the loop $`l`$. The probability $`p_i^{}`$ is

$$p_i^{}=\frac{{\displaystyle \underset{L^{}\overline{E}_L^{}}{}}e^{\beta |L^{}|}}{{\displaystyle \underset{L\overline{E}_L}{}}e^{\beta |L|}}$$
(6)
In the denominator we sum over all possible sets $`L\overline{E}_L`$ and in the numerator over all subsets $`L^{}\overline{E}_L`$ such that an odd number of loops encloses the site $`i`$. $`\overline{E}_L^{}`$ denotes the set of all $`L^{}\overline{E}_L`$, such that an odd number of loops encloses $`i`$; while $`\overline{E}_L^+`$ denotes the set of all $`L^+\overline{E}_L`$, such that an even number of loops encloses $`i`$. Hence, $`\overline{E}_L=\overline{E}_L^+\overline{E}_L^{}`$.

We will call $`l_i`$ the shortest SOS loop belonging to $`L^{}`$ and surrounding $`i`$ (see Figure 5). Each set $`L^{}`$ can be considered as the union of $`l_i`$ and a suitable set of $`\overline{E}_L^+`$. Therefore, equation (6) can be written as

$$p_i^{}=\frac{{\displaystyle \underset{l_i}{}}e^{\beta |l_i|}{\displaystyle \underset{L^+\overline{E}_L^+}{}^{}}e^{\beta |L^+|}}{{\displaystyle \underset{L^+\overline{E}_L^+}{}}e^{\beta |L^+|}+{\displaystyle \underset{L^{}\overline{E}_L^{}}{}}e^{\beta |L^{}|}}$$
(7)
$`_{l_i}`$ denotes the sum over all possible SOS loops $`l_i`$ enclosing the site $`i`$. $`_{L^+\overline{E}_L^+}^{}`$ is the sum over all $`L^+\overline{E}_L^+`$ such that $`L^+l_i=\mathrm{}`$ and such that, in $`l_iL^+`$, $`l_i`$ is the shortest SOS loop surrounding $`i`$. Dropping the restriction on the sum $`_{L^+\overline{E}_L^+}^{}`$ we obtain an overestimate of $`p_i^{}`$

$$p_i^{}\frac{{\displaystyle \underset{l_i}{}}e^{\beta |l_i|}{\displaystyle \underset{L^+\overline{E}_L^+}{}}e^{\beta |L^+|}}{{\displaystyle \underset{L^+\overline{E}_L^+}{}}e^{\beta |L^+|}+{\displaystyle \underset{L^{}\overline{E}_L^{}}{}}e^{\beta |L^{}|}}\underset{l_i}{}e^{\beta |l_i|}\underset{k=0}{\overset{\mathrm{}}{}}n_i(k)e^{\beta k}$$
(8)
$`n_i(k)`$ represents the number of SOS loops of length $`k`$ enclosing $`i`$. Eventually we can write

$$p_i^{}\underset{\alpha }{}\underset{k=0}{\overset{\mathrm{}}{}}n_i^\alpha (k)e^{\beta k}$$
(9)
where $`n_i^\alpha (k)`$ is the number of SOS loops of length $`k`$, enclosing $`i`$ and passing the site $`\alpha `$ of the dual graph.

Now we take the thermodynamic limit. The theorem will be proved by showing on $`n_i^\alpha (k)`$ an exponential bound independent from $`i`$. Up to now we followed step by step the Peierls argument for the Ising model on two-dimensional lattices . However, here the dual graph is more intricate than in the two-dimensional case, since it has unbounded coordination. Hence, the proof of the bound on $`n_i^\alpha (k)`$ requires more work.

## 4 Tree representation of the loops

In order to count the SOS loops of length $`k`$, surrounding $`i`$ and starting from $`\alpha `$, we represent them into a tree. By induction on $`N`$ we prove that any set of $`N`$ SOS loops of length $`k`$, starting from $`\alpha ^{}`$, can be represented in a tree satisfying the following properties (TP).

Each site of the tree $`a`$ is associated to a site of the dual graph $`\alpha (a)`$. Nearest neighbour sites in the tree correspond to nearest neighbour sites in the dual graph. The correspondence is not one-to-one, however, if $`b`$ and $`c`$ are nearest neighbour of the same site of the tree, then they represent different sites of the dual, i.e. $`\alpha (b)\alpha (c)`$. Consequently, calling $`\stackrel{~}{z}_a`$ the coordination number of a site of the tree and $`z_\alpha `$ the coordination of a site of the dual, we have $`\stackrel{~}{z}_\alpha z_{\alpha (a)}`$. One site of the tree is called the origin $`o`$. We have $`\alpha (o)=\alpha ^{}`$ and the maximum distance of any sites of the tree from $`o`$ is $`k`$ ($`k`$ will be called the length of the tree). There are exactly $`N`$ sites at a distance of $`k`$ steps from $`o`$ and to each of them we associate, in a one-to-one correspondence, one of the loops. These sites will be called ending points $`e`$. $`\alpha (e)=\alpha ^{}`$ and they are the only ones in the tree with coordination $`1`$. Therefore, the number of loops represented in the tree can be evaluated by counting the ending points. Finally, the sites crossed in the tree by the walk of $`k`$ steps, connecting the origin to an ending point $`e`$, correspond, in a one-to-one relation, to the sites of the dual graph belonging to the loop associated to $`e`$.

The set made of any single loop can be represented by a linear chain of $`k+1`$ sites and $`k`$ links. The first site of the chain is the origin and it corresponds to $`\alpha ^{}`$, the second corresponds to the second site of the loop and so on, the last site corresponds again to $`\alpha ^{}`$ and it is the ending point of the tree.

Let us show that, if there is a tree representation for any set of $`N1`$ loops starting from $`\alpha ^{}`$, we can add to any of these sets a new loop and produce a tree representing this new set. We will proceed by adding a new chain to the tree, relevant to the $`N1`$ loops. The sites of this tree correspond, in both representations, to the same sites of the dual graph and they represent the first $`N1`$ loops. The starting point $`\alpha ^{}`$ of the new loop is naturally associated to the origin $`o`$ of the tree. Then, if one of the nearest neighbour of $`o`$ corresponds in the dual to the second site of the loop, we move to this site of the tree and check if one of its neighbours correspond to the third site of the loop and so on. Until we find that, at the step $`q`$, no neighbour of the site represents the site reached in the $`q+1`$ step of the loop. Since we are considering SOS loops (we can not move backward), this site is distant $`q`$ from the origin of the tree. Now we add to this site a bifurcation and a new chain of length $`kq`$. The first site of this new chain corresponds to the site reached in the $`q+1`$ step of the loop, the second to the site reached in the $`q+2`$ step, the last corresponds again to $`\alpha ^{}`$. So, when we add a loop to the set, we add to the tree one ending point naturally associated with the new loop. The new neighbour sites added to the tree are neighbour also in the dual. Furthermore, we never add to any site of the tree $`a`$ a new neighbour $`b`$, such that $`\alpha (b)`$ is already represented in the tree by a neighbour of $`a`$. This way, we produce a tree satisfying TP properties and representing a set of $`N`$ loops passing $`\alpha ^{}`$.

In particular, it is possible to construct the tree representing the set of all SOS loops of length $`k`$ surrounding $`i`$ and starting from $`\alpha `$. The number of these loops is equal to the number of the ending points in the tree. In Figure 6 is illustrated a tree corresponding to the all the loops of length $`7`$ passing $`\alpha =0`$ and enclosing $`i`$.

Let us consider a tree of length $`k`$ and satisfying TP. We call $`\overline{e}`$ the ending point maximizing the product $`\overline{P}_k`$ of the coordination numbers of the sites crossed by the $`k`$ steps walk connecting the origin to $`\overline{e}`$. We prove by induction on $`k`$ that the number of the ending points $`T_k`$ is smaller than $`\overline{P}_k`$.

For $`k=1`$ the tree is given by the origin and its $`\stackrel{~}{z}_o`$ neighbours which are the ending points. Hence both $`\overline{P}_1`$ and $`T_1`$ are equal to $`\stackrel{~}{z}_o`$. Let us now suppose that $`T_{k1}\overline{P}_{k1}`$ for any tree of length $`k1`$. We need to show that, given a tree of length $`k`$, $`T_k\overline{P}_k`$. Cutting the origin $`o`$ from the tree of length $`k`$, the graph is disconnected into $`\stackrel{~}{z}_o`$ subgraphs. Each of these subgraphs is a tree of length $`k1`$, satisfying TP, whose origin is one of the neighbours of $`o`$. We will denote these trees with the index $`h`$ and we will call $`T_{k1}^h`$ the number of the ending points of the tree $`h`$. $`T_k`$ is equal to the sum over $`h`$ of $`T_{k1}^h`$. Hence:

$$T_k=\underset{h=1}{\overset{\stackrel{~}{z}_o}{}}T_{k1}^h\underset{h=1}{\overset{\stackrel{~}{z}_o}{}}\overline{P}_{k1}^h\stackrel{~}{z}_o\underset{h}{\mathrm{max}}(\overline{P}_{k1}^h)$$
(10)
In the first inequality we use the fact that $`T_{k1}^h`$ and $`\overline{P}_{k1}^h`$ are, respectively, the number of the ending points and the maximum of the products of the coordination numbers in a tree of length $`k1`$. Since the origin belongs to any of the walks connecting $`o`$ to an ending point, $`\overline{P}_k`$ can be expressed as the product of $`z_o`$ and the maximum value of $`\overline{P}_{k1}^h`$. Therefore, from (10) one immediately obtains the proof.

In the tree representing all the SOS loops of length $`|l|`$ enclosing $`i`$ and passing $`\alpha `$, we will call $`\overline{w}_i^\alpha `$ the walk connecting the origin to $`\overline{e}`$ and we will call $`\overline{l}_i^\alpha `$ the loop associated to $`\overline{e}`$. We have:

$$n_i^\alpha (|l|)\underset{a\overline{w}_i^\alpha }{}\stackrel{~}{z}_a=\stackrel{~}{Z}_{\overline{l}_i^\alpha }\underset{a\overline{w^{}}_i^\alpha }{}\stackrel{~}{z}_a\stackrel{~}{Z}_{\overline{l}_i^\alpha }\mathrm{exp}\left(\underset{\gamma \overline{l^{}}_i^\alpha }{}\mathrm{log}(z_\gamma )\right)$$
(11)
$`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$ is the coordination number of the tree site $`m`$ corresponding to the site $`\mu `$ of the loop $`\overline{l}_i^\alpha `$ with the highest coordination in the dual graph (if the sites of highest coordination are more than one, we arbitrarily chose one of them). $`\overline{w^{}}_i^\alpha `$ and $`\overline{l^{}}_i^\alpha `$ are obtained by subtracting from the walk $`\overline{w}_i^\alpha `$ and the loop $`\overline{l}_i^\alpha `$, respectively, $`m`$ and $`\mu `$. In the last inequality we use the one-to-one correspondence between $`\overline{w^{}}_i^\alpha `$ and $`\overline{l^{}}_i^\alpha `$ and fact that the coordination number $`\stackrel{~}{z}_a`$ of the sites of the tree is smaller or equal than the coordination number $`z_{\gamma (a)}`$ of the relevant sites of the dual graph.

## 5 Sparse high connectivity

In the dual graph the possible values of the coordination numbers are $`43^m`$ with $`m=0,1,\mathrm{}`$. Hence we have

$$n_i^\alpha (|l|)\stackrel{~}{Z}_{\overline{l}_i^p}\mathrm{exp}\left(\underset{m}{}N_{\overline{l^{}}_i^\alpha }(m)(\mathrm{log}(4)+m\mathrm{log}(3))\right)$$
(12)
$`N_{\overline{l^{}}_i^\alpha }(m)`$ is the number of sites in $`\overline{l^{}}_i^\alpha `$ with coordination number in the dual graph equal to $`43^m`$.

The minimum chemical distance $`d(m)`$ between two sites of the dual graph with coordination greater or equal than $`43^m`$ is:

$$d(m)=\{\begin{array}{cc}1& \mathrm{if}m=0\hfill \\ 2^{m+1}& \mathrm{if}m>0\hfill \end{array}$$
(13)
Equation (13) represents the fundamental topological property of the dual graph of the Sierpinski carpet which will allow us to prove the exponential bound on $`n_i(k)`$, even in absence of bounded coordination. We will call this property sparse high connectivity, since it implies that, in the topology of the dual graph generated by the chemical distance, sites with high coordination are far apart.

For a SOS loop $`l`$, the sites with coordination $`43^m`$ are less than $`1+|l|/d(m)`$. Since in $`\overline{l^{}}_i^\alpha `$ we have excluded the point of highest coordination, we can overestimate the number of sites of coordination $`43^m`$ as:

$$N_{\overline{l^{}}_i^\alpha }(m)\frac{|l|}{d(m)}$$
(14)
From (14) we obtain that, if $`m>\mathrm{log}_2(l)1=m_M`$, then $`N_{\overline{l^{}}_i^\alpha }(m)=0`$. Therefore, $`m_M`$ represents the maximum value of $`m`$ on the sites of $`\overline{l^{}}_i^\alpha `$.

Thus we have:

$`n_i^\alpha (l)`$ $``$ $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }\mathrm{exp}\left(|l|\mathrm{log}(4)+l{\displaystyle \underset{m}{\overset{m_M}{}}}2^{m1}(\mathrm{log}(4)+m\mathrm{log}(3))\right)`$ (15)
$``$ $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }\mathrm{exp}\left(|l|\mathrm{log}(4)+l{\displaystyle \underset{m}{\overset{\mathrm{}}{}}}2^{m1}(\mathrm{log}(4)+m\mathrm{log}(3))\right)`$
$``$ $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }\mathrm{exp}\left(K|l|\right)`$
where $`K`$ is a suitable positive, real constant.

## 6 The site of highest coordination

In this section we will show that $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }10l^{\mathrm{log}_2(3)}`$. If $`z_\mu 10l^{\mathrm{log}_2(3)}`$ ($`\mu `$ is the site in the dual graph with highest coordination), the inequality is trivially satisfied. Otherwise, we will use the fact that $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$ is the coordination of a site of a tree representing SOS loops surrounding $`i`$. Two sites of the tree are neighbour only if the corresponding sites of the dual are neighbours and it exists a SOS loop passing through them and enclosing $`i`$. Therefore, the bound on $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$ is proved by showing that the $`Z_{\mu ,\overline{l}_i}10l^{\mathrm{log}_2(3)}`$; where $`Z_{\mu ,\overline{l}_i}`$ represents the number of nearest neighbours of $`\mu `$, which can be crossed by a SOS walk of length $`|l|`$, passing $`\mu `$ and enclosing $`i`$.

Let $`\nu `$ and $`\rho `$ be nearest neighbour of $`\mu `$. We define the distance along the boundary $`\overline{r}_{\nu ,\rho }`$ as in Figure 7. In Figure 7 the plaquette of the site $`\mu `$ is also defined.

Let us consider a SOS loop $`l^{\nu ,\rho }`$ of length $`|l|`$ passing $`\mu `$ and its nearest neighbours $`\rho `$ and $`\nu `$. We will prove that:

$$\overline{r}_{\nu ,\rho }2|l|^{\mathrm{log}_2(3)}.$$
(16)
Furthermore, if $`l^{\nu ,\rho }`$ encloses the site of the carpet $`i`$, from the planarity of the dual graph we have the following property: no loop of length $`|l|`$ passing $`\mu `$ and enclosing $`i`$ can pass through any site $`\tau `$ of the plaquette of $`\mu `$, such that $`\tau `$ is located with respect to $`\rho `$ in the opposite direction of $`\nu `$ at a distance $`\overline{r}_{\tau ,\rho }>4l^{\mathrm{log}_2(3)}`$.

An analogous property holds for the sites of the plaquette at a distance greater than $`4l^{\mathrm{log}_2(3)}`$ from $`\nu `$ in the direction opposite to $`\rho `$. Therefore, since $`\overline{r}_{\nu ,\rho }2|l|^{\mathrm{log}_2(3)}`$, the number $`Z_{\mu ,\overline{l}_i}`$ of sites belonging to the plaquette of $`\mu `$ and crossed by a loop passing $`\mu `$ and surrounding $`i`$ is smaller than $`10|l|^{\mathrm{log}_2(3)}`$. This way we obtained the bound on $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$.

Let us prove (16). The dual graph is naturally embedded in a two dimensional euclidean space. Since the plaquettes are convex subsets of this space, the length of the border $`\overline{r}_{\nu ,\rho }`$ turns out to be smaller than the length, in the euclidean space, of any walk from $`\nu `$ to $`\rho `$ which do not pass through the plaquette itself. In particular, it is smaller than the length of $`l^{\nu ,\rho }`$. $`l^{\nu ,\rho }`$ is the walk obtained subtracting $`\mu `$ from the loop $`l^{\nu ,\rho }`$. Now, a step in the dual graph, crossing a site with coordination $`z_\rho `$, covers, in the euclidean space, a distance smaller than $`z_\rho /2`$. We have:

$$\overline{r}_{\nu ,\rho }\frac{1}{2}\underset{\rho l^{\nu ,\rho }}{}z_\rho 2\underset{m}{\overset{m_M}{}}N_{l^{\nu ,\rho }}(m)3^m2l+l\underset{m}{\overset{\mathrm{log}_2(|l|)1}{}}\left(\frac{3}{2}\right)^m2l^{\mathrm{log}_2(3)}$$
(17)
$`N_{l^{\nu ,\rho }}(m)`$ is the number of sites in $`l^{\nu ,\rho }`$ with coordination $`43^m`$. In equation (17) $`N_{l^{\nu ,\rho }}(m)`$ has been estimated using inequality (14).

Now we need to prove that no that no loop of length $`|l|`$ passing $`\tau `$ and $`\mu `$ can enclose the site $`i`$. We suppose, ad absurdum, the existence of this loop and we call it $`l^{\tau ,\sigma }`$ ($`\sigma `$ is the other site of the loop belonging to the plaquette of $`\mu `$). Since $`\tau `$ and $`\sigma `$ are connected by a loop of length $`|l|`$, from (16) we have $`\overline{r}_{\tau ,\sigma }<2|l|^{\mathrm{log}_2(3)}`$. Hence $`\overline{r}_{\rho ,\sigma }>2|l|^{\mathrm{log}_2(3)}`$. If also $`l^{\tau ,\sigma }`$ surrounded $`i`$, for the planarity of the dual graph, there should exist two sites $`\gamma `$ and $`\delta `$ belonging both to $`l^{\tau ,\sigma }`$ and to $`l^{\nu ,\rho }`$ (see Figure 8 for an illustration).

We denote with $`|\gamma ,\delta |_{l^{\tau ,\sigma }}`$ the length of the part of the walk $`l^{\tau ,\sigma }`$ within the sites $`\gamma `$ and $`\delta `$. We have

$`|\rho ,\delta |_{l^{\nu ,\rho }}+|\delta ,\gamma |_{l^{\nu ,\rho }}+|\gamma ,\nu |_{l^{\nu ,\rho }}=|l|2`$
$`|\sigma ,\delta |_{l^{\tau ,\sigma }}+|\delta ,\gamma |_{l^{\tau ,\sigma }}+|\gamma ,\tau |_{l^{\tau ,\sigma }}=|l|2`$ (18)
and then:

$$|\rho ,\delta |_{l^{\nu ,\rho }}+|\gamma ,\nu |_{l^{\nu ,\rho }}+|\sigma ,\delta |_{l^{\tau ,\sigma }}+|\gamma ,\tau |_{l^{\tau ,\sigma }}2(|l|2)$$
(19)
On the other hand, since $`\overline{r}_{\nu ,\tau }>|l|^{\mathrm{log}_2(3)}`$ and $`\overline{r}_{\rho ,\sigma }>|l|^{\mathrm{log}_2(3)}`$, from (16) we get

$`|\rho ,\delta |_{l^{\nu ,\rho }}+|\sigma ,\delta |_{l^{\tau ,\sigma }}>|l|2`$
$`|\nu ,\gamma |_{l^{\nu ,\rho }}+|\tau ,\gamma |_{l^{\tau ,\sigma }}>|l|2`$ (20)
and then

$$|\rho ,\delta |_{l^{\nu ,\rho }}+|\sigma ,\delta |_{l^{\tau ,\sigma }}+|\nu ,\gamma |_{l^{\nu ,\rho }}+|\tau ,\gamma |_{l^{\tau ,\sigma }}>2(|l|2)$$
(21)
Equation (21) can not hold together with equation (19). Therefore, assuming the existence of the site $`\tau `$, we obtained the contradiction we wanted to prove. Hence, we have concluded the proof of the bound on $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$.

## 7 Euclidean length of a loop

With the bound on $`\stackrel{~}{Z}_{\overline{l}_i^\alpha }`$ proved in the previous section, we obtain that probability for the site $`i`$ to have negative magnetization can be estimated as

$$p_i^{}\underset{|l|=0}{\overset{\mathrm{}}{}}N_i(|l|)10|l|^{\mathrm{log}_2(3)}e^{(K\beta )|l|}$$
(22)
$`N_i(|l|)`$ is the number of points in the dual lattice which can be crossed by a SOS of length $`|l|`$ which encloses $`i`$.

An estimate of $`N_i(|l|)`$ can be obtained by using again the fact that the dual graph is embeddable in a two-dimensional euclidean space. In particular, in a walk in the dual graph, a step crossing the site $`\alpha `$ covers in the euclidean space a distance smaller or equal than $`z_\alpha ^{}=\overline{r}_{\alpha ^{},\alpha ^+}`$, where $`\alpha ^{}`$ and $`\alpha ^+`$ are respectively the sites preceding and following $`\alpha `$ within the walk. Let us consider $`l_i`$ SOS loop in the dual graph of length $`|l|`$ and enclosing the site $`i`$ of the carpet. We call $`d(l_i)`$ the distance covered by this loop in the euclidean space, we get

$$d(l_i)\underset{\alpha l_i}{}z_\alpha ^{}Z_{l_i}^{}+\underset{\alpha l_i^{}}{}z_\alpha $$
(23)
In the sum we separate the contribution of the site with highest coordination number and we used the simple property that $`z_\alpha ^{}<z_\alpha `$. $`Z_{\overline{l}_i}^{}`$ represents the distance along the boundary between the sites preceding and following the site of highest coordination number in a walk of length $`|l|`$. In the previous section we proved that $`Z_{\overline{l}_i}^{}2l^{\mathrm{log}_2(3)}`$. Furthermore the sum over all sites belonging to $`l_i^{}`$ has been already evaluated in (17). Therefore we have that

$$d(l_i)8|l|^{\mathrm{log}_2(3)}$$
(24)
The number of sites of the dual graph, distant from $`i`$ in the euclidean space less than $`d(l_i)`$ it is smaller than $`\pi d^2(l_i)`$. Therefore we obtain that $`N_i(l)\pi (8|l|^{\mathrm{log}_2(3)})^2`$. Hence

$$p_i^{}\underset{|l|=0}{\overset{\mathrm{}}{}}C|l|^{3\mathrm{log}_2(3)}e^{(K\beta )|l|}$$
(25)
where $`C`$ is a suitable real constant. For small enough values $`\beta `$ the sum in (25) is smaller than $`ϵ<1/2`$. Thus we obtain the uniform bound on $`p_i^{}`$ proving the existence of spontaneous magnetization at finite temperature.

The author is grateful to R. Burioni and D. Cassi for useful comments and discussions.

## References


text:
# Cycles in 𝐺-orbits in 𝐺^ℂ-flag manifolds

## 0 Introduction and Notation

Let $`G`$ be a non-compact semi-simple Lie group without compact factors which is embedded in its complexification $`G^{}`$ and let $`Z=G^{}/Q`$ be a $`G^{}`$-flag manifold, i.e., a compact, homogeneous, algebraic $`G^{}`$-manifold. Denote by $`K`$ a maximal compact subgroup of $`G`$; in particular $`G/K`$ is a negatively curved Riemannian symmetric space. In the sequel we will assume that $`G`$ is simple. The necessary adjustments for the semi-simple case are straight-forward.

Let $`Orb_Z(G)`$ (resp. $`Orb_Z(K^{})`$) denote the set of $`G`$-orbits (resp. $`K^{}`$-orbits) in $`Z`$. It is known that these sets are finite (\[W1\]). If $`\kappa Orb_Z(K^{})`$ and $`\gamma Orb_Z(G)`$, then $`(\kappa ,\gamma )`$ is said to be a dual pair if $`\kappa \gamma `$ is non-empty and compact.

If $`\gamma `$ is an open $`G`$-orbit, then $`\kappa `$ being dual to $`\gamma `$ is equivalent to $`\kappa \gamma `$. In (\[W1\]) it is shown that every open $`G`$-orbit contains a unique compact $`K^{}`$-orbit, i.e., duality at the level of open $`G`$-orbits. This is extended in (\[M\], see also \[BL\] and \[MUV\]) to the case of all orbits: For every $`\gamma Orb_Z(G)`$ there exists a unique $`\kappa Orb_Z(K^{})`$ such that $`(\gamma ,\kappa )`$ is a dual pair and vice versa. Furthermore, if $`(\gamma ,\kappa )`$ is a dual pair then the intersection $`\kappa \gamma `$ is transversal at each of its points and consists of exactly one $`K`$-orbit.

To motivate the notion of a cycle in this case, let us begin with the case of an open $`G`$-orbit $`D`$. The dual orbit $`\kappa `$ defines a point in the cycle space $`𝒞^q(D)`$, where $`q:=dim_{}\kappa `$. The connected component $`\mathrm{\Omega }_W(D)`$ of $`\{gG^{}:g(\kappa )D\}`$ can be regarded as a family of cycles by the procedure of associating $`g`$ to the cycle $`g(\kappa )`$. Clearly $`\mathrm{\Omega }_W(D)`$ is invariant by the action of $`K^{}`$ on $`G^{}`$ on the right and therefore we often regard it as being in the affine homogenous space $`\mathrm{\Omega }:=G^{}/K^{}`$.

The cycle space $`C(\gamma )`$ associated to a lower-dimensional orbit is defined analogously, at least when one has duality in mind: $`C(\gamma )`$ is the connected component containing the identity of the interior of the set

$$\{gG^{}:g(\kappa )\gamma \text{ is non-empty and compact}\}.$$

Since the intersection $`\kappa \gamma `$ is transversal, it is clear that $`C(\gamma )`$ is non-empty

Here, in a result that we state at the outset, it is shown that this is in fact a reasonable set. The following is proved in $`\mathrm{\S }\text{2}`$.

###### Proposition 1.

If $`gC(\gamma )`$, then $`g(\text{c}\mathrm{}(\kappa ))\text{c}\mathrm{}(\gamma )=:M_g`$ is a compact subset of $`g(\kappa )\gamma `$. This intersection is transversal at each of its points and the manifold $`M_g`$ is homotopic in $`\gamma `$ to $`M=M_e`$. If $`g\text{bd}(C(\gamma ))`$, then either $`g(\kappa )\gamma `$ is non-compact or empty. In particular, if $`\{g_n\}`$ is a divergent sequence in $`C(\gamma )`$, then there exists $`z_ng_(\kappa )\gamma `$ with $`\{z_n\}`$ divergent in $`\gamma `$.

In the sequel we take this to be the meaning of the cycle space $`C(\gamma )`$ and regard the manifolds $`M_g`$ as cycles. Just as in the case of open orbits, we often regard $`C(\gamma )`$ as a $`G`$-invariant domain in $`\mathrm{\Omega }`$.

Our main result is the complete characterization of the cycle spaces $`C(\gamma )`$ in the case where $`G`$ is non-Hermitian, where our contribution is in the case of the non-open orbits. For a given group $`G`$ these cycle spaces are all naturally biholomorphically isormorphic to a fixed domain which, when realized in $`\mathrm{\Omega }`$, is denoted by $`\mathrm{\Omega }_{AG}`$ (see Thm. 9).

This domain was discussed in (\[C\]) in the context of differential geometry. If $`G\times _K𝔭`$ is the tangent bundle of the Riemannian symmetric space $`M=G/K`$, then $`\mathrm{\Omega }_{AG}`$ is identified by the polar coordinates map $`𝒫:TM\mathrm{\Omega }`$, $`[(g,\xi )]gexp(i\xi )`$, with the maximal neighborhood of the $`0`$-section on which $`𝒫`$ is a local diffeomorphism. It was considered in (\[AG\]) from the point of view of neigborhoods of $`M`$ in $`\mathrm{\Omega }`$ on which $`G`$ acts properly. It is known to be a Stein domain and its complex geometry is closely related to the Riemannian geometry of the symmetric space $`M`$ (\[BHH\]).

In terms of roots, if $`𝔤=𝔨+𝔞+𝔫`$ is an Iwasawa-decomposition, $`\mathrm{\Phi }`$ is a system of roots on $`𝔞`$ and $`\omega _{AG}`$ is the connected component containing $`0𝔞`$ of the set which is obtained by removing from $`𝔞`$ the union affine hyperplanes

$$\underset{\alpha \mathrm{\Phi }}{}\{\xi 𝔞:\alpha (\xi )=\frac{\pi }{2}\}.$$

Then $`\mathrm{\Omega }_{AG}=Gexp(i\omega _{AG}).x_0`$, where $`x_0G^{}/K^{}`$ is the base point.

Using a certain triality and related incidence varieties (\[HW1\]) along with $`G`$-invariant theoretic properties and the Kobayashi hyperbolicity of $`\mathrm{\Omega }_{AG}`$ (\[H\],\[FH\]), it has been recently shown that, with a few well-known Hermitian exceptions where $`\mathrm{\Omega }_W(D)`$ is the associated bounded symmetric domain, the cycle domain $`\mathrm{\Omega }_W(D)`$ of an open orbit is naturally identifiable with $`\mathrm{\Omega }_{AG}`$.

Our work here makes use of the methods and results of these papers along with a result of (\[GM\]) which, together with knowledge of the intersection of the cycle domains for the open orbits in $`G^{}/B`$, implies the inclusion $`\mathrm{\Omega }_{AG}C(\gamma )`$ for all $`\gamma Orb_Z(G)`$.

For a survey of these and other basic properties of $`\mathrm{\Omega }_{AG}`$ see (\[HW2\]).

## 1 Basic triality

Here $`B`$ denotes a Borel subgroup of $`G^{}`$ which contains the factor $`AN`$ of an Iwasawa decomposition $`G=KAN`$. As usual the closure $`S`$ of a $`B`$-orbit $`O`$ in $`Z`$ is referred to as a Schubert variety. Let $`Y:=SO`$.

Since the set of Schubert varieties $`𝒮`$ generates the homology of $`Z`$, for every $`\kappa Orb_Z(K^{})`$ the set

$$𝒮_\kappa :=\{S𝒮:S\text{c}\mathrm{}(\kappa )\mathrm{}\}$$

is non-empty. The following is a slightly refined version of Thm. 3.1 of (\[HW1\]).

###### Theorem 2.

Let $`(\kappa ,\gamma )`$ be a dual pair and $`S𝒮_\kappa `$. Then

1. $`S\text{c}\mathrm{}(\kappa )\kappa \gamma `$
2. The intersection $`S\gamma `$ is open in $`S`$ and consists of finitely many $`AN`$-orbits each of which is open in $`S`$ and closed in $`\gamma `$.
3. If $`z_0S\gamma `$, then $`\mathrm{\Sigma }:=(AN).z_0`$ intersects $`\kappa `$ in exactly one point and that interesection is transversal in $`Z`$.

The only refinement is that, instead of $`\mathrm{\Sigma }\kappa `$ being finite, we now show that it consists of just one point. This is implicit in \[HW1\] (see $`\mathrm{\S }5`$ in that paper). Let us repeat the relevant details.

Let $`\alpha :K_{z_0}\times (AN)_{z_0}G_{z_0}`$ be defined by multiplication, $`(k,an)kan`$. As was shown in (\[HW1\]) $`\alpha `$ is a diffeomorphism onto a number of components of $`G_{z_0}`$. However, since the orbit $`M:=K.z_0`$ is a strong deformation retract of $`\gamma `$, it follows that $`G_{z_0}/K_{z_0}`$ is connected and consequently $`\alpha `$ is surjective. Thus $`|\mathrm{\Sigma }\kappa |=1`$ is proved just as in Cor. 5.2 of (\[HW1\]). $`\mathrm{}`$

Given $`\gamma `$,$`\kappa `$, an Iwasawa-decomposition $`G=KAN`$, a Borel subgroup $`B`$ of $`G^{}`$ which contains $`AN`$, a $`B`$ Schubert variety $`S𝒮_\kappa `$ and an intersection point $`z_0\kappa S`$ as above, we refer to $`\mathrm{\Sigma }=AN.z_0`$ as the associated Schubert slice. Note that $`G`$-conjugation yields a $`G_p`$-invariant family of Schubert slices $`\mathrm{\Sigma }`$ at every point $`p\gamma `$.

It should also be noted that in the case that $`\gamma =\gamma _\text{c}\mathrm{}`$ is closed, $`\mathrm{\Sigma }`$ is just the associated $`B`$-fixed point.

## 2 Cycle transversality

Our main goal here is to prove Prop.$`\mathrm{\hspace{0.17em}1}`$. The first step is to show that if $`g(\kappa )\gamma `$ is compact, the intersection of the variety $`g(\text{c}\mathrm{}(\kappa ))`$ with every Schubert slice $`\mathrm{\Sigma }`$ has optimal transversality properties.

###### Lemma 3.

For all $`gG^{}`$ with $`g(\kappa )\gamma `$ compact the number of points in the intersection $`g(\kappa )\mathrm{\Sigma }`$ is bounded by the intersection number $`S.\text{c}\mathrm{}(\kappa )`$.

###### Proof.

Since $`\mathrm{\Sigma }`$ can be regarded as a domain in $`O^n`$ and $`g(\kappa )\gamma `$ is compact, it follows from the maximum principle that $`g(\kappa )\mathrm{\Sigma }`$ is finite and of course it is then bounded by the the intersection number $`S.\text{c}\mathrm{}(\kappa )`$. ∎

It should be underlined that, since $`|g(\kappa )\mathrm{\Sigma }|`$ is finite, it is semi-continuous in the sense that it can only increase as $`g`$ moves away from $`g_0`$.

Let

$$I:=\{gG^{}:|g(\kappa )\mathrm{\Sigma }|=1\text{ for all }\mathrm{\Sigma }\}$$

Here for all $`\mathrm{\Sigma }`$ means for all choices of the maximal compact group $`K`$ and all Iwasawa factors $`AN`$, i.e., all Schubert slices which arise by $`G`$-conjugation of those $`\mathrm{\Sigma }`$ which are connected components of $`S\gamma `$ for a fixed $`S𝒮_\kappa `$.

We now consider the open set $`IC(\gamma )`$.

###### Lemma 4.

If $`g\text{bd}(C(\gamma )I)`$, then either $`g(\kappa )\gamma `$ is empty or non-compact. In particular, $`C(\gamma )I`$.

###### Proof.

We may assume that $`gI`$, because if $`gI`$ and $`g(\kappa )\gamma `$ is compact, then both conditions hold in an open neighborhood of $`g`$ and consequently $`gC(\gamma )`$.

We assume that $`g(\kappa )\gamma `$ is compact and reach a contradiction. For this let $`\stackrel{~}{M}`$ be the limiting set of the sequence of manifolds $`M_n:=g_n(\kappa )\gamma `$. Since $`C(\gamma )`$ is by definition connected and $`M_e`$ is connected, it follows that $`\stackrel{~}{M}`$ is a connected closed set.

Since $`g(\kappa )\gamma `$ is compact, it follows that $`\stackrel{~}{M}\gamma `$ is compact and is therefore closed in $`\stackrel{~}{M}`$. On the other hand $`\stackrel{~}{M}\text{bd}(\gamma )`$ is closed in $`\stackrel{~}{M}`$ and consequently $`\stackrel{~}{M}\gamma `$ is also open in $`\stackrel{~}{M}`$. By the semicontinuity of the intersection number and the fact that $`gI`$, $`\stackrel{~}{M}\mathrm{\Sigma }_0=\mathrm{}`$ for some Schubert slice $`\mathrm{\Sigma }_0`$. In particular, since $`|M_n\mathrm{\Sigma }_0|=1`$ for all $`n`$, $`\stackrel{~}{M}\gamma `$. Since $`\stackrel{~}{M}`$ is connected, it follows that $`\stackrel{~}{M}\gamma =\mathrm{}`$.

But $`g(\kappa )\gamma `$ is non-empty. So there exists $`p\gamma `$ and an open neighborhood $`U(p)`$ so that $`g_n(\kappa )U=\mathrm{}`$, but $`pg(\kappa )`$. On the other hand, if $`\mathrm{\Sigma }`$ is a Schubert slice at $`p`$, and $`p`$ were isolated in $`g(\kappa )\mathrm{\Sigma }`$, it would follow that $`g_n(\kappa )U\mathrm{\Sigma }`$ is non-empty for $`n`$ sufficiently large. ∎

Proof of Proposition 1. Observe that if $`gC(\gamma )`$ and $`g(\text{c}\mathrm{}(\kappa ))\text{c}\mathrm{}(\gamma )`$ contained an additional point $`p\text{bd}(\gamma )`$ or in $`\text{bd}(\kappa )`$, then for $`hC(\gamma )`$ chosen appropriately, in particular small, we would find some $`\mathrm{\Sigma }_0`$ which contains $`h(p)`$ as well as another point in $`M_{hg}`$. This is contrary to the fact that $`C(\gamma )I`$ and that this intersection contains exactly one point.

The transversality of the intersection and the properties of $`M_g`$ are also immediate consequences of $`C(\gamma )`$ being connected and contained in $`I`$.

If $`g\text{bd}(C(\gamma ))`$, then, again since $`C(\gamma )I`$, by Lemma 4 $`g(\kappa )\gamma `$ is either empty or non-compact. $`\mathrm{}`$

## 3 Description of the cycle spaces

### 3.1 Lifting cycle spaces

The above transversality results are only useful in the case when $`\gamma `$ is not closed. Here we prove a Lifting Lemma which will be used to understand the cycle space $`C(\gamma _\text{c}\mathrm{})`$ of the closed orbit. For this let $`Z=G^{}/P`$ as usual, let $`\stackrel{~}{Z}=G^{}/\stackrel{~}{P}`$ be defined by a parabolic group $`\stackrel{~}{P}`$ which is contained in $`P`$ and $`\pi :\stackrel{~}{Z}Z`$ is the natural projection.

###### Proposition 5.

If $`(\gamma ,\kappa )`$ is a dual pair of orbits in $`Z`$ with $`z_0\gamma \kappa `$ and $`\stackrel{~}{z}_0`$ is in a closed $`G_{z_0}`$-orbit in the fiber $`F:=\pi ^1(z_0)`$, then $`\stackrel{~}{\gamma }:=G.z_0`$ and $`\stackrel{~}{\kappa }:=K^{}.z_0`$ define a dual pair $`(\stackrel{~}{\gamma },\stackrel{~}{\kappa })`$ in $`\stackrel{~}{Z}`$. Furthermore, the mapping $`\pi |\stackrel{~}{\gamma }:\stackrel{~}{\gamma }\gamma `$ is proper.

###### Proof.

Since $`K_{z_0}`$ is a maximal compact subgroup of $`G_{z_0}`$, it acts transitively on the compact orbit $`G_{z_0}.\stackrel{~}{z}_0`$. Consequently $`\stackrel{~}{\gamma }F=K_{z_0}.\stackrel{~}{z}_0`$ and, since $`\gamma \kappa =K.z_0`$, it follows that $`\stackrel{~}{\gamma }\stackrel{~}{\kappa }=K.\stackrel{~}{z}_0`$.

The properness of $`\pi |\stackrel{~}{\gamma }`$ follows immediately from the fact that it is a homogenous fibration with compact fiber. ∎

In the following result we maintain the above notation.

###### Proposition 6.

If $`\gamma `$ is not closed, then $`C(\gamma )C(\stackrel{~}{\gamma })`$

###### Proof.

Let $`\{g_n\}`$ be a sequence in $`C(\stackrel{~}{\gamma })`$ which converges to $`g\text{bd}(C(\stackrel{~}{\gamma })`$. By Prop.1 there is a sequence $`\stackrel{~}{z}_n`$ in $`g_n(\stackrel{~}{\kappa })\stackrel{~}{\gamma }`$ which diverges in $`\stackrel{~}{\gamma }`$. Since $`\pi |\stackrel{~}{\gamma }`$ is proper, the corresponding sequence $`z_n`$ in $`C(\gamma )`$ is also divergent.

Now either $`g_nC(\gamma )`$ infinitely often, in which case $`gC(\gamma )`$ or we may assume that $`\{g_n\}C(\gamma )`$. In the latter case, since $`z_ng_n(\kappa )\gamma `$ is divergent in $`\gamma `$ it likewise follows that $`gC(\gamma )`$.

Hence $`\text{bd}(C(\stackrel{~}{\gamma }))C(\gamma )=\mathrm{}`$ and the desired result follows. ∎

Finally, let $`\gamma `$ be such that $`\text{c}\mathrm{}(\gamma )`$=$`\gamma \dot{}\gamma _\text{c}\mathrm{}`$ and $`\stackrel{~}{\gamma }`$ be as above. If $`g_nC(\gamma )`$ converges to $`g\text{bd}(C(\gamma ))`$, then, again by Prop.1, it follows that $`g(\text{c}\mathrm{}(\kappa ))\gamma _\text{c}\mathrm{}\mathrm{}`$. Consequently, $`C(\gamma _\text{c}\mathrm{})C(\gamma )`$.

Thus, in the notation above, we have the following consquence.

###### Corollary 7.

$`C(\gamma _\text{c}\mathrm{})C(\gamma )C(\stackrel{~}{\gamma })`$

### 3.2 Proof of the main theorem

Let us first consider the case where $`\gamma `$ is not closed and let $`S𝒮_\kappa `$ as above. Since $`\kappa S\gamma `$ already realizes the intersection number $`S.\text{c}\mathrm{}(\kappa )`$, it follows that $`g(\text{c}\mathrm{}(\kappa ))Y=\mathrm{}`$ for all $`gC(\gamma )`$.

From now on we regard the homogeneous space $`\mathrm{\Omega }=G^{}/K^{}`$ as a family of $`q`$-dimensional cycles, $`q:=dim_{}\kappa `$, via the identification of $`gC(\gamma )`$ with the cycle $`g(\text{c}\mathrm{}(\kappa ))`$.

Since $`Y:=SO`$ can be given the structure of a very ample divisor in $`S`$, it follows that incidence variety of all $`q`$-dimensional cycles $`C`$ with $`CY\mathrm{}`$ contains a complex hypersurface which pulls back to a complex hypersurface $`H\mathrm{\Omega }`$ (\[BK\],\[BM\]).

By the method of (\[BK\]), for $`f\mathrm{\Gamma }(S,𝒪(Y))`$ an appropriately chosen meromorphic function with poles along $`Y`$, the trace-transform $`Tr(f)`$ has a non-empty polar set $`P`$ which is the union of a certain number of components of $`H`$. Apriori it is possible that there are cycles $`gC(\gamma )`$ with $`\text{c}\mathrm{}(g(\kappa ))Y\mathrm{}`$, but with $`|\text{c}\mathrm{}(g(\kappa ))\mathrm{\Sigma }|=S.\text{c}\mathrm{}(g(\kappa ))`$. These would necessarily have positive-dimensional intersection with $`S`$ and the non-discrete components would lie in $`S\mathrm{\Sigma }`$.

However, this phenomenon occurs on a lower-dimensional subvariety in $`\mathrm{\Omega }`$, and such cycles are limits of generic cycles which intersect $`S`$ only in points of $`\mathrm{\Sigma }`$ and of course at only finitely many points which are bounded away from $`Y`$. Thus the value of $`Tr(f)`$ at $`g(\text{c}\mathrm{}(g(\kappa ))`$ is finite and therefore such cycles are not in $`P`$. As a consequence $`PC(\gamma )=\mathrm{}`$ and we redefine $`H`$ to be $`P`$ in the sequel.

###### Proposition 8.

If $`\gamma `$ is not closed, then there exists a Borel subgroup $`B`$ which contains a factor $`AN`$ of an Iwasawa-decomposition $`G=KAN`$ and a $`B`$-invariant hypersurface $`H`$ in $`\mathrm{\Omega }`$ so that $`\mathrm{\Omega }_{AG}C(\gamma )\mathrm{\Omega }_H`$

###### Proof.

From the characterization of cycle spaces of the open $`G`$-orbits (\[HW1\],\[FH\]) it follows in particular that the intersection of all such cycle spaces for the open orbits in $`G^{}/B`$ is $`\mathrm{\Omega }_{AG}`$ (This intersection property also follows in most cases from the results in \[GM\]). By Prop. 8.1 of (\[GM\]) it then follows that

$$\mathrm{\Omega }_{AG}C(\gamma ).$$

In the case of a non-closed orbit we have the $`B`$-invariant hypersurface $`H`$ in the complement of $`C(\gamma )`$ and, since $`C(\gamma )`$ is $`G`$-invariant and contains the base point in $`\mathrm{\Omega }_{AG}`$ it follows that it is contained in the connected component of

$$\mathrm{\Omega }(\underset{kK}{}k(H))$$

which by definition is $`\mathrm{\Omega }_H`$. ∎

###### Theorem 9.

If $`G`$ is not of Hermitian type, then

$$C(\gamma )=\mathrm{\Omega }_{AG}$$

for all $`\gamma Orb_Z(G)`$.

###### Proof.

Since $`G`$ is non-Hermitian, $`\mathrm{\Omega }_H`$ is Kobayashi hyperbolic (see \[H\],\[FH\]) and the main theorem of (\[FH\]) can therefore be applied: A $`G`$-invariant, Stein, Kobayashi hyperbolic domain containing $`\mathrm{\Omega }_{AG}`$ is $`\mathrm{\Omega }_{AG}`$ itself. Thus $`\mathrm{\Omega }_{AG}=\mathrm{\Omega }_H`$ and the result for non-closed orbits follows from from Prop.8.

By Cor. 7 it then follows that $`C(\gamma _\text{c}\mathrm{})\mathrm{\Omega }_{AG}`$. But, if $`\stackrel{~}{Z}=G^{}/B`$, it is clearly the case that $`C(\stackrel{~}{\gamma }_\text{c}\mathrm{})C(\gamma _\text{c}\mathrm{})`$ and it is known that $`C(\stackrel{~}{\gamma }_\text{c}\mathrm{})=\mathrm{\Omega }_{AG}`$ (\[B\],\[H\], see also \[FH\]). Thus, $`C(\gamma _\text{c}\mathrm{})\mathrm{\Omega }_{AG}`$ and the result is proved for closed orbits as well. ∎

It should be remarked that we actually only use the Kobayashi hyperbolicity of $`\mathrm{\Omega }_H`$ and that one might expect the following result in the Hermitian case: If $`\mathrm{\Omega }_H`$ is not Kobayashi hyperbolic, then $`C(\gamma )`$ can be identified with the bounded Hermitian symmetric space associated with $`G`$.

Note added in proof. With a few added details which we note here, we also handle the Hermitian case. For this assume that $`G`$ is of Hermitian type and let $`P`$ be a complex subgroup of $`G^{}`$ which properly contains $`K^{}`$. Then $`X:=G^{}/P`$ is a compact Hermitian symmetric space. There are only two choices for $`P`$ and the (open) $`G`$-orbit of the neutral point in $`X`$ is the bounded Hermitian symmetric domain $``$ or its conjugate $`\overline{}`$.

###### Proposition 10.

If $`G`$ is of Hermitian type, then either

$$C(\gamma )=\mathrm{\Omega }_{AG}=\times \overline{}$$

or the base dual cycle $`\text{c}\mathrm{}(\kappa )`$ is $`P`$-invariant and $`C(\gamma )`$ is either $``$ or $`\overline{}`$, depending on the choice of sign.

###### Proof.

In the Hermitian case it is known that $`\mathrm{\Omega }_{AG}`$ agrees with $`\times \overline{}`$ in its natural embedding in $`G^{}/K^{}`$ (\[BHH\]).

Let $`\pi :G^{}/K^{}G^{}/P=:X`$, where $`P`$ is one of the two choices mentioned above, and let $`B`$ be an Iwasawa-Borel subgroup of $`G^{}`$ which is being used for the incidence geometry. If the $`B`$-invariant hypersurface $`H`$ in $`G^{}/K^{}`$ of $`\mathrm{\S }\text{3.2}`$ is not a lift $`H=\pi ^1(H_0)`$, then $`\mathrm{\Omega }_H`$ is Kobayashi hyperbolic and therefore $`\mathrm{\Omega }_H=\mathrm{\Omega }_{AG}`$ (\[FH\]). Thus, just as in the non-Hermitian case, the desired result follows from Prop. 8.

In order to complete the proof, we assume that $`H`$ is a lift, but that $`\text{c}\mathrm{}(\kappa )`$ is not $`P`$-invariant, and reach a contradiction.

Let $`x_0\gamma `$ be a base point with $`\kappa =K^{}.x_0`$. Since $`\kappa `$ is not $`P`$-invariant, $`\text{c}\mathrm{}(P.x_0)`$ contains $`\text{c}\mathrm{}(\kappa )`$ as a proper algebraic subvariety. Now the intersection $`\kappa \gamma `$ is transversal in $`Z`$. Thus every component of $`P.x_0𝒪`$ is positive-dimensional. Since $`𝒪=^{m(𝒪)}`$ is affine, every such component has at least one point of $`Y`$ in its closure.

Thus for $`B`$ an arbitrarily small neighborhood of the identity in $`G^{}`$ there exists $`pP`$ and $`gB`$ with $`gp.x_0Y`$, and consequently $`gpK^{}\mathrm{\Omega }_H`$.

But $`H`$ was assumed to be a lift. This is equivalent to $`\mathrm{\Omega }_H`$ being a lift, i.e., at the group level $`\mathrm{\Omega }_H`$ is invariant under the action of $`P`$ defined by right-multiplication. Hence $`gK^{}`$ is also in $`\mathrm{\Omega }_H`$. However, $`g`$ can be chosen arbitrarily near the identity, contrary to $`C(\gamma )`$ being an open neighborhood of the neutral point in $`G^{}/K^{}`$. ∎

Acknowledgement. We would like to thank the referee for his constructive remarks; in particular, for underlining the fact that the set of $`gG^{}`$ with $`g(\kappa )\gamma `$ non-empty and compact could theoretically be rather bad, e.g., not open. $`\mathrm{}`$

| AH and BN: |
| --- |
| Fakultät für Mathematik |
| Ruhr–Universität Bochum |
| D-44780 Bochum, Germany |
| ahuck@cplx.ruhr-uni-bochum.de |
| ntatin@cplx.ruhr-uni-bochum.de |


text:
# Finite subgraphs of uncountably chromatic graphs

## 1 Introduction

In  Erdős and Hajnal determined those finite graphs which appear as subgraphs in every uncountably chromatic graph: the bipartite graphs. In fact, not just that any odd circuit can be omitted, for every natural number $`n1`$ and infinite cardinal $`\kappa `$ there is a graph with cardinality and chromatic number $`\kappa `$ such that it omits all odd circuits up to length $`2n+1`$. They observed that the so-called $`r`$-shift graph construction has all but one of these properties; the vertex set of $`\mathrm{Sh}_r(\kappa )`$ is the set of all $`r`$-tuples from $`\kappa `$, with $`\{x_0,x_1,\mathrm{},x_{r1}\}_<`$ joined to $`\{x_1,x_2,\mathrm{},x_r\}_<`$, then this graph omits odd circuits of length $`3,5,\mathrm{},2r+1`$ and the Erdős-Rado theorem asserts that the chromatic number of $`\mathrm{Sh}_r(\mathrm{exp}_{r1}(\kappa )^+)`$ is at least $`\kappa ^+`$.

The problem of determining the classes of finite graphs that occur in uncountably chromatic graphs seems to be much harder, and its investigation was strongly pushed by Erdős and Hajnal.

An early conjecture for example was the following. Every uncountably chromatic graph contains all odd circuits from some length onward. This was then proved by Erdős, Hajnal, and Shelah , and independently, by Thomassen .

In  and later in  the following problem was posed (the Taylor conjecture). If $`\kappa `$, $`\lambda `$ are uncountable cardinals and $`X`$ is a $`\kappa `$-chromatic graph, is there a $`\lambda `$-chromatic graph $`Y`$ such that every finite subgraph of $`Y`$ appears as a subgraph of $`X`$. Notice that the above shift graphs give some evidence for this conjecture—the finite subgraphs of $`\mathrm{Sh}_r(\kappa )`$ do not depend on the parameter $`\kappa `$. The authors of  remarked that even the following much stronger conjecture seemed possible. If $`X`$ is uncountably chromatic, then for some $`r`$ it contains all finite subgraphs of $`\mathrm{Sh}_r(\omega )`$. This conjecture was then disproved in .

One easy remark, the so called Hanf number argument gives that there is a cardinal $`\kappa `$ with the property that if the chromatic number of some graph $`X`$ is at least $`\kappa `$ then there are arbitrarily large chromatic graphs with all finite subgraphs appearing in $`X`$. This argument, however, does not give any reasonable bound on $`\kappa `$.

Another conjecture of Erdős and Hajnal if the maximal chromatic number of $`n`$-element subgraphs of an uncountably chromatic graph as a function of $`n`$ can converge to infinity arbitarily slowly as $`n`$ tends to infinity. It was mentioned in several problem papers, for example in , , , , . See also , . The relevance of the above examples is that the chromatic number of the $`n`$-vertex subgraphs of (any) $`\mathrm{Sh}_r(\kappa )`$ grows roughly as the $`r1`$ times iterated logarithm of $`n`$. Perhaps it was this fact that led Erdős and Hajnal to the above problem.

Erdős also tirelessly popularized the Taylor conjecture, he mentioned it e.g., in , , , , , . It is also mentioned in , the book collecting Erdős’ conjectures on graphs. In  we gave some results when the additional hypotheses $`|X|=\kappa `$, $`|Y|=\lambda `$ was imposed. We described countably many different classes $`𝒦_{n,e}`$ of finite graphs and proved that if $`\lambda ^\mathrm{}_0=\lambda `$ then every $`\lambda ^+`$-chromatic graph of cardinal $`\lambda ^+`$ contains, for some $`n`$, $`e`$, all elements of $`𝒦_{n,e}`$ as subgraphs. On the other hand, it is consistent for every regular infinite cardinal $`\kappa `$ that there is a $`\kappa ^+`$-chromatic graph on $`\kappa ^+`$ that contains finite subgraphs only from $`𝒦_{n,e}`$. We got, therefore, some models of set theory, where the finite subraphs of graphs with $`|X|=\mathrm{Chr}(X)=\kappa ^+`$ for regular uncountable cardinals $`\kappa `$ were completely described.

Notice that the class of regular cardinals on which the above result operated excludes $`\omega _1`$, and in this paper we show the reason, by resolving the above Erdős-Hajnal conjecture: it is consistent that for every monotonically increasing function $`f:\omega \omega `$ there is a graph with size and chromatic number $`\mathrm{}_1`$ in which every $`n`$-chromatic subgraph has at least $`f(n)`$ elements ($`n3`$). The possibility of transforming the proof into a ZFC argument will be checked in the forthcoming , Chapter 9. An application of the method presented here gives the consistent existence of a graph $`X`$ with $`\mathrm{Chr}(X)=|X|=\mathrm{}_1`$ such that if $`Y`$ is a graph (of any size) all whose subgraphs are subgraphs of $`X`$ then $`\mathrm{Chr}(Y)\mathrm{}_2`$. This gives a consistent negative answer to the Taylor conjecture. As for the positive direction we prove that it is consistent that if $`X`$ is a graph with chromatic number at least $`\mathrm{}_2`$ then there are arbitrarily large chromatic graphs all whose finite subgraphs being induced subgraphs of $`X`$.

Theorems 1 and 2 were proved by S. Shelah and then P. Komjáth proved Theorems 3 and 4.

Notation. We use the standard axiomatic set theory notation. If $`A`$ is a set of ordinals, $`\beta `$ is an ordinal, then $`\beta <A`$, means that $`\beta <\alpha `$ holds for every $`\alpha A`$. Similarly for $`\beta A`$, $`A<\beta `$, etc. If $`f`$ is a function, $`A`$ a set, then we let $`f[A]=\{f(x):xA\}`$. If $`S`$ is a set, $`\kappa `$ is a cardinal, $`[S]^\kappa =\{XS:|X|=\kappa \}`$, $`[S]^{<\kappa }=\{XS:|X|<\kappa \}`$. A graph is an ordered pair $`(V,X)`$ where $`V`$ is some set (the set of vertices) and $`X[V]^2`$ (the set of edges). In some cases we identify the graph and $`X`$. The chromatic number of a graph $`(V,X)`$ is the least cardinal $`\mu `$ such that there exists a function $`f:V\mu `$ with $`f(x)f(y)`$ for $`\{x,y\}X`$ (a good coloring). A path of length $`n`$ is a sequence $`\{v_0,\mathrm{},v_n\}`$ of distinct vertices such that $`\{v_i,v_{i+1}\}X`$ holds for $`i<n`$. A cycle of length $`n`$ is a sequence $`\{v_1,\mathrm{},v_n\}`$ of vertices such that for $`1i<n`$ we have $`\{v_i,v_{i+1}\}X`$ and $`\{v_n,v_1\}X`$ also holds. If the vertices are distinct then we call it a circuit.

## 2 A large chromatic graph with small chromatic finite subgraphs

Let $`f:\omega \omega `$ be a strictly increasing function. Fix a sequence $`\{C_\alpha :\alpha <\omega _1,\text{limit}\}`$ such that $`C_\alpha `$ is an $`\omega `$-sequence converging to $`\alpha `$, and the whole sequence is a club guessing sequence, that is, if $`C\omega _1`$ is a closed unbounded set, then $`C_\alpha C`$ holds for some $`\alpha `$. Notice that the existence of a guessing sequence is an easy consequence of the diamond principle.

We are going to define the notion of forcing $`(Q^f,)`$. Every condition $`pQ^f`$ will be of the form $`p=(s,u,g,m,h_i,c)`$ where $`s[\omega _1]^{<\omega }`$, $`us`$, consisting of limit ordinals, $`g`$ is a graph on $`u`$, for every $`\alpha u`$ we have an $`m(\alpha )<\omega `$, and then the ordinals $`h_0(\alpha )<\mathrm{}<h_{m(\alpha )1}(\alpha )<\alpha `$ which are $`C_\alpha `$-separated, that is, $`\mathrm{min}(C_\alpha )<h_0(\alpha )`$ and between $`h_i(\alpha )`$ and $`h_{i+1}(\alpha )`$ there is an element of $`C_\alpha `$ ($`h_i(\alpha )`$ is undefined if $`im(\alpha )`$ or $`\alpha u`$). $`c:g\omega `$ satisfies that if $`\{x,\alpha \}g`$, $`\{y,\alpha \}g`$ and $`x,y<\alpha `$ then $`c(x,\alpha )c(y,\alpha )`$.

Given $`pQ^f`$ we define

$$Y_r^p=\{eg:c(e)r\}$$

for any natural number $`r`$.

We add the following stipulations.

1. If $`\alpha u`$ is incident to some $`eg`$ with $`c(e)r`$ then $`m(\alpha )r`$.
2. If $`x`$, $`y`$ are connected in $`Y_r^p`$ in $`i`$ steps then $`h_{ji}(x)<h_j(y)<h_{j+i}(x)`$ holds for $`ijf(r)i`$.
3. $`Y_r^p`$ does not contain odd circuits of length $`f(r)`$.

We notice that although a condition $`p=(s,u,g,m,h_i,c)`$ is infinite (perhaps $`p=(s,u,g,m,(h_i)_{i<\omega },c)`$ or $`p=(s,u,g,m,h_i,c)_{i<\omega }`$ would be better notation) as all but finitely many of the partial functions $`\{h_i:i<\omega \}`$ are the empty function, every condition is really a finite object.

The partial order on $`Q^f`$ is defined the natural way. $`p^{}=(s^{},u^{},g^{},m^{},h_i^{},c^{})`$ extends $`p=(s,u,g,m,h_i,c)`$ iff the following hold. $`s^{}s`$, $`u=u^{}s`$, $`g=g^{}[s]^2`$. $`m^{}(\alpha )m(\alpha )`$ holds for $`\alpha u`$, and $`h_i^{}(\alpha )=h_i(\alpha )`$ for $`i<m(\alpha )`$. Finally, $`c^{}(x,\alpha )=c(x,\alpha )`$ holds for $`\{x,\alpha \}g`$.

We call two conditions $`p=(s,u,g,m,h_i,c)`$ and $`p^{}=(s^{},u^{},g^{},m^{},h_i^{},c^{})`$ isomorphic iff $`|s|=|s^{}|`$ and the unique order preserving mapping $`\pi :ss^{}`$ satisfies $`u^{}=\pi [u]`$, $`g^{}=\pi [g]`$, $`m(\alpha )=m^{}(\pi (\alpha ))`$ for $`\alpha u`$, $`h_i^{}(\pi (\alpha ))=h_i(\alpha )`$ and $`c^{}(\pi (x),\pi (\alpha ))=c(x,\alpha )`$ hold whenever the right hand sides are defined. Notice that, as our conditions are finite structures, we have only countably many isomorphism types.

From a generic $`GQ^f`$ we define the following graphs on $`\omega _1`$:

$$X=\{g:(s,u,g,m,h_i,c)G\},$$

$$X_n=\{\{x,y\}:\{x,y\}g,c(x,y)=n,(s,u,g,m,h_i,c)G\},$$

$$Y_r=X_rX_{r+1}\mathrm{}$$

and notice that $`Y_r=\{Y_r^p:pG\}`$.

Lemma 1. For $`\alpha <\omega _1`$ the set $`\{(s,u,g,m,h_i,c)Q^f:\alpha s\}`$ is dense.

Proof. Straightforward.

Lemma 2. If $`\alpha <\omega _1`$ is limit, $`(s,u,g,m,h_i,c)Q^f`$, $`\alpha s`$, then there is an extension $`(s^{},u^{},g^{},m^{},h_i^{},c^{})(s,u,g,m,h_i,c)`$ with $`\alpha u^{}`$.

Proof. Straightforward.

Lemma 3. If $`(s,u,g,m,h_i,c)Q^f`$, $`\alpha u`$, $`n<\omega `$ then there is an extension $`(s^{},u^{},g^{},m^{},h_i^{},c^{})(s,u,g,m,h_i,c)`$ with $`m(\alpha )n`$.

Proof. It suffices to show that $`m(\alpha )`$ can be incremented by one. Given $`h_{m(\alpha )1}(\alpha )<\alpha `$ if we choose $`h_{m(\alpha )}^{}(\alpha )<\alpha `$ large enough the condition on $`C_\alpha `$ will surely be satisfied.

Lemma 4. $`(Q^f,)`$ is ccc.

Proof. Modulo standard arguments we have to show that $`p=(s,u,g,m,h_i,c)`$ and $`p^{}=(s^{},u^{},g^{},m^{},h_i^{},c^{})`$ are compatible, assuming that they are isomorphic, and $`ss^{}`$ is an initial segment of both $`s`$ and $`s^{}`$. Let $`\pi :ss^{}`$ be the order preserving structure isomorphism. We let $`p^{\prime \prime }=(s^{\prime \prime },u^{\prime \prime },g^{\prime \prime },m^{\prime \prime },h_i^{\prime \prime },c^{\prime \prime })`$ where we take unions in all coordinates.

In order to show that $`p^{\prime \prime }`$ is a condition we have to check properties (1.–3.).

(1.) is obvious.

For (3.) assume that $`C`$ is an odd circuit of length $`f(r)`$ in $`Y_r^{p^{\prime \prime }}`$. If we replace every $`eC`$ that contains at least one vertex from $`ss^{}`$ with $`\pi (e)`$ then we get an odd cycle $`C^{}`$ in $`Y_r^p^{}`$. $`C^{}`$ splits into circuits, at least one of them odd, so we get a contradiction.

For (2.) notice that it holds if $`x`$, $`y`$ are joined via a path going entirely in $`Y_r^p`$ or $`Y_r^p^{}`$. It suffices, therefore, to show that if some path $`P`$ between $`x`$ and $`y`$ of length $`i`$ is split by an inner point $`z`$ into the paths $`P_0`$ and $`P_1`$ between $`x`$ and $`z`$, and $`z`$ and $`y`$, respectively, and of the respective lengths $`i_0`$ and $`i_1`$ (so $`i_0+i_1=i`$) and the statement holds for $`P_0`$ and $`P_1`$ then it holds for $`P`$, as well. Indeed, for $`ijf(r)i`$ we have

$$h_{j(i_0+i_1)}(x)<h_{ji_1}(z)<h_j(y)<h_{j+i_1}(z)<h_{j+(i_0+i_1)}(x).$$

Lemma 5. $`\mathrm{Chr}(X)=\omega _1`$.

Proof. Assume that some $`\overline{p}`$ forces that $`\underset{¯}{F}`$ is a good coloring of $`X`$ with the elements of $`\omega `$. Select an increasing, continuous sequence of countable elementary submodels $`\overline{p},\underset{¯}{F},Q^f,\parallel –N_0N_1\mathrm{}N_\alpha H(\lambda )`$ with some large enough regular cardinal $`\lambda `$, for $`\alpha <\omega _1`$, such that $`\gamma _\alpha =N_\alpha \omega _1`$ is an ordinal. The set $`C=\{\gamma _\alpha :\alpha <\omega _1\}`$ will be a closed, unbounded set, so by the guessing property there is some $`\delta =\gamma _\alpha `$ such that $`C_\delta C`$. Notice that all points of $`\overline{p}`$ are smaller than $`\delta `$.

Extend $`\overline{p}`$ to a $`p^{}`$ using Lemma 2., adding $`\delta `$ to the $`u`$-part, then let $`p^{}`$ be a condition extending $`p^{}`$ such that $`p^{}\parallel –\underset{¯}{F}(\delta )=i`$ holds for some $`i<\omega `$.

Let $`n`$ be some natural number that $`n\{c^{}(x,\delta ):\{x,\delta \}g^{},x<\delta \}`$ where $`p^{}=(s^{},u^{},g^{},m^{},h_i^{},c^{})`$. Extend $`p^{}`$ using Lemma 3., to some condition $`p`$ with $`p=(s,u,g,m,h_i,c)`$ such that $`m=m(\delta )f(n)`$ holds.

In $`p`$ we have the values

$$h_0(\delta )<h_1(\delta )<\mathrm{}<h_{m1}(\delta )<\delta $$

and by our requirements on conditions there are elements $`\delta _0,\mathrm{},\delta _{m1}`$ of $`C_\delta `$ such that

$$\delta _0<h_0(\delta )<\delta _1<h_1(\delta )<\mathrm{}<\delta _{m1}<h_{m1}(\delta )<\delta $$

holds.

The values $`\delta _0,\mathrm{},\delta _{m1},\delta `$ break $`s`$ into disjoint parts: $`s=s_0\mathrm{}s_ms_{m+1}`$ with

$$s_0<\delta _0s_1<\delta _1s_2<\mathrm{}<\delta _{m1}s_m<\delta s_{m+1}$$

(some of them may be empty).

Sublemma. There is a condition $`p^{}`$ on some $`s^{}=s_0s_1^{}\mathrm{}s_m^{}s_{m+1}^{}`$ isomorphic to $`p`$ with $`|s_i^{}|=|s_i|`$, $`\delta ^{}=\mathrm{min}(s_{m+1}^{})`$, $`p^{}\parallel –\underset{¯}{F}(\delta ^{})=i`$ and

$$s_0<s_1^{}<\delta _0s_1<s_2^{}<\delta _1s_2<\mathrm{}<s_m^{}<\delta _{m1}s_m<s_{m+1}^{}<\delta s_{m+1}$$

holds.

Proof. Let $`\theta `$ be the isomorphism type of $`p`$. For the ordered finite sets $`\overline{x}_0,\overline{x}_1,\mathrm{},\overline{x}_{m+1}`$ let $`\psi (\overline{x}_0,\overline{x}_1,\mathrm{},\overline{x}_{m+1})`$ denote the statement that $`\overline{x}_0<\overline{x}_1<\mathrm{}<\overline{x}_{m+1}`$, $`|\overline{x}_i|=|s_i|`$ and for the (unique) condition $`p`$ on $`\overline{x}_0\overline{x}_1\mathrm{}\overline{x}_{m+1}`$ of type $`\theta `$ $`p\parallel –\underset{¯}{F}(\delta )=i`$ where $`\delta =\mathrm{min}(\overline{x}_{m+1})`$.

Set

$$\phi _{m+1}(\overline{x}_0,\overline{x}_1,\mathrm{},\overline{x}_{m+1})=\psi (\overline{x}_0,\overline{x}_1,\mathrm{},\overline{x}_{m+1})$$

and for $`0im`$

$$\phi _i(\overline{x}_0,\overline{x}_1,\mathrm{},\overline{x}_i)=^{}\overline{x}_{i+1}\phi _{i+1}(\overline{x}_0,\overline{x}_1,\mathrm{},\overline{x}_{i+1})$$

where the quantifier $`^{}`$ denotes “there exist unboundedly many” which is expressible in the first order language of $`(\omega _1,<)`$.

Claim. For $`0im+1`$ the sentence $`\phi _i(s_0,s_1,\mathrm{},s_i)`$ holds.

Proof. We prove the statement by reverse induction on $`0im+1`$. We certainly have $`\phi _{m+1}(s_0,s_1,\mathrm{},s_{m+1})`$. If for some $`0im`$ we had that $`\phi _{i+1}(s_0,s_1,\mathrm{},s_{i+1})`$ holds yet

$$\phi _i(s_0,s_1,\mathrm{},s_i)=^{}\overline{x}_{i+1}\phi _{i+1}(s_0,s_1,\mathrm{},s_i,\overline{x}_{i+1})$$

fails, then there was a bound, computable from $`s_0,s_1,\mathrm{},s_i`$ for the minima of those sets $`\overline{x}_{i+1}`$ for which $`\phi _{i+1}(s_0,s_1,\mathrm{},s_i,\overline{x}_{i+1})`$ holds. Then this bound was smaller than $`\delta _i`$ ($`\delta `$ for $`i=m`$) as there is an elementary submodel containing the ordinals $`<\delta _i`$ (or $`<\delta `$) but this contradicts the fact that $`\phi _{i+1}(s_0,s_1,\mathrm{},s_{i+1})`$ holds and $`\delta _is_i`$.

Using the Claim we can inductively select the sets $`s_1^{},\mathrm{},s_{m+1}^{}`$ such that for every $`1im+1`$ we have $`\phi _i(s_0,s_1^{},\mathrm{},s_i^{})`$ and $`s_i<s_{i+1}^{}\delta _i`$, as required.

Using the Sublemma we create the following one-edge amalgamation $`p^{\prime \prime }`$ of $`p`$ and $`p^{}`$. $`p^{\prime \prime }=(s^{\prime \prime },u^{\prime \prime },g^{\prime \prime },m^{\prime \prime },h_i^{\prime \prime },c^{\prime \prime })`$ where $`s^{\prime \prime }=ss^{}`$, $`u^{\prime \prime }=uu^{}`$, $`g^{\prime \prime }=gg^{}\left\{\{\delta ,\delta ^{}\}\right\}`$, $`m^{\prime \prime }=mm^{}`$, $`h_i^{\prime \prime }=h_ih_i^{}`$, $`c^{\prime \prime }=cc^{}`$.

We have to show that $`p^{\prime \prime }`$ is indeed a condition, that is, we have to check if the properties (1.-3.) hold.

(1.) is obvious.

For (2.) we argue as in the proof of Lemma 4; every path in question is the union of paths for which this condition holds, plus possibly the path $`\{\delta ,\delta ^{}\}`$ but (2.) also holds for this.

Assume finally, that $`C`$ is a circuit of length $`2t+1f(r)`$ in $`Y_r^{p^{\prime \prime }}`$. Unless $`C`$ contains $`\{\delta ,\delta ^{}\}`$, we can argue as in Lemma 4. So we are left with the case that $`C`$ contains $`\{\delta ,\delta ^{}\}`$ and $`rn`$. That is, $`\delta s`$ and $`\delta ^{}s^{}`$ are joined in $`Y_r^pY_r^p^{}`$ in $`2t`$ steps, and this is only possible if the connecting path has vertices in $`ss^{}`$. So we get that $`\delta `$ can be connected in $`Y_r^p`$ with some point in $`ss^{}`$ in $`t`$ steps. But this is impossible: if $`xss^{}`$ is such a point then $`h_0(\delta )<h_t(x)<h_{2t}(\delta )`$ by condition (2.) and also $`x<h_0(\delta )`$, a contradiction.

As $`p^{\prime \prime }`$ forces that $`F(\delta )=F(\delta ^{})=i`$ yet they are joined in $`X`$, we are finished.

Theorem 1. The forcing $`Q^f`$ adds an uncountably chromatic graph $`X`$ on $`\omega _1`$ such that every subgraph on at most $`f(r)`$ vertices is at most $`2^{r+1}`$-chromatic.

Proof. As every $`X_n`$ is a circuitfree graph, it can be colored with two colors. Consider now a subgraph of $`X`$ induced by a set $`S`$ of at most $`f(r)`$ vertices. On $`S`$ all the graphs $`X_0,\mathrm{},X_{r1}`$ are bipartite, and so is $`Y_r=X_r\mathrm{}`$ (as it has no odd circuits of length $`f(r)`$). So their union, $`X`$ restricted to $`S`$, can be colored by at most $`2^{r+1}`$ colors.

Theorem 2. It is consistent with CH that for every function $`f:\omega \omega `$ there is an uncountably chromatic graph $`X`$ on $`\omega _1`$ such that every sugraph of $`X`$ on $`f(r)`$ vertices is at most $`r`$-chromatic ($`r2`$).

Proof. Assume that $`\mathrm{}`$ holds in the ground model. Then we have CH and there is a club guessing sequence $`\{C_\alpha :\alpha <\omega _1,\text{limit}\}`$ as required for Theorem 1. We force with a finite support iteration $`P=\{P_\alpha ,Q_\alpha :\alpha <\omega _1\}`$. In step $`\alpha <\omega _1`$ we add $`Q_\alpha =Q^{f_\alpha }`$ for some increasing function $`f_\alpha :\omega \omega `$. As this will be a ccc forcing that preserves CH it is possible by bookkeeping to make sure that every suitable $`f:\omega \omega `$ occurs as some $`f_\alpha `$. Also, as $`P_\alpha `$, the iteration up to $`\alpha `$ is ccc, every closed, unbounded set $`C`$ in $`V^{P_\alpha }`$ contains a ground model closed, unbounded set $`D`$, and as there is some element $`C_\alpha `$ of the club guessing system that $`C_\alpha D`$ we have $`C_\alpha C`$, that is the club guessing system retains its property in $`V^{P_\alpha }`$.

Call a condition $`pP`$ determined if for every $`\alpha <\omega _1`$ the condition $`p|\alpha `$ completely determines $`p(\alpha )`$, that is, for every $`\alpha `$ coordinate $`p(\alpha )`$ is not just a name for a finite structure but it is actually a finite structure.

Lemma 6. The determined conditions form a dense set in $`P`$.

Proof. We prove by induction on $`\alpha <\omega _1`$ that the determined conditions form a dense subset of $`P_\alpha `$. This is obvious if $`\alpha `$ is limit, as we are considering finite supports. Assume that we have the statement for some $`\alpha <\omega _1`$ and we try to handle the case of $`\alpha +1`$. Let $`(p,q)P_{\alpha +1}=P_\alpha Q_\alpha `$ be arbitrary. Extend $`p`$ to some $`p^{}`$ that completely determines $`q`$, that is, there is a finite structure $`h`$ that $`p^{}\parallel –q=h`$. Then extend $`p^{}`$ to a determined $`p^{}P_\alpha `$. Now $`(p^{},h)`$ is a determined extension of $`(p,q)`$.

Lemma 7. For every $`\alpha <\omega _1`$, $`\mathrm{Chr}(X_\alpha )=\omega _1`$ holds in $`V^P`$.

Proof. By moving to $`V^{P_\alpha }`$ we can assume that $`\alpha =0`$. We imitate the proof of Lemma 5. By Lemma 6 we can work with determined conditions. We consider every such condition as a finite structure on some finite subset $`s`$ of $`\omega _1`$, here $`s`$ contains all points of all graphs $`p(\beta )`$ where $`\beta `$ is an arbitrary element of the support of $`p`$, and we also add the elements of the support to $`s`$. Assume that some $`\overline{p}P`$ forces that $`\underset{¯}{F}`$ is a good coloring of $`X_0`$ with the elements of $`\omega `$. With an argument like in Lemma 5 we get some natural number $`n`$, ordinals $`\delta ^{}<\delta <\omega _1`$, and also $`\alpha _1,\mathrm{},\alpha _m,\beta _1,\mathrm{},\beta _t,\beta _1^{},\mathrm{},\beta _t^{}`$ and two isomorphic determined conditions $`p`$ and $`p^{}`$ with the respective supports $`\{0,\alpha _1,\mathrm{},\alpha _m,\beta _1,\mathrm{},\beta _t\}`$ and $`\{0,\alpha _1,\mathrm{},\alpha _m,\beta _1^{},\mathrm{},\beta _t^{}\}`$ that $`p\parallel –\underset{¯}{F}(\delta )=n`$, $`p^{}\parallel –\underset{¯}{F}(\delta ^{})=n`$ hold, $`p(0)`$ and $`p^{}(0)`$ are isomorphic conditions that behave like $`p`$ and $`p^{}`$ in Lemma 5, for every $`\alpha _i`$ the structures $`p(\alpha _i)`$ and $`p^{}(\alpha _i)`$ are isomorphic with the common part preceding the tails, that is, it is possible to make a non-edge amalgamation. We can, therefore, take the union of $`p`$ and $`p^{}`$, and add the edge $`\{\delta ,\delta ^{}\}`$ with color $`n`$ in coordinate 0.

The above Lemma concludes the proof of the Theorem.

## 3 The Taylor conjecture

Theorem 3. It is consistent that there is a graph $`X`$ with $`\mathrm{Chr}(X)=|X|=\mathrm{}_1`$ such that if $`Y`$ is a graph with all finite subgraphs occurring in $`X`$ then $`\mathrm{Chr}(Y)\mathrm{}_2`$, that is, the Taylor conjecture fails.

Proof. Let $`V`$ be a model of GCH and $`\mathrm{}`$. Let $`P`$ be the notion of forcing that adds a Cohen real. It is well known that $`P`$ adds an undominated real, that is, a function $`f:\omega \omega `$ such that for no $`g:\omega \omega `$ in $`V`$ does $`f(n)g(n)`$ hold for every $`n<\omega `$. Let $`V^{}`$ be the forced model. Notice that $`V^{}`$ still has GCH and club guessing (by the argument in the proof of Theorem 2.). Now force over $`V^{}`$ with the partial order $`Q^f`$, and get a graph $`X`$ with $`\mathrm{Chr}(X)=|X|=\mathrm{}_1`$ such that every $`n`$-chromatic subgraph of $`X`$ has at least $`f(n)`$ elements ($`n3`$). This $`X`$ will be our graph. To show the property stated, assume that $`Y`$ is a graph in $`V^{P,Q^f}`$ whose every finite subgraph is a subgraph of $`X`$. We assume that the vertex set of $`Y`$ is some cardinal $`\lambda `$. We notice that every $`n`$-chromatic subgraph of $`Y`$ has at least $`f(n)`$ elements.

Lemma 8. If $`ZY`$ is a subgraph with $`ZV`$ then $`Z`$ is finitely chromatic.

Proof. Otherwise for every $`n<\omega `$ we can let $`g(n)`$ be the minimal size of an $`n`$-chromatic subgraph of $`Z`$. Now notice that $`gV`$ and also by the absoluteness of the set of finite subsets of $`\lambda `$ and the absoluteness of the cromatic number of a finite graph, $`g`$ denotes the same thing in $`V`$ and $`V^{PQ^f}`$. This implies that $`g(n)f(n)`$ holds for every $`n`$, but that obviously contradicts the fact that $`f`$ cannot be dominated by the the ground model $`\omega \omega `$ functions.

We finally need the following Lemma.

Lemma 9. If $`R`$ is a notion of forcing over some model $`V`$, $`Y`$ is a graph in the extended model on some ordinal $`\lambda `$ then $`Y`$ is the union of at most $`|R|`$ subgraphs which are elements of $`V`$.

Proof. Let $`\tau `$ be a name for (the edge set of) $`Y`$. Set

$$Z_p=\{e[\lambda ]^2:p\parallel –e\tau \}$$

for $`pR`$, then $`Y=\{Z_p:pG\}`$ where $`GR`$ is a generic set.

To finish the proof of the Theorem we remark that by Lemma 9 $`Y`$ decomposes into the union of $`|PQ^f|=\mathrm{}_1`$ graphs each being in $`V`$, therefore finitely chromatic, so we get $`\mathrm{Chr}(Y)2^\mathrm{}_1=\mathrm{}_2`$.

The followig argument gives that the Hanf number mentioned in the Introduction can be as small as $`\mathrm{}_2`$.

Theorem 4. It is consistent that if $`X`$ is a graph with $`\mathrm{Chr}(X)\mathrm{}_2`$ then for every cardinal $`\lambda `$ there exists a graph $`Y`$ with $`\mathrm{Chr}(Y)\lambda `$ all whose finite subgraphs are induced subgraphs of $`X`$.

Proof. Let $`V`$ be a model of GCH. Choose the regular cardinal $`\kappa `$ so large that the following holds. If $`X`$ is a graph with $`\mathrm{Chr}(X)\kappa `$ and $`\lambda `$ is a cardinal then there is a graph with $`\mathrm{Chr}(Y)\lambda `$ all whose finite subgraphs occur as subgraphs of $`X`$. Clearly, such a $`\kappa `$ exists.

Let $`P=\mathrm{Col}(\omega ,\kappa )`$ be the collapse of $`\kappa `$ to $`\mathrm{}_0`$, that is, the elements of $`P`$ are those functions of the form $`p:n\kappa `$ for some $`n<\omega `$ with $`pq`$ iff $`p`$ extends $`q`$ as a function. Our claim is that if $`GP`$ is generic then $`V[G]`$ models the statement of the Theorem. Notice that $`|\kappa |=\mathrm{}_0`$ holds there and calculation shows that GCH still holds in $`V[G]`$.

Assume that $`X`$ is a graph in $`V[G]`$ with chromatic number at least $`\mathrm{}_2`$ (that is, $`\mathrm{}_2^{V[G]}`$). By Lemma 9., $`X`$ is the union of $`|G|=\mathrm{}_0`$ ground model graphs. As $`\mathrm{}_1^\mathrm{}_0=\mathrm{}_1`$, one of them, say $`Y`$ must have chromatic number at least $`\mathrm{}_2`$. In $`V`$, $`Y`$ has chromatic number at least $`\mathrm{}_2^{V[G]}=\kappa ^{++}`$. Assume that we are given some $`\lambda >\kappa `$. By the choice of $`\kappa `$, there is a graph $`Z`$ with $`\mathrm{Chr}(Z)\lambda `$ such that every finite induced subgraph of $`Z`$ is an induced subgraph of $`Y`$.

Lemma 10. $`\mathrm{Chr}(Z)\lambda `$ holds in $`V[G]`$.

Proof. Otherwise let $`\underset{¯}{F}`$ be a name for a coloring with the ordinals less than $`\tau <\lambda `$. Then the coloring $`x(p,\xi )`$ is a good coloring of the vertices of $`Z`$ with $`\kappa +\tau <\lambda `$ colors, where $`pP`$ is some element of $`P`$ with $`p\parallel –\underset{¯}{F}(x)=\xi `$.

We are almost finished, the only problem is that the finite induced subgraphs of $`Z`$ are not induced subgraphs of $`X`$, they only are (edge-)subgraphs of induced subgraphs of $`X`$. The following Lemma is what we need.

Lemma 11. There is a graph $`Z^{}`$ on the vertex set of $`Z`$ with $`Z^{}Z`$ and such that every induced subgraph of $`Z^{}`$ is an induced subgraph of $`X`$.

Proof. Let $`S`$ be the vertex set of $`Z`$. For every finite subset $`s`$ of $`S`$ there are some graphs on $`s`$, which on the one hand are isomorphic to induced subgraphs of $`X`$, on the other hand they are supergraphs of the graph $`Z`$ restricted to $`s`$. Call these graphs appropriate for $`s`$. Notice that there are finitely many appropriate graphs for every given $`s`$, and if $`T`$ is an appropriate graph for $`s`$ and $`s^{}`$ is a subset of $`s`$ then $`T`$ restricted to $`s^{}`$ is a graph appropriate for $`s^{}`$. We can therefore apply the Rado selection principle (or the compactness theorem of model theory) and get a graph $`Z^{}`$ on $`S`$ every induced subgraph of which is appropriate, so $`Z^{}`$ is a required.

As $`\mathrm{Chr}(Z^{})\mathrm{Chr}(Z)\lambda `$ holds we are done.

Péter Komjáth Department of Computer Science Eötvös University Budapest, P.O.Box 120 1518, Hungary e-mail: kope@cs.elte.hu   Saharon Shelah Institute of Mathematics, Hebrew University, Givat Ram, 91904, Jerusalem, Israel e-mail: shelah@math.huji.ac.il