Intelligent Computational Methods for Financial Engineering

(1)

GRAPHS WITH SMALL CYCLES

VICTOR NEUMANN-LARA AND RICHARD G. WILSON Received 11 November 2004 and in revised form 12 July 2005

A topologyτon the vertices of a comparability graphGis said to becompatible with G if each subgraphH ofGis graph-connected if and only if it is a connected subspace of (G,τ). In two previous papers we considered the problem of finding compatible topologies for a given comparability graph and we proved that the nonexistence of infinite paths was a necessary and suﬃcient condition for the existence of a compact compatible topology on a tree (that is to say, a connected graph without cycles) and we asked whether this condition characterized the existence of a compact compatible topology on a comparability graph in which all cycles are of length at mostn. Here we prove an extension of the above-mentioned theorem to graphs whose cycles are all of length at most five and we show that this is the best possible result by exhibiting a comparability graph in which all cycles are of length 6, with no infinite paths, but which has no compact compatible topology.

1. Introduction and preliminary results

Recall that a graph is acomparability graphif and only if it is the graph of some poset.

More formally if we define thegraphof a poset (X,<), denoted byᏳ((X,<)), on the vertex setX, by

[x,y]∈EᏳ(X,<) if and only if eitherx < yory < x, (1.1) thenGis a comparability graph if it is isomorphic toᏳ((X,<)) for some poset (X,<).

Note thatᏳis a functor from the category of posets onto the category of comparability graphs with reflexive graph-homomorphisms as morphisms. Thus ifGis a comparability graph, then there is some (nonunique) poset (X,<) such thatᏳ(X,<)=G (thusX= V(G)) and soᏳinduces orderings on the vertices ofG(or equivalently, orientations of the edges ofG). In the sequel, a comparability graphGwith a (fixed) induced order<will be denoted by (G,<) (even though strictly speaking, the order is on the setV(G)) and we refer to such a graph as anordered comparability graph; clearly the category of posets and the category of ordered comparability graphs are isomorphic.

International Journal of Mathematics and Mathematical Sciences 2005:14 (2005) 2195–2205 DOI:10.1155/IJMMS.2005.2195

(2)

Pr´ea introduced the notion of compatibility between a graphGand a topology on its vertex setV(G) in [7]. There, a topologyτ on V(G) was said to becompatible(resp., weakly compatible) with a graphGif every induced subgraphH ofG(resp., every finite induced subgraphHofG) is connected if and only if the relative topology induced byτon V(H) is connected. It was shown that, in the case of a locally finite comparability graph Gwith a finite number of components, a compatible topology exists if and only ifGis a comparability graph. This result was generalized to arbitrary comparability graphs in [5].

Clearly, if a topologyτon the vertex setV(G) of a graphGis weakly compatible, then the graph structure ofGis determined by the topology in the sense that wheneverx,yare distinct vertices ofG, [x,y]∈E(G) (the edge set ofG) if and only ifx∈cl_τ{y}ory∈cl_τ{x}. We will be studying topologies on the vertex sets of ordered comparability graphs and in order to relate the topology to the partial order, we require that the specialization order of the topologyτ(which we denote byτ and is defined byxτ yif and only if x∈clτ{y}) exactly coincide with the given partial order. Such a topology will be said to beconsistentwith the poset or ordered comparability graph. Clearly a consistent topology must be weakly compatible in the sense of [5,7], but not vice versa. In what follows, in order to avoid unnecessary terminology, we assume that the conditions of weak compatibility and compatibility include the condition of consistency. Thus we make the following formal definitions.

A topologyτon the vertex set of an ordered comparability graph (G,<) is said to be compatible(resp.,weakly compatible) if for each induced subgraphH ofG(resp., each finite induced subgraphH ofG),H isτ-connected if and only if it is graph-connected andτcoincides with<.

Recall from [6] that a graphGis said to becyclically boundedif there is somek∈N(the set of positive integers) such that every cycle inGis of length at mostk. In [6, Theorem 3.1], we have shown that an (ordered) tree possesses a compact compatible topology if and only if it has no infinite paths and we asked whether a similar theorem holds in the case of cyclically bounded ordered comparability graphs.

If≤is a partial order on a setX, then we define (←,x]= {y:y≤x}and [x,→)= {y: y≥x}; theweak topologyωonXis the topology generated by the sets{X\(←,x] :x∈X} and the Alexandroﬀtopologyαinduced by the partial order is that topology with base {[x,→) :x∈X}. It was shown in [5, Theorem 1.10] that ifµis a compatible topology for a poset (X,<), thenω⊆µ⊆α.

Forw∈V(G),N(w) will denote the set of graph neighbours ofwand a graphG is said to bebluntif for eachv∈V(G),G\N(v) has only a finite number of components.

Finally, say that a set of verticesH of a graphGiscentredif there existsv∈Gsuch that H⊆N(v)\ {v}.vis then said to be acentreforH. Say thatH isfinitely centredif every finite subset ofHis centred.

For all other undefined topological and graph-theoretical terms we refer the reader to [1,2,3].

Theorem1.1. If an ordered bipartite graph(G,<)either (1)has no infinite paths, or

(2)is cyclically bounded, then the weak topology is compact.

(3)

Proof. We denote the set of minimal (resp., maximal) elements of the order by min(G) (resp., max(G)). Suppose to the contrary that the weak topology is not compact; then by [6, Theorem 2.12], there is some (necessarily infinite) subsetV⊆max(G) of maximal elements of (G,<) which is finitely centred but not centred. Choosev0∈Vandm0∈min(G) such thatm0< v0. Suppose now that we have chosen distinct verticesv0,v1,...,vn∈Vand m0,...,mn∈min(G) such that

(a)mkis a centre for{v0,v1,...,vk}for eachk∈ {0, 1,...,n}, and (b) [mk,vk+1]∈E(G) for eachk∈ {0, 1,...,n−1},

then clearly

T=m0,v0,m1,v1,...,mn,vn (1.2) is a path inGof length 2n+ 1 and

v0,m1,v1,...,vn−1,mn (1.3) is a cycle of length 2n. We extend this path to a path of length 2n+ 3 thus showing by induction that there is an infinite path inGand at the same time construct a cycle of length 2n+ 2, showing that (G,<) is not cyclically bounded.

Sincemnis not a centre forV, there is somevn+1∈V such thatmn≤vn+1and then necessarilyvn+1∈ {v0,v1,...,vn}by (a) above. However,V is finitely centred and hence there is somemn+1∈min(G) such thatmn+1< vkfor allk∈ {0, 1,...,n,n+ 1}; it follows from (b) thatmn+1∈ {m0,m1,...,mn}and hence we have extended the pathTto a path of length 2n+ 3,m0,v0,m1,v1,...,mn,vn,mn+1,vn+1. Note also, that since [mn+1,v0]∈E(G), we have also constructed a cycle

v0,m1,v1,...,vn−1,mn,vn,mn+1 (1.4)

of length 2n+ 2.

We recall the following definitions from [6].

A poset (or equivalently, an ordered comparability graph) (X,<) will be said to be basalif the set of minimal elements of the order, min(X), is coinitial. Let (X,<) be a basal poset; we define a new order≺onXas follows:

x≺y if and only ifx < yandx∈min(X). (1.5) The poset (X,≺) will be called thebipartite skeletonof (X,<). Similarly,Ᏻ(X,≺) will be called theordered bipartite skeletonofᏳ(X,<); it is easy to see thatᏳ(X,≺) is an (ordered) bipartite graph.

In [6, Section 2], we showed that the existence of a compact compatible (or weakly compatible) topology on such a graph is equivalent to the existence of such a topology on its bipartite skeleton [6, Theorems 2.14 and 2.18].

Corollary 1.2. If an ordered comparability graph has no infinite paths or is cyclically bounded, then it has a compact weakly compatible topology.

(4)

Proof. Suppose (G,<) is an ordered comparability graph which is either cyclically bounded or has no infinite paths; we claim thatGis basal. For if not, then there is some descending chainx0> x1> x2>··· of vertices which implies the existence both of an infinite path and arbitrarily large cycles inG. Thus (G,<) has a bipartite skeleton which we denote by (H,≺). SinceH is a subgraph ofG, it also is either cyclically bounded or has no infinite paths and hence by the theorem, the weak topology on (H,≺) is compact.

The result now follows from [6, Theorem 2.14].

Corollary1.3. The weak topology corresponding to either of the two possible orderings of a tree is compact.

Let us say that a bipartite graph is (weakly)bilaterally compactif for each of the two possible orderings there is at least one compact (weakly) compatible topology.

The following result is now clear.

Corollary1.4. A bipartite graph which either has no infinite paths or is cyclically bounded is weakly bilaterally compact.

Thus a bipartite graph which is not weakly bilaterally compact must have both an infinite path and arbitrarily large cycles—such a graph is given as [6, Example 2.19]. Notice that for this graph neither of the two weak topologies corresponding to the two possible orderings of the graph are compact. However, by modifying slightly the above-mentioned example, we obtain a bipartite graph which has a compact compatible topology with respect to one ordering, but which does not even have a weakly compatible compact topology with respect to the other.

Example 1.5. The graphGis defined by V(G)=(N× {0})∪

N∪ {∞}

× {1} , E(G)=

(m, 0), (n, 1):m,n∈N,m=n∪

(∞, 1), (n, 0):n∈N

. (1.6)

It is easy to see that with the ordering in which vertices whose second coordinate is 0 are minimal, the weak topology restricted to the set of minimal elements{(n, 0) :n∈N}

is discrete (exactly as in [6, Example 2.19]) and hence the weak topology is not compact. However, with the reverse order, the vertex (∞, 1) is a centre for the set of maximal elements{(n, 0) :n∈N}and hence by [6, Corollary 2.10], for this ordering there is a compatible compact topology onG.

2. Graphs whose cycles are small

We have shown in [6, Theorem 3.4] that if (G,<) is a cyclically bounded ordered comparability graph for which there exists a compact compatible topology, thenGhas no infinite paths. Hence we were led to ask the following question, the answer to which will be given in this section.

Problem 2.1. If a cyclically bounded ordered comparability graph has no infinite paths, then does it have a compatible compact topology?

(5)

Recall that ablockin a graphGis a maximal 2-connected induced subgraph; a block is trivialif it contains only two vertices (and hence one edge). A well-known construction (see [3, page 36]) is theblock-cut-point treewhose vertices are the set of blocks together with the set of cut-points ofGand whose edges correspond to the adjacency of blocks and cut-points in the original graph. In the sequel,Kα,β denotes the complete bipartite graph onαandβvertices.

Theorem 2.2. LetG be a 2-connected ordered bipartite graph in which all cycles are of length at most 4; thenGis bilaterally compact.

Proof. IfGis a trivial block, then the result is clear. If not, then we claim thatG=K2,γfor some cardinalγ >1. To see this, consider the sets min(G) and max(G) of minimal and maximal elements ofG, respectively. Since each pair of points in a 2-connected graph lie in a cycle, wheneverv∈min(G) andw∈max(G), there is some 4-cycle containingvand wand hence [v,w]∈E(G); thusGis a complete bipartite graph. However, if both min(G) and max(G) have at least three elements, thenGcontains a copy of the complete bipartite graphK3,3and hence contains a cycle of length 6, thus proving our claim. To complete the proof of the theorem, it remains only to show that for each cardinalγ, the graphK2,γ is bilaterally compact; that is to say, for either of the two possible orderings ofK2,γ, there is a compact compatible topology onK2,γ. However, if the set of minimal elements is finite, then the Alexandroﬀtopology corresponding to that ordering is a compact compatible topology. If on the other hand, the set of minimal elements is infinite, then letting α denote the Alexandroﬀtopology induced by the ordering, we can define a topologyσon G=K2,γas follows: fixv0∈min(G), then

U∈σ if and only ifU∈αand ifv0∈U, thenG\Uis finite. (2.1) Ifγis infinite, then the relative topology whichσinduces on min(G) is homeomorphic to the one-point compactification of the discrete space of cardinalityγand henceσ is compact. We leave the routine verification thatσis compatible to the reader.

Remark 2.3. We note for future reference that the topologyσconstructed in the previous theorem on the 2-connected ordered bipartite graphG=K2,γhas (at least) one minimal vertex all of whose neighbourhoods are cofinite. If the set of<-minimal elements ofG is finite, then the topology onGis precisely the Alexandroﬀtopologyαinduced by the order<; if on the other hand, the set of minimal elements is infinite, then all vertices but one (the vertexv0 ofTheorem 2.2) have Alexandroﬀneighbourhoods. In either case,σ will be termed acanonicaltopology for the blockG. A minimal vertex all of whose neighbourhoods are cofinite inGwill be calleddetermining forG. Hence, ifσ is a canonical topology forG, then either there are a finite number of minimal vertices, all of which are determining or there is a unique minimal vertex which is determining, in which case this vertex will be termedspecial. It is also clear that every maximal element ofGisσ-open and each minimal element isσ-closed.

The following lemma shows that in the search for compact compatible topologies, we may restrict our attention to connected graphs.

(6)

Lemma2.4. If each graph component of an ordered comparability graph(G,<)has a com- pact compatible topology, then so does(G,<).

Proof. Let{Cα:α∈I}be the set of graph components of (G,<) and letσαbe a compact compatible topology forCα. IfIis finite, then the disjoint topological union of the spaces (Cα,σα) is the required compact space. If on the other handIis infinite, then fixα∈Iand x∈Cαand define a topologyτonGas follows:

U∈τ if and only ifU∩Cα∈σαand ifx∈U, thenU⊇

Cα:α∈I\Ffor some finiteF⊆I. (2.2)

We omit the straightforward proof thatτis a compact compatible topology for (G,<).

In order to prove our main theorem, we need some more notation. Suppose thatG has no infinite paths, thenGhas a non-cut-point. LetB0—theroot blockofG—be the block containing the non-cut-point which we denote byvB0. Every blockCofGdistinct fromB0contains a unique cut-pointvCofGwhose distance fromvB0is minimal among all other vertices ofC. Say that a blockCis animmediate successorblock to a blockB(or equivalently thatBis an immediate predecessortoC) ifB∩C= ∅,vB=vC, and every path fromvCtovB0 containsvB. Each block other thanB0has a unique immediate predecessor, but in general may have many immediate successors. Finally, say that a blockC is asuccessorto a blockBif there is a finite sequence of blocksB=B0,B1,...,Bn=Csuch thatBk+1is an immediate successor ofBkfor eachk∈ {0, 1,...,n−1}.

Theorem2.5. Let(G,<)be a connected ordered bipartite graph in which all cycles are of length no greater than 4. Then(G,<)has a compact compatible topology if and only if the associated block-cut-point tree has no infinite paths.

Proof. Suppose that (G,<) is such a connected ordered bipartite graph whose associated block-cut-point tree has no infinite paths.

Using the notation of the paragraph preceding this theorem, the ordering<onGde- termines an ordering<B0 on the root blockB0. Letσ0be a canonical compact topology forB0in which, if the non-cut-pointvB0(henceforth denoted byv0) is minimal in (G,<), then it is a determining vertex for (B0,σ0). IfGhas no cut-points, thenGconsists of the single bilaterally compact blockB0and we defineτ=σ0and we are done. Otherwise, we proceed to define a topologyσ onGas follows.

Let{Bα:α∈κ}be a well-ordering of the blocks ofGin such a way thatB0is the root block fixed previously and forα >0, letvαbe the cut-point ofGin Bα whose distance fromv0is minimal.

The ordering<onGdetermines an ordering<Bon each blockBofG. Since each block Bis either trivial or isomorphic toK2,γfor some cardinalγand each block has a unique immediate predecessor, it is clear that we can choose a canonical compact compatible topology σα onBα (in which every maximal element of (Bα,<Bα) is σα-open and each minimal element isσα-closed) and such that

(7)

(1) ifvαis a minimal vertex of the blockBα, thenσαis chosen in such a way thatvα

is a determining vertex forBα(and thus ifBαhas an infinite number of minimal vertices,vαwill be the unique special vertex of (Bα,σα)).

We now define a topologyσonGby

U∈σ if and only ifU∩Bα∈σαfor each blockBαofG. (2.3) A moment’s reflection now shows that the topologyσis well defined and that

(2) each vertex which is maximal with respect to<isσ-open, and each vertex which is minimal with respect to<isσ-closed; furthermore, for eachα∈κ,σ|Bα=σα; (3) ifz is minimal (resp., maximal), then the graph components ofG\ {z}areσ- open (resp.,σ-closed) inG. Furthermore, for eachz∈G, the graph components ofG\ {z}are open and closed inG\ {z};

(4) ifzis a maximal (resp., minimal) vertex ofG, theno(z)= ∪{Bβ: every path from vβtov0containsz}isσ-open (resp.,σ-closed). (o(z) may be thought of as those points which are separated fromv0byztogether withzitself.)

The topologyσ onGis weakly compatible since if [v,w]∈E(G), it follows thatv,w∈ Bαfor some blockBαofGand then by (2), sinceσαis a compatible topology forBα, it follows that{v,w}isσα-connected and henceσ-connected. Conversely, if [v,w]∈E(G), then there are two possibilities. Ifv,wlie in some blockBαofG, then sinceσαis a compatible topology forBα, it follows again from (2) that{v,w}is notσ-connected. If there is no block ofGcontaining bothvandw, then there is some cut-pointzofGsuch that vandwlie in diﬀerent graph components ofG\ {z}. Condition (3) now shows that the relativeσtopology on{v,w}is discrete.

We claim thatσ is a compatible topology forG. To show this, by [6, Lemma 2.7], it suﬃces to show that ifH is aσ-connected subset ofGandvis a vertex ofGsuch that N(v)∩H = ∅, thenv∈cl_σ(H). Now, to prove our claim, note that byRemark 2.3, if v∈Gis not a special determining vertex of any block, then eachσ-neighbourhood ofvin Gis an Alexandroﬀneighbourhood ofvinGand hencevhas a neighborhood contained inN(v). Hence if we assume thatN(v)∩H= ∅andv∈cl_σ(H), thenvmust be a special vertex of some block. However, ifvis special in some block, then eachσ-neighborhood ofvcontains all maximal vertices and all but finitely many minimal vertices of that block and soHmust meeto(z) for infinitely many minimal (nonspecial) verticesz(=v) lying in some blockBin whichvis special. By (4), each sucho(z) isσ-closed ando(z)\ {z}isσ- open; sinceHcannot contain any maximal vertices ofB(they all lie inN(v)),H∩o(z)= H∩(o(z)∪N(z)) is a proper open and closed subset ofH, a contradiction.

We now wish to modify the topologyσso as to obtain a compact compatible topology τonG. Letw0be a determining vertex forB0and for eachα >0 pick a determining vertex inBα, with the condition that ifvαis closed (and hence by the definition of the topology σα,vαis determining inBα), thenvαis the determining vertex so chosen. Denote byW this set of determining vertices and for each distinct vertexw∈W, we fix a blockBαsuch thatw is determining inBα. There may be many such blocks, but we assume that ifw is special in some block, thenBα is chosen so thatw is special inBαand also that the distance fromv0tovαis minimal among all blocks in whichwis special; in other words, ifwis special in some block, thenBαis chosen so thatwis special inBαbut not in the

(8)

immediate predecessor block ofBα. Also, ifzis a vertex ofG, then we denote the set of graph components ofG\ {z}which do not containv0byᏯz; it follows from (3) that ifz is maximal (resp., minimal), then each element ofᏯzis closed (resp., open) in (G,σ).

Now for eachw∈Wand each blockBαso chosen and for each finite setFof minimal vertices ino(vα)\ {w}, each finite setKof maximal vertices ofo(vα)\ {w}and each finite setᏴ⊆ ∪{Ꮿz:z∈K}, we define

V(w,F,K,Ᏼ)=

N(w)∪o(vα)\ ∪

o(z) :z∈F\ ∪Ᏼ. (2.4) Ifw=vα, thenvαis maximal and hence by (4),o(vα) isσ-open andN(w)⊆o(vα).

While ifw=vα, then sincewis not special in the immediate predecessor block ofBα, it follows again thatN(w)∪o(w) is aσ-open neighbourhood ofw. Thus in both cases, it follows from (3) and (4) that for each vertexw∈W,V(w,F,K,Ᏼ) isσ-open. We now define

Ꮾ=

U∈σ: wheneverw∈W∩U, thenU⊇V(w,F,K,Ᏼ) for some finite set of minimal verticesF⊆o(vα)\ {w}, some finite set of maximal verticesK⊆o(vα)\ {w} and some finite setᏴ⊆ ∪{Ꮿz:z∈K}

.

(2.5)

After a moment’s thought it is clear thatᏮis closed under finite intersections and henceᏮis a base for a topology which we denote byτ. Note also that ifBαis a block of Gandw∈Bαis determining inBα, thenwhas aσ-open neighbourhoodUsuch neigh- bourhoodU such thatBα\Uconsists of minimal vertices. Moreover, every other point ofBαhas aσ-neighborhood which misseswand henceτ|Bα=σ|Bαand clearlyτ⊆σ.

Finally it is clear from the definition ofτthat

(5) ifzis a maximal vertex, then each elementC∈Ꮿz isτ-closed andC∪ {z}(and henceo(z)) isτ-open, and ifzis a minimal vertex, then each elementC∈Ꮿz is τ-open ando(z) is closed.

We will prove thatτis a compact compatible topology for (G,<). To this end, we show first thatτis a weakly compatible topology forG. However, if [x,y]∈E(G), then there is some blockBα ofGsuch that x,y∈Bα and hence{x,y}isσα-connected and hence τ-connected. Conversely, if [x,y]∈E(G) andx,ylie in some blockBαofG, then sinceσα

is a compatible topology forBα, it follows again that{x,y}is notσ-connected. If there is no block ofGcontaining bothxandy, then there is some cut-pointz∈ {x,y}ofGsuch thatxand ylie in diﬀerent components ofG\ {z}. That{x,y}is discrete in (G,τ) now follows from (5) by considering the cases in whichzis maximal or minimal and whether or not one of the verticesxorylies in the component ofG\ {z}which containsv0.

Next we show thatτis a compatible topology forG. Sinceτis weakly compatible, it follows from [6, Lemma 2.7] that it suﬃces to show that ifHis anyτ-connected subgraph of GandN(w)∩H = ∅, thenw∈clτ(H). Ifw∈W, thenw has a τ-neighbourhood contained inN(w) and the result follows trivially; hence we suppose thatw∈Wand that Bαhas been chosen as above, that is to say,w is determining in the blockBα and ifw is special in some block, thenBαwas chosen so that the distance ofvαtov0 is minimal among all blocks in whichwis special.

(9)

Ifw∈clτ(H), then sinceN(w)∪o(vα) is aτ-open neighbourhood ofwandH∩N(w)

= ∅, it follows we can assume thatH⊆o(vα). There are two cases to consider.

(a) IfH meets some blockBcontainingw, then sinceH∩N(w)= ∅andN(w) contains all maximal vertices ofB, it follows thatH∩Bis a finite set of minimal vertices, say z1,...,zn. By (5), o(zi) is τ-closed for each i∈ {1,...,n} and so for each such zi, H∩o(zi)=H∩(o(zi)∪N(zi)) is aτ-clopen subset ofH. Thus for somei∈ {1,...,n}, H⊆o(zi) and so (N(w)∪o(vα))\o(zi) is aτ-open neighbourhood ofwmissingH.

(b) If on the other hand,H∩B= ∅for each blockBcontainingw, then for some blockBcontainingwthere is a vertexz∈Bsuch thatH∩o(z)= ∅, for otherwise,H∩ o(vα)= ∅. Sincewis determining in each block which contains it,zis not special inB.

Ifzis a minimal vertex, then sinceH∩o(z)=H∩(o(z)∪N(z)), it follows from (5) that H∩o(z) is aτ-clopen subset ofHand henceH⊆o(z)\ {z}. Thus (N(w)∪o(vα))\o(z) is aτ-open neighbourhood ofwmissingH. If on the other handzis maximal, thenH must meet some graph componentC∈Ꮿz. However, again using (5),Cisτ-closed and C∪ {z}isτ-open, thus sinceH∩C=H∩(C∪ {z}), it follows thatC∩H is a proper τ-clopen subset ofH. ThusH⊆Cand thenG\Cis aτ-open neighbourhood ofwwhich missesH.

Finally, we need to show that (G,τ) is compact. To this end, let᏿be a cover ofGby τ-open sets. There is someU0∈᏿such thatw0∈U0. Sincew0 is a determining vertex forB0andU0∈τ0, it follows thatUcoversGexcept for a finite number of sets{o(zi) :i∈ {1,...,n}}for some finite set of minimal vertices{zi: 1≤i≤n} ⊆B0and a finite number of graph components{Ci: 1≤y≤m}in∪{Ꮿz:z∈K}for some finite setKof maximal vertices inB0. LetBαi(1≤i≤m) be the (unique) immediate successor block ofB0which meetsCi. Sinceziis determining in each block which contains it,zi∈Wand each block Bαicontains a determining vertexwαi∈W. The above argument can now be repeated for the finite family of subgraphs{o(zi) : 1≤i≤n} ∪ {Ci: 1≤i≤m}. Since the block-cut- point tree ofGhas no infinite paths, it follows from K¨onig’s lemma (see [4, page 298]) that the process stops after a finite number of steps and we obtain a finite subcover of᏿, thus proving that (G,τ) is compact.

Conversely, suppose thatτis a compact compatible topology forGand the block-cut- point tree ofGhas an infinite path. ThenGcontains an infinite path of distinct vertices P= {pn:n∈N}. The intersection of this path with each blockBofGmust be finite since Bis either trivial or isomorphic toK2,γ for some cardinalγ. Hence, consideringP as an induced subgraph ofG, each vertexpn∈Phas only a finite number of graph neighbours and soPis blunt. Thus by [5, Corollary 2.15], the only compatible topology forPis the Alexandroﬀtopology. Thusτ|P is the Alexandroﬀtopology onP and hence is locally finite; it follows that (P,τ|P) is not compact and hence is not closed in (G,τ).

However, cl_τ(P) is compact, and ify∈cl_τ(P)\P, then since the intersection ofPwith each block is finite, it follows thatN(y)∩Pis finite. ThusN(y) misses some final interval of P, say N(y)∩ {pn:n≥k} = ∅. Sinceτ is a compatible topology for G, it follows from [6, Lemma 2.7] that there is someτ-neighbourhoodU of ywhich misses theτ- connected set{pn:n≥k} and henceU∩P is finite. Thus each vertex of clτ(P) has a τ-neighbourhood whose intersection withPis finite, contradicting the fact that cl_τ(P) is

compact.

(10)

We note that in the final paragraph of the proof ofTheorem 2.5, we have eﬀectively shown thatGhas an infinite path if and only if its block-cut-point tree has an infinite path and hence we have proved the following.

Corollary2.6. Let(G,<)be a connected ordered bipartite graph in which all cycles are of length no greater than 4. Then(G,<)has a compact compatible topology if and only ifGhas no infinite paths.

Since the operation of passing to the bipartite skeleton destroys all odd cycles, after applyingLemma 2.4we have shown the following.

Theorem2.7. Let(G,<)be an ordered comparability graph in which every cycle is of length at most 5, thenGhas a compact compatible topology if and only if it has no infinite paths.

Since every minimal vertex of a finite block is determining, similar methods can be used to prove the following theorem, but we omit the laborious details.

Theorem2.8. Let(G,<)be an ordered comparability graph in which every block is finite, thenGhas a compatible compact topology if and only if it has no infinite paths.

Example 2.9. For eachn∈N, letAnbe a copy ofC6(the6-cycle) where we suppose that V(An)= {v1,n,...,v6,n}. We denote the disjoint union of the graphsAnbyH and letG be the quotient graph obtained fromHby identifying each of the vertices{v1,n:n∈N}

and each of the vertices{v4,n:n∈N}.Gis clearly 2-connected and since ifv∈V(An) eitherv1,n∈N(v) orv4,n∈N(v), it follows thatGis blunt. It is then a consequence of [5, Corollary 2.15], that the only compatible topology forGis the Alexandroﬀtopology.

However, the Alexandroﬀtopology (corresponding to either of the two possible orderings ofG) is not compact since, as is easily seen, the set of minimal elements is infinite and discrete in the relative topology.

We have shown that there exists a bipartite graph with no infinite paths and all of whose cycles are of length 6, but which has no compact compatible topology. Thus Theorem 2.5andCorollary 2.6do not generalize to comparability graphs, all of whose cycles are of length at most 6 so proving thatTheorem 2.7is the best possible result and together withExample 2.9gives a complete answer toProblem 2.1.

An interesting question arises in regard to local connectivity of compact compatible topologies. The Alexandroﬀtopology on a poset or ordered comparability graph is locally connected as is the topologyτconstructed inTheorem 2.5. On the other hand, the trivial graph (no edges) on a countably infinite set of vertices has a compact compatible topology but no locally connected compact topology. However we do not know the answer to the following.

Problem 2.10. If a connected ordered comparability graph has a compact compatible topology does it have a locally connected compact compatible topology?

Acknowledgments

We thank the referee for his helpful comments. Research was supported by Consejo Na- cional de Ciencia y Tecnolog´ıa M´exico, Grant 38164-E. The second author wishes to

(11)

thank the University of Auckland for their hospitality during the preparation of this pa- per. Victor Neumann-Lara died on February 26, 2004.

References

[1] C. Berge, Graphs and Hypergraphs, North-Holland Mathematical Library, vol. 6, North- Holland, Amsterdam, 1973.

[2] R. Engelking,General Topology, Sigma Series in Pure Mathematics, vol. 6, Heldermann, Berlin, 1989.

[3] F. Harary,Graph Theory, Addison-Wesley, Massachusetts, 1957.

[4] A. L´evy,Basic Set Theory, Springer, Berlin, 1979.

[5] V. Neumann-Lara and R. G. Wilson,Compatible connectedness in graphs and topological spaces, Order12(1995), no. 1, 77–90.

[6] ,Compact compatible topologies for posets and graphs, Order15(1998), no. 1, 35–50.

[7] P. Pr´ea,Graphs and topologies on discrete sets, Discrete Math.103(1992), no. 2, 189–197.

Victor Neumann-Lara: Instituto de Matemáticas, Universidad Nacional Aut ónoma de México, Ciudad Universitaria, 04510 México DF, Mexico

Richard G. Wilson: Departamento de Matemáticas, Universidad Aut ónoma Metropolitana, Unidad Iztapalapa, Avenida San Rafael Atlixco 186, Apartado Postal 55-532, 09340 México DF, Mexico

E-mail address:[email protected]

(12)

Special Issue on

Intelligent Computational Methods for Financial Engineering

Call for Papers

As a multidisciplinary field, financial engineering is becom- ing increasingly important in today’s economic and financial world, especially in areas such as portfolio management, asset valuation and prediction, fraud detection, and credit risk management. For example, in a credit risk context, the re- cently approved Basel II guidelines advise financial institu- tions to build comprehensible credit risk models in order to optimize their capital allocation policy. Computational methods are being intensively studied and applied to improve the quality of the financial decisions that need to be made. Until now, computational methods and models are central to the analysis of economic and financial decisions.

However, more and more researchers have found that the financial environment is not ruled by mathematical distribu- tions or statistical models. In such situations, some attempts have also been made to develop financial engineering models using intelligent computing approaches. For example, an artificial neural network (ANN) is a nonparametric estima- tion technique which does not make any distributional as- sumptions regarding the underlying asset. Instead, ANN ap- proach develops a model using sets of unknown parameters and lets the optimization routine seek the best fitting parameters to obtain the desired results. The main aim of this special issue is not to merely illustrate the superior perfor- mance of a new intelligent computational method, but also to demonstrate how it can be used eﬀectively in a financial engineering environment to improve and facilitate financial decision making. In this sense, the submissions should especially address how the results of estimated computational models (e.g., ANN, support vector machines, evolutionary algorithm, and fuzzy models) can be used to develop intelligent, easy-to-use, and/or comprehensible computational systems (e.g., decision support systems, agent-based system, and web-based systems)

This special issue will include (but not be limited to) the following topics:

• Computational methods: artificial intelligence, neural networks, evolutionary algorithms, fuzzy inference, hybrid learning, ensemble learning, cooperative learning, multiagent learning

• Application fields: asset valuation and prediction, asset allocation and portfolio selection, bankruptcy prediction, fraud detection, credit risk management

• Implementation aspects: decision support systems, expert systems, information systems, intelligent agents, web service, monitoring, deployment, implementation

Authors should follow the Journal of Applied Mathemat- ics and Decision Sciences manuscript format described at the journal site http://www.hindawi.com/journals/jamds/.

Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Track- ing System athttp://mts.hindawi.com/, according to the following timetable:

Manuscript Due December 1, 2008 First Round of Reviews March 1, 2009 Publication Date June 1, 2009

Guest Editors

Lean Yu,Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;

Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong;

[email protected]

Shouyang Wang,Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; [email protected]

K. K. Lai,Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong; [email protected]

Hindawi Publishing Corporation http://www.hindawi.com