IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 50 (2012), 1171 ISSN 2232-2094 BUCOLIC COMPLEXES B. Brešar J. Chalopin V. Chepoi T. Gologranc D. Osajda Ljubljana, February 10, 2012 O CM IN I CM 00 CM CM CO CO CO u a CD U Bucolic complexes 1Faculty of Natural Sciences and Mathematics, University of Maribor, Koroska cesta 160, SI-2000 Maribor, Slovenia B. BREŠAR1, J. CHALOPIN2, V. CHEPOI2, T. GOLOGRANC3, and D. OšAJDA4,5 Ctf bostj an.bresar@uni-mb.si 2Laboratoire d'Informatique Fondamentale, Aix-Marseille Universite and CNRS, , Faculte des Sciences de Luminy, F-13288 Marseille Cedex 9, France {jeremie.chalopin, victor.chepoi}@lif.univ-mrs.fr 3Institute of Mathematics, Physics and Mechanics, Jadranska 19, SI-1000 Ljubljana, Slovenia tanja.gologranc@imfm.si 4Universitat Wien, Fakultät für Mathematik Nordbergstraße 15, 1090 Wien, Austria 5Instytut Matematyczny, Uniwersytet Wroclawski, pl. Grunwaldzki 2/4, 50-384 Wroclaw, Poland dosaj @math.uni.wroc.pl CM Abstract. In this article, we introduce and investigate bucolic complexes, a common generalization of systolic complexes and of CAT(0) cubical complexes. This class of complexes is closed under Cartesian products and amalgamations over some convex subcomplexes. We study various approaches to bucolic complexes: from graph-theoretic and topological viewpoints, as well as from the point of view of geometric group theory. Bucolic complexes can be defined as locally-finite simply connected prism complexes satisfying some local combinatorial conditions. We show that bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. In particular, we prove a version of the Cartan-Hadamard theorem, the fixed point theorem for finite group actions, and establish some results on groups acting geometrically on such complexes. We also characterize the 1-skeletons (which we call bucolic graphs) and the 2-skeletons of bucolic complexes. In particular, we prove that bucolic graphs are precisely retracts of Cartesian products of locally finite weakly bridged graphs (i.e., of 1-skeletons of weakly systolic complexes). We show that bucolic graphs are exactly the weakly modular graphs satisfying some local conditions formulated in terms of forbidden induced subgraphs and that finite bucolic graphs can be obtained by gated amalgamations of products of weakly bridged graphs. ^ 1. INTRODUCTION Cß Avant-propos. In this paper, we introduce bucolic complexes and their 1-skeletons - bucolic graphs. Bucolic complexes can be defined as simply connected prism complexes satisfying some local combinatorial conditions. This class of cell complexes contains the class of CAT(0) cubical complexes and of weakly systolic simplicial complexes and is closed under Cartesian products and amalgamations over some convex subcomplexes. We show that bucolic complexes satisfy some nonpositive-curvature-like properties: we prove a version of the Cartan-Hadamard theorem, and the fixed point theorem for finite group actions. On the other hand, o fi we characterize the 1-skeletons of bucolic complexes in several different ways, in particular, we show that the bucolic graphs are exactly the retracts of Cartesian products of weakly bridged graphs, i.e., of 1-skeletons of weakly systolic complexes (in comparison, notice that the median graphs - the 1-skeletons of CAT(0) cubical complexes - are exactly the retracts of Cartesian products of edges, i.e., 1-skeletons of 1-simplices). Finally, we characterize the triangle-square complexes which can be realized as 2-skeletons of bucolic complexes as simply connected triangle-square complexes satisfying some local combinatorial conditions. Graph-theoretic and geometric viewpoint. Median and bridged graphs constitute two of the most important classes of graphs investigated in metric graph theory and occur in different areas of discrete mathematics, geometric group theory, CAT(0) geometry, and theoretical computer science. Median graphs and related structures (median algebras and CAT(0) cubical complexes) have many nice properties and admit numerous characterizations. All median structures are intimately related to hypercubes: median graphs are isometric subgraphs of hypercubes; in fact, by a classical result of Bandelt [2] they are the retracts of hypercubes into which they embed isometrically. It was also shown by Isbell [28] and van de Vel [38] that every finite median graph G can be obtained by successive applications of gated amalgamations from hypercubes, thus showing that the only prime median graph is the two-vertex complete graph K2 (a graph with at least two vertices is said to be prime if it is neither a Cartesian product nor a gated amalgam of smaller graphs). Median graphs also have a remarkable algebraic structure, which is induced by the ternary operation on the vertex set that assigns to each triplet of vertices the unique median vertex, and their algebra can be characterized using four natural axioms [7,28] among all discrete ternary algebras. Finally, it was shown in [19,35] that the median graphs are exactly the 1-skeletons of CAT(0) cubical complexes. Thus, due to a result of Gromov [24], the cubical complexes derived from median graphs can be characterized as simply connected cubical complexes in which the links of vertices are flag simplicial complexes. Sageev [36] established several important geometrical properties of hyperplanes in CAT(0) cubical complexes, and initiated the investigation of groups acting on such complexes. For more detailed information about median structures, the interested reader can consult the survey [6] and the books [27,30,39]. Bridged graphs are the graphs in which all isometric cycles have length 3. It was shown in [23,37] that the bridged graphs are exactly the graphs in which the metric convexity satisfies one of the basic properties of Euclidean geometry (and, more generally, of the CAT(0) geometry): neighborhoods of convex sets are convex. Combinatorial and structural aspects of bridged graphs have been investigated in [1,16,34]. In particular, it was shown in [1] that bridged graphs are dismantlable (a simpler algorithmic proof is given in [18]), showing that the clique complexes (i.e., the simplicial complexes obtained by replacing complete subgraphs by simplices) of bridged graphs are collapsible. Similarly to the local-to-global characterization of CAT(0) cubical complexes of [24], it was shown in [19] that the clique complexes of bridged graphs are exactly the simply connected simplicial flag complexes in which the links of vertices do not contain induced 4- and 5-cycles. These complexes have been rediscovered and investigated in depth by Januszkiewicz and Swiatkowski [29], and, independently by CO u a CD U IN Haglund [25], who called them "systolic complexes" and considered as simplicial complexes satisfying combinatorial nonpositive curvature property. More recently, Osajda [32] proposed a generalization of systolic complexes still preserving some structural properties of systolic complexes: the resulting weakly systolic complexes and their 1-skeletons - the weakly bridged graphs - have been investigated and characterized in [20]. Since CAT(0) cubical complexes and systolic simplicial complexes can be both characterized via their 1-skeletons and via simple connectivity and a local condition on links, a natural question is to find a common generalization of such complexes which still obey the combinatorial nonpositive curvature properties. The cells in such complexes are prisms (Cartesian products of simplices) and the 2-dimensional faces are triangles and squares. In [11], answering a question from [12], the 1-skeletons of prism complexes resulting from clique complexes of chordal graphs by applying Cartesian products and gated amalgams have been characterized: those graphs (which are exactly the retracts of products of chordal graphs) are the weakly modular graphs not containing induced K2,3, wheels Wk, and almost wheels W-, k > 4 (weakly modular graphs and some other classes of graphs are defined in next section). It was also shown that, endowed with the 12-metric, such prism complexes are CAT(0) spaces. The structure theory of graphs based on Cartesian multiplication and gated amalgamation was further elaborated for more general classes of graphs. Some of the results for median graphs have been extended to quasi-median graphs introduced by Mulder [30] and further studied in [8]: quasi-median graphs are precisely the weakly modular graphs not containing induced K2 3 and K4 - e; they can also be characterized as the retracts of Hamming graphs CM and can be obtained from complete graphs by Cartesian products and gated amalgamations. More recently, Bandelt and Chepoi [4] presented a similar decomposition scheme of weakly median graphs and characterized the prime graphs with respect to this decomposition: the hyperoctahedra and their subgraphs, the 5-wheel W5, and the 2-connected plane bridged graphs (i.e., plane triangulations in which all inner vertices have degrees > 6). Generalizing the CO proof of the decomposition theorem of [4], Chastand [14,15] presented a general framework of CO fiber-complemented graphs allowing to establish many general properties, previously proved only for particular classes of graphs. An important subclass of fiber-complemented graphs is that of pre-median graphs [14, 15] which are the weakly modular graphs without induced K2,3 and K2,3 with an extra edge (which can be viewed as the graph W- defined below). It is an open problem to characterize all prime (elementary) fiber-complemented or pre-median graphs (see [14, p. 121]). In this paper, we continue this line of research and characterize the graphs G which are retracts of Cartesian products of weakly bridged and bridged graphs. We show (cf. Theorem 2 below) that retracts of Cartesian products of weakly bridged (resp., bridged) graphs are exactly the weakly modular graphs which do not contain K2,3, the wheel W4, and the almost wheel W4- (resp., K2,3, W4, W5 and W-) as induced subgraphs (for an illustration of these forbidden graphs, see Fig. 1). We establish that these pre-median graphs are exactly the graphs obtained by gated amalgamations of Cartesian products of weakly bridged (or of bridged) graphs, thus answering Question 1 from [11]. This also provides a partial answer to a o CM 00 CM CM o CM rO CD U a CD U Chastand's problem mentioned above by showing that the weakly bridged graphs are exactly the prime graphs of pre-median graphs without W4 and that the bridged graphs are the prime graphs of pre-median graphs without W4 and W5. Topological and geometric group theory viewpoint. Analogously to median graphs which are built from cubes, are retracts of hypercubes, and gives rise to CAT(0) cubical complexes, the graphs studied in this article are built from Hamming graphs (i.e., products of simplices), are retracts of products of bridged or weakly bridged graphs (i.e., 1-skeletons of systolic or weakly systolic complexes), and thus they can be viewed as 1-skeletons of some cell complexes with cells being prisms (or Hamming cells), i.e., products of simplices. We call such prism complexes bucolic complexes1. Thus our previous result can be viewed as a characterization of 1-skeletons of bucolic complexes. We also characterize (Theorem 1 below) bucolic complexes via their 2-skeletons (consisting of triangle and square faces) by showing that they are exactly the simply connected triangle-square complexes satisfying the cube and house conditions and not containing W4, W5, and W5- (this answers Question 2 from [11]). Then we prove that the bucolic complexes are contractible (Theorem 3). Thus the three results constitute a version of the Cartan-Hadamard theorem, saying that under some local conditions the complex is aspherical, i.e. its universal covering space is contractible. Only limited number of such local characterizations of asphericity is known, and most of them refer to the notion of nonpositive curvature; cf. e.g. [13,22,24,29,32]. In fact bucolic complexes CM exhibit many nonpositive-curvature-like properties. Besides the Cartan-Hadamard theorem we prove the fixed point theorem for finite groups acting on bucolic complexes (Theorem 4), and we conclude that groups acting geometrically on such complexes have finitely many conjugacy classes of finite subgroups (Corollary 2). Counterparts of such results are known CM for other nonpositively curved spaces; cf. e.g. [13,20,29,32]. Thus our classes of complexes and groups acting on them geometrically form new classes of combinatorially nonpositively curved complexes and groups (see e.g. [20, 24, 29, 32] for more background) containing the CAT(0) cubical and systolic classes of objects. A question of studying such unification theories was raised often by various researchers, e.g. by Januszkiewicz and Swi§tkowski (personal communication). Due to our knowledge, bucolism is the first generalization of the CAT(0) cubical and systolic worlds studied up to now. The class of bucolic complexes is closed under taking Cartesian products and amalgamations over some convex subcomplexes - the gated subcomplexes. Thus the class of groups acting geometrically on them is also closed under similar operations. It should be noticed that both systolic and CAT(0) cubical groups satisfy some strong (various for different classes) restrictions; cf. e.g. [32] and references therein. It implies that there are groups that are neither systolic nor CAT(0) cubical but which act geometrically on our complexes. In particular, in view of Theorem 4 and the fixed point theorems for systolic and CAT(0) complexes (compare [20]), the free product of a systolic group with a CAT(0) cubical group always act geometrically on a complex from our class, ^The term bucolic is inspired by systolic, where b stands for bridged and c for cubical. See also the acknowledgement for another source of our "inspiration". i-H o ft CD IN CO u a CD U although the group being such a product is often not systolic neither CAT(0) cubical. Another example with this property is the Cartesian product of two systolic but not CAT(0) cubical groups. Article's structure. In the following Section 2 we introduce all the notions used later on. In Section 3 we state the main results of the article mentioned above (Theorems 1-4). In Section 4, we provide the characterization of bucolic graphs (Theorem 2). A proof of the main characterization of bucolic complexes (Theorem 1) is presented in Section 5. In Section 6 we prove the contractibility and the fixed point result for bucolic complexes (Theorems 3 and 4). Acknowledgements. This research was supported by the French-Slovenian Egide PROTEUS project "Distances, structure and products of graphs". B.B. is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana, and was also supported by the Ministry of Science and Technology of Slovenia under the grants J1-2043 and P1-0297. V.C. was also supported by the ANR Projets Blanc THEOMATRO and GGAA. D. O. was partially supported by MNiSW grant N201 012 32/0718. The authors would like to acknowledge the participants of the ANR project GRATOS for organizing the workshop "Journees Graphes et Structures Topologiques" in a bucolic place in the Cevennes and for inviting three of us to participate. 2. Preliminaries 2.1. Graphs. All graphs G = (V, E) occurring in this paper are undirected, connected, and without loops or multiple edges, locally-finite but not necessarily finite. For two vertices u and v of a graph G, we will write u ~ v if u and v are adjacent and u + v, otherwise. We will use the notation v ~ A to note that a vertex v is adjacent to all vertices of a set A and the notation v + A if v is not adjacent to any of the vertices of A. The distance d(u,v) = dG (u,v) between two vertices u and v is the length of a shortest (u,v)-path. For a vertex v of a graph G we will denote by B\(v,G) the set of vertices consisting of v and the neighbors of v in G. We call Bi(v,G) the 1-ball centered at v. More generally, we denote by Br(v,G) the ball in G of radius r and centered at vertex v. The interval I(u,v) between u and v consists of all vertices on shortest (u,v)-paths, that is, of all vertices (metrically) between u and v: I(u,v) = {x e V : d(u,x) + d(x,v) = d(u,v)}. An induced subgraph of G (or the corresponding vertex set A) is called convex if it includes the interval of G between any pair of its vertices. The smallest convex subgraph containing a given subgraph S is called the convex hull of S and is denoted by conv(S). An induced subgraph H of a graph G is said to be gated if for every vertex x outside H there exists a vertex x' (the gate of x) in H such that each vertex y of H is connected with x by a shortest path passing through the gate x' (i.e., x' e I(x,y)). The smallest gated subgraph containing a given subgraph S is the gated hull of S. A graph G = (V, E) is isometrically embeddable into a graph H = (W,F) if there exists a mapping : V ^ W such that dH(^(u),^(v)) = dG(u,v) for all vertices u,v e V. A retraction

2, if three k-cubes of X pairwise intersect in a (k - 1)-cube and all three intersect in a (k - 2)-cube of X, then are included in a (k + 1)-dimensional cube of X. Independently, Chepoi [19] and Roller [35] established that the 1-skeletons of CAT(0) cube complexes are exactly the median graphs, i.e., the graphs in which any triplet of vertices admit a unique median vertex. CO u a CD U CU 9 o CM & u CD IN Figure 3. The cube condition (left), the house condition (middle), and the IF5-wheel condition (right). 0 o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO Jh a CD U Now we briefly recall the definitions of systolic and weakly systolic simplicial complexes, which are both considered simplicial complexes with combinatorial nonpositive curvature. For an integer k > 4, a flag simplicial complex X is locally k-large if every cycle consisting of less than k edges in any of its links of simplices has some two consecutive edges contained in a 2-simplex of this link, i.e., the links do not contain induced cycles of length < k. A simplicial complex is k-systolic if it is locally k-large, connected and simply connected. A flag simplicial complex is systolic if it is 6-systolic [19,25,29]. It was shown in [19] that systolic complexes are exactly the clique complexes of bridged graphs. On the other hand, among many other results, it was shown in [29] that the 1-skeletons of 7-systolic complexes are Gromov hyperbolic. In the same paper were given sufficient combinatorial conditions under which a systolic complex with regular simplices as cells is a CAT(0) space. A generalization of systolic complexes inheriting many of their properties have been proposed in [32] and [20]: a simplicial complex X is weakly systolic if and only if X is flag, connected and simply connected, locally 5-large, and satisfies the following local condition: W5-wheel condition: for each extended 5-wheel X(W5) of X, there exists a vertex v adjacent to all vertices of this extended 5-wheel (see Fig. 3, right). It was shown in [20] that the weakly bridged graphs, i.e. the 1-skeletons of weakly systolic complexes, are exactly the weakly modular graphs without induced 4-cycles or, equivalently, the weakly modular graphs with convex balls. 3. Main results 3.1. Bucolic complexes. A prism complex X is bucolic if it is flag, connected and simply connected, and satisfies the following three local conditions: (W4,W5)-condition: the 1-skeleton X(1) of X does not contain induced W4 and satisfies the W5-wheel condition; o CM IN o CM CM CO CO u a CD u Hypercube condition: if k > 2 and three k-cubes of X pairwise intersect in a (k - 1)-cube and all three intersect in a (k - 2)-cube, then they are included in a (k + 1)-dimensional cube of X; & Hyperhouse condition: if a cube and a simplex of X intersect in a 1-simplex, then they are included in a prism of X. _ As we already noticed in the previous section, subject to simply connectivity, the (W4,W5)-condition characterizes the weakly systolic complexes. On the other hand, as we noticed above, the hypercube condition is equivalent to Gromov's condition of flagness of links. Fi-~ nally, the hyperhouse condition shows how simplices and cubes of X give rise to prisms. We call a graph G bucolic if G is the 1-skeleton of a bucolic complex X, i.e., G = X(1). Now, we consider the 2-dimensional versions of the last two conditions. We say that a triangle-square complex X satisfies: Cube condition: any three squares of X, pairwise intersecting in an edge, and all three intersecting in a vertex of X, are included in a 3-dimensional cube (see Fig. 3, left); House condition: any house (i.e., a triangle and a square of X sharing an edge) is included in a 3-dimensional prism (see Fig. 3, middle). We start with the main result of our paper, which is a local-to-global characterization of the 1- and the 2-skeletons of bucolic complexes. It can be viewed as an analogue of similar local-to-global characterizations of CAT(0) cube complexes, systolic, and weakly systolic complexes provided in the papers [19,20,29,32]. Theorem 1. For a locally-finite prism complex X, the following conditions are equivalent: (i) X is a bucolic complex:; (ii) the 2-skeleton X(2) of X is a connected and simply connected triangle-square flag complex satisfying the (W4, W5)-condition, the cube condition, and the house condition; (iii) the 1-skeleton G(X) of X is a weakly modular graph not containing induced subgraphs of the form K2,3, W4 and W-. Moreover, if X is a connected flag prism complex satisfying the (W4 ,W5 ), the hypercube, and the hyperhouse conditions, then the universal cover XX of X is bucolic. The proof of this theorem is provided in Section 5. The most difficult part of the proof is to show that the 1-skeleton of a simply connected triangle-square complex X satisfying the local conditions of the theorem is weakly modular. To show this, we closely follow the proof method of a local-to-global characterization of weakly systolic complexes provided by Osajda [32] using the level-by-level construction of the universal cover of X. Analogously to Theorem 1, one can characterize the prism complexes derived from systolic complexes. We will say that a bucolic complex X is strongly bucolic if it satisfies the following (W4,W5)-condition: the 1-skeleton X(1) of X does not contain induced W4 and W5. Corollary 1. For a locally-finite prism complex X, the following conditions are equivalent: 5H (i) X is a strongly bucolic complex; (ii) the 2-skeleton X(2) of X is a connected and simply connected triangle-square flag complex satisfying the (W4,W5)-condition, the cube condition, and the house condition; (iii) the 1-skeleton G(X) of X is a weakly modular graph not containing induced subgraphs of the form K2,3, W4, W-, and W5. Moreover, if X is a connected flag prism complex satisfying the (W4,W5), the hypercube, and the hyperhouse conditions, then the universal cover XX of X is strongly bucolic. CD 3.2. Bucolic graphs. In this subsection, we present several characterizations of finite and locally-finite bucolic graphs. We show that finite bucolic graphs are exactly the finite graphs which are obtained from Cartesian products of bridged graphs or weakly bridged graphs via gated amalgamations. We also show that the locally-finite bucolic graphs are the weakly modular graphs that do not contain induced K2,3, 4-wheels W4, and almost-wheels W4- and that they are exactly the retracts of Cartesian products of weakly bridged graphs: Theorem 2. For a locally-finite graph G = (V,E), the following conditions are equivalent: (i) G is a retract of the (weak) Cartesian product of weakly bridged (resp., bridged) graphs; (ii) G is a weakly modular graph not containing induced K2,3, W4, and W4- (resp., K2,3, W-, W4, and W5), i.e., G is a bucolic graph; (iii) G is a K2,3, W4 -free weakly modular graph in which all elementary (or prime) subgraphs are edges or 2-connected weakly bridged (resp., bridged) graphs. Moreover, if G is finite, then the conditions (i)-(iii) are equivalent to the following condition: (iv) G can be obtained by successive applications of gated amalgamations from Cartesian products of 2-connected weakly bridged (resp., bridged) graphs. The proof of this theorem is provided in Section 4. The most difficult part of the proof is the implication (ii)^(iii), which we establish in two steps. First we show that if G is a weakly modular graph not containing induced W4 and W4-, then all its primes are 2-connected weakly CO bridged graphs or K2. Then, we deduce both theorems using the results of [5,14,15,20]. The following convexity property of bucolic graphs (proved in Section 4) will be useful for establishing contractibility and fixed point results for bucolic complexes. Proposition 3.1. If G = (V,E) is a locally-finite bucolic graph, then the convex hull conv(S) in G of any finite set S c V is finite. 3.3. Contractibility and the fixed point property. Using previous results, we establish the following basic properties of bucolic complexes (proofs are provided in Section 6). The first result is a version of the Cartan-Hadamard theorem. It has its CAT(0) (cf. [13, Corollary 1.5]) and systolic (cf. [19, Theorem 8.1]&[18] and [29, Theorem 4.1]) counterparts. CD Theorem 3. Bucolic complexes are contractible. U a CD U The above property is the most important nonpositive-curvature-like property of bucolism. Beneath we provide further properties of a nonpositive-curvature-like nature. All of them have their CAT(0) and systolic counterparts; cf. [13,20]. o cm in 00 cm cm CO CD co u a CD U Theorem 4. If X is a bucolic complex and F is a finite group acting by cell automorphisms on X, then there exists a prism n of X which is invariant under the action of F. The center of the prism n is a point fixed by F. A standard argument (see e.g. the proof of [20, Corollary 6.4]) gives the following immediate consequence of Theorem 4. Jh Corollary 2. Let F be a group acting geometrically by automorphisms on a bucolic complex X. Then F contains only finitely many conjugacy classes of finite subgroups. 4. Proofs of Theorem 2 and Proposition 3.1 4.1. Gated closures of triangles. In this section, we prove that if G is a weakly modular graph not containing induced 4-wheels W4 and almost 4-wheels W— then the gated hull of a triangle is a weakly bridged graph. Additionally, we show that if G does not contain induced 5-wheels W5, then the gated hull of a triangle is a bridged graph. £ Lemma 4.1. Let G be a weakly modular graph without induced W4 and W4 . Then G does not contain an induced W" for n > 4. Proof. Suppose by way of contradiction that W" is an induced subgraph of G and suppose that G does not contain induced Wj for any 3 < k < n. Let (xi,x2,... ,xn,x1) be the outer cycle C of W" and consider a vertex c adjacent to all vertices of C except x1. We apply the triangle condition to the triple x1,x2,xra_1 and find a vertex a e N(x1) n N(x2) n N(xra_1). Note that if a ~ c, then x1,x2, c, xn,a induce W4 if a is adjacent to xn or W4" otherwise. Assume now that a + c. If n = 5, then the vertices x4,a,x2, c,x3 induce either W4 if x3 is adjacent to a, or W__ otherwise. Now, if n > 6 and if a is not adjacent to x3,x4,... ,xn_ 3 or xn_2, the subgraph induced by the vertices a,x2,x3,...,xn_ 1 ,c has an induced subgraph CO isomorphic to one of the forbidden induced subgraphs Wj , where k < n. Thus a is adjacent to all vertices of C except maybe xn. The vertices a,x3, c, xn_ 1 ,x4 induce W4, if n = 6, or W4 otherwise, a contradiction. □ By an (a, b)-walk of a graph G we mean a sequence of vertices W = (a = xo, x1,..., xk _ 1, xk = b) such that any two consecutive vertices xi and xi+1 of W are different and adjacent (notice that in general we may have xi = xj if \i - j\ > 2). If k = 2, then we call W a 2-walk of G. A 2-walk W in which all three vertices are different is called a 2-path. Let H be an induced subgraph of a graph G. A 2-walk W = (a,v,b) of G is H-fanned if a,v,b e V(H) and if there exists an (a, b)-walk W' in H not passing via v and such that v is adjacent to all vertices of W', i.e., v ~ W'. Notice that W' can be chosen to be an induced path of G. A walk W = (x0,x1 ,...,xk _ 1 ,xk) of G with k > 2 is H-fanned if every three consecutive vertices (xi ,xi+1 ,xi+2) of W form an H-fanned 2-walk. When H is clear from the context (typically when H = G), we say that W is fanned. If the endvertices of a 2-walk W = (a,v,b) coincide or are adjacent, then W is fanned. Here is a generalization of this remark. i-H o rO CD O u a CD U Lemma 4.2. If W = (x0,xl,... ,xk) is a fanned walk and the vertices xi-l and xi+l coincide or are adjacent, then the walks W' = (x0,... ,xi-2,xi+l,xi+2, ■ ■ ■ ,xk) in the first case and W" = (x0,..., xi-\,xi+i, ■ ■ ■ ,xk) in the second case are also fanned. Proof. First suppose that xi-l = xi+l. Every 2-walk (xj,xj+l,xj+2), where j < i-4 or j > i+1 is fanned, because W is fanned. Thus to show that the walk W' is fanned it suffices to show that the 2-walk (xi-2,xi+i,xi+2) is fanned. Since the 2-walks (xi-2,xi-i,xi) and (xj,,xi+i,xi+2) are fanned as 2-walks of W, there exist a (xi-2,xi)-walk Rl not passing via xi-l and a (xi,xi+2)-walk R2 not passing via xi+l such that xi-l ~ Rl and xi+l ~ R2. Since xi-l = xi+l, we conclude that the vertex xi+l is adjacent to all vertices of the (xi-2,xi+2)-walk (Rl,R2), showing that the 2-walk (xi-2,xi-l,xi+2) is fanned. Now, let xi-l ~ xi+l. Every 2-walk (xj,xj+l,xj+2), where j < i - 3 or j > i + 1 is fanned, because W is fanned. Therefore, to show that W" is fanned it suffices to show that the 2-walks (xi-2,xi-l,xi+l) and (xi-l,xi+l,xi+2) are fanned. Since both cases are similar, we will check the first one. Since the 2-walk (xi-2,xi-l,xi) is fanned, there exists a (xi-2,xi)-walk R such that xi-l ~ R. Therefore (R,xi+l) is a (xi-2,xi+l)-walk with all vertices adjacent to xi-i. Hence the 2-walk (x--2, x--i, x-+i ) is fanned. □ In the remaining auxiliary results of this section we assume that G is a locally finite (possibly infinite) weakly modular graph without induced W4 and W4-. By Lemma 4.1, G does not contain W- with k > 3. Lemma 4.3. If C = (x,u,y,v,x) is an induced 4-cycle of G, then no induced 2-path of C is fanned. Proof. Suppose that the 2-path P = (u,y,v) is fanned. Let R = (u,tl,... ,tm,tm+l = v) be a shortest (u, v)-walk such that y ~ R (such a walk exists because P is fanned). Necessarily, R is an induced path of G. Since C is induced, m > 1 and ti t x for all i e {1, ■ ■ ■, m}. If tl is CO adjacent to x, then the vertices x, u, y, v, ti induce W4 if ti is adjacent to v, or W4- otherwise. CO Suppose now that ti is not adjacent to x and let i > 2 be the smallest index such that ti is adjacent to x. Since R is a shortest walk, the cycle (x,u,tl,...,ti,x) is induced. Thus the vertices x,u,tl,... ,ti,y induce a forbidden Wi"+2. □ Let v be a common neighbor of vertices a and b of G. For an (a, b)-walk W, we denote by D(W) the distance sum D(W) ■■= d(x,v). Lemma 4.4. Let W = (a = x0,xl,... ,xm = b) be a fanned (a,b)-walk not containing v, let k = max{d(xi,v) ■ xi e W} > 2 and j be the smallest index so that d(xj,v) = k. Then either xj-l = xj+l and the walk W' = (x0, ■ ■ ■, xj-2, xj+l,xj+2,..., xm) is fanned or xj-l ~ xj+l and the walk W" = (x0, ■ ■ ■ , xj-i, xj + i, ■ ■ ■ , xm ) is fanned, or there exists a vertex y such that d(y,v) = k - 1 and the walk W"' = (xo,... , xj-l, y, xj + l, ■ ■ ■ , xm ) is fanned. In particular, if W is a fanned (a,b)-walk avoiding v with minimal distance sum D(W), then v ~ W. Proof. If Xj-\ = Xj+i or Xj-\ ~ Xj+\, then Lemma 4.2 implies that the walks W' and W" are fanned. So, suppose that Xj-i and Xj+i are different and non-adjacent. Note that d(xj-i,v) = IN k -1 and k -1 < d(xj+1,v) < k. If d(xj+1,v) = k -1, then we can use the quadrangle condition for vertices v,xj-1,xj and xj+1 and find a vertex z e N(xj_1)nN(xj+1) such that d(v, z) = k-2 (z = v if k = 2). Since z and xj are not adjacent, the 4-cycle (z,xj-1,xj,xj+1,z) is induced. Since W is fanned, the 2-walk (xj-1,xj,xjis fanned as well, contradicting Lemma 4.3. So, suppose that d(xj+1,v) = k. Applying the triangle condition to the triple v,xj,xj+1, we can find a common neighbor y of xj and xj+1 with d(v,y) = k - 1. Note that y t xj-1 since xj-1 + xj+1. First, let xj-1 + y. Then we can apply the quadrangle condition to the vertices xj-1,xj,y,v, and find a vertex z e N(xj-1) n N(y) with d(z,v) = k - 2 (z = v if k = 2). Clearly, z is not adjacent to xj and xj+1. Hence, the cycle (xj-1,xj ,y,z,xj-1) is induced. Since the 2-walk (xj-1,xj ,xj+1) is fanned, there exists a (xj-1, xj+1 )-walk Q0 not containing xj such that xj - Q0. As a consequence, (Q0,y) is a (xj-1,y)-walk of G not passing via xj whose all vertices are adjacent to xj. Therefore the 2-walk (xj-1,xj ,y) of the induced 4-cycle (xj-1,xj,y,z,xj-1) is fanned, contradicting Lemma 4.3. This implies that xj-1 must be adjacent to y. Then W''' = (x0,... ,xj-1,y,xj+1,... ,xm) is a walk of G. We claim that W''' is fanned. Indeed, all 2-paths of W''', except the three consecutive 2-walks (xj-2,xj-1,y), (y,xj+1 ,xj+2), (xj-1 ,y,xj+1), are also 2-walks of W, hence they are fanned. The 2-walk (xj-1,y,xj+1) is fanned because y is adjacent to all vertices of the walk (xj-1,xj,xj+1). Since the 2-walk (xj,xj+1,xj+2) is fanned, there is an (xj, xj+2)-walk R such that xj+1 - R. Then all vertices of the (y,xj+2)-walk (y,R) are adjacent to xj+1, whence the 2-walk (y,xj+1,xj+2) is fanned. Analogously, one can show that the 2-walk (xj-2,xj-1,y) is fanned, showing that W''' is fanned. Since each of D(W'),D(W''),D(W''') is smaller than CM D(W), we conclude that if W is a fanned (a, b)-walk not containing v with minimal distance sum D(W), then k = 1, i.e., v - W. □ CM CM Now, let us define the concept of a twin-ball. Let S be a finite subset of a vertex set of G. We define TB0(S) = S and suppose that the twin-ball TBt(S) is already determined for CO some t > 0. Then let TBt+1(S) be defined as the set of vertices from G that have at least two CO neighbors in TBt(S). Note that every TBt(S) is finite, since G is a locally finite graph. Let T be a triangle in G. Let H3,H4,... be a (possibly infinite) sequence of induced 2-connected subgraphs of G, with H3 = T and Hi+1 is the subgraph of G induced by V(Hi)u{v}: where v is an arbitrary vertex from the ball TBt(T), t being the smallest integer such that all vertices from TBt-1(T) lie in H,. (If there exists no such vertex v then the procedure stops after a finite number of steps.) Hence v has at least two neighbors in H,. Let K := U^ H,. In the following lemmas, we prove that for every i, every 2-walk of H, is K-fanned and that H, does not contain any induced 4-cycle. • i Lemma 4.5. For every i, any 2-walk of H, is K-fanned. CD Proof. We proceed by induction on i. Clearly, H3 = T fulfils this property. Assume by induction hypothesis that any 2-walk of H, is K-fanned. Let v e G \ H, be an arbitrary vertex from the ball TBt(T), where t is the smallest integer such that all vertices from TBt-1(T) lie in HClearly v has at least two neighbors in HWe will prove that any o CM IN 2-walk of Hj+i = G(V(H) u {v}) is K-fanned. It suffices to consider the 2-walks Q of Hi+i that contain v, since all other 2-walks lie in Hi and are K-fanned by the induction hypothesis. Case 1. Q = (a,v,c). Since Hi is connected and a,c e V(Hi), there exists an (a,c)-walk R in Hi. Since any 2-walk of Hi is K-fanned by induction hypothesis, R itself is K-fanned. As Hi is a subgraph of K, R belongs to K. Among all K-fanned (a, c)-walks belonging to K and avoiding v, let W — (a = xo,xi,... ,xm = c) be chosen in such a way that the distance sum D(W) = EXieW d(v,xi) is minimized. By Lemma 4.4, v ~ W and thus the 2-walk Q is K-fanned. Case 2. Q = (c, b, v). If c and v are adjacent, then Q is trivially fanned. Thus we may assume that c f v, and c ^ v as v ^ Hi. Since v has at least two neighbors in Hi, there exists a vertex a e Hi adjacent to v and different from b. Since Hi is 2-connected and a, c e Hi, there exists an (a, c)-walk P0 in Hi that avoids b. The walks P0 and (P0, b) are K-fanned because all their 2-walks are fanned by induction hypothesis. Hence, there exists at least one K-fanned (a, b)-walk (P0,b) that passes via c, avoids v, and all vertices of P0 are different from b. Among all such (a, b)-walks (P0,b) of K (i.e., that pass c, avoid v, the vertices of P0 are different from b, and are K-fanned), let W = (a = x0,xi,... ,xm,xm+i = c, b) be chosen in such a way that D(W) is minimized. Since v and xm+i — c are different and not adjacent, k — max{dG(xi,v) : xi e W} > 2. Let j be the smallest index such that d(xj,v) — k. First suppose that j ^ m + 1. By Lemma 4.4, the vertices a and b can be connected by one of the walks W', W'', W''' derived from W. These walks are K-fanned, contain the 00 vertex c, avoid the vertex v, and all three have smaller distance sums than W. In case of W' and W'' we obtain a contradiction with the minimality choice of W. Analogously, in case of W"' we obtain the same contradiction except if the vertex y coincides with b, i.e., b is adjacent to the vertices xj-i,xj, and xj+i. In this case, d(xj,v) — 2 and xj-i ~ v. CO Consider the 2-walk (c, b,xj+i). By construction, we know that there is a K-fanned walk R — (x m+i — c,xTO,...,xj+2,xj+i) that avoids b. Applying Lemma 4.4 with b and R, there exists a K-fanned (c,xj+i )-walk R' avoiding b such that b ~ R'. Consequently, there is an walk (R' , x j, x j—i, v) in K from c to v in the neighborhood of b and thus (c, b, v) is K-fanned. Now suppose that j — m +1, i.e., v is adjacent to all vertices of W except xm+i — c. From the choice of W we conclude that b + xm. If b f xm, then C — (v, xm, c, b, v) is an induced 4-cycle. Since the 2-path (b, c,xm) is K-fanned, we obtain a contradiction with Lemma 4.3. Finally, if b is adjacent to xm, then the 2-path (c, b, v) is K-fanned because c and v are connected in K by the 2-path (c,xm,v) and xm is adjacent to b. □ CD O CM i CM CM Lemma 4.6. Any Hi does not contain induced 4-cycles. CD Proof. Again we proceed by induction on i. Suppose by induction hypothesis that Hi does not contain induced 4-cycles. Let Hi+i — G(V(Hi)u{v}) and suppose by way of contradiction that Hi+i contains an induced 4-cycle C. Then necessarily v belongs to C. Let C — (v,a,b,c,v). Since by Lemma 4.5 the 2-walks of Hi+i are K-fanned, the 2-path (a, b, c) of C is fanned and o CM 5H G o CM i CO CO $H a CD U we obtain a contradiction with Lemma 4.3. This shows that any Hi does not contain induced 4-cycle. □ Lemma 4.7. K is the gated hull of T in G. Proof. Note that it is clear by the construction that all the vertices of K belong to the gated hull of T. On the other hand, since G is weakly modular graph, we also deduce that K is gated, by noting that it is A-closed and locally convex (i.e., if x,y e K and 0 < d(x,y) < 2, then any common neighbor v of x and y also belongs to K) [4]. Indeed, if there is a vertex u that has at least two neighbors v,w in K then there exists t such that v,w e TBt and thus u e TBt+i. Hence all vertices not in K have at most one neighbor in K. □ IN Summarizing, we obtain the main result of this subsection. i—l Proposition 4.8. Let G be a locally finite weakly modular graph not containing induced W4 and W-. Then the gated hull of any triangle T of G is a 2-connected weakly bridged graph. Additionally, if G does not contain induced W5, then the gated hull of T is a 2-connected bridged graph. Proof. By Lemma 4.7, the gated hull of T is the 2-connected subgraph K of G constructed by our procedure. Since K is a convex subgraph of a weakly modular graph G, K itself is a weakly modular graph. By Lemma 4.6, the graph K does not contain induced 4-cycles, thus K is weakly bridged by [20, Theorem 3.1(iv)]. If, additionally, G does not contain 5-wheels. then G does not contain induced 5-cycles because in a weakly bridged graph any 5-cycle is 00 included in a 5-wheel. Then K is a weakly modular graph without induced 4- and 5-cycles, thus K is bridged by [19, Theorem 8.1(ii)]. □ 4.2. Proof of Theorem 2. We first prove the implications (i)^(ii). First, bridged and weakly bridged graphs are weakly modular. Weakly bridged graphs do not contain induced K2,3, W4, and W- because they do not contain induced 4-cycles. Bridged graphs additionally do not contain induced W5. Weakly modular graphs are closed by taking (weak) Cartesian products (this holds also when there are infinite number of factors in weak Cartesian products, since the distances between vertices in a weak Cartesian product are finite). If a (weak) Cartesian product □i€iHi contains an induced K2,3,W4,W5 or W4-, then necessarily this graph occurs in one of the factors Hi. As a consequence, Cartesian products H = □is/Hi of weakly bridged graphs do not contain induced K2,3,W4, and W4-. Analogously, Cartesian products H = □is/Hi of bridged graphs do not contain induced K2,3, W4, W- and W5. If G is a retract of H, then G is an isometric subgraph of H, and therefore G does not contain induced K2,3, W4, W- in the first case and induced K2,3, W4, W4- and W5 in the second case. It remains to notice that the triangle and quadrangle conditions are preserved by retractions, thus G is a weakly modular graph, establishing that (i)^(ii). Now suppose that G is a weakly modular graph satisfying the condition (ii) of Theorem 2. Then G is a pre-median graph. By [14, Theorem 4.13], any pre-median graph is fiber-complemented. By [14, Lemma 4.8], this implies that any gated subgraph H of G is IN elementary if and only if it is prime. Note that the gated hull of any edge in G is either the edge itself, or it is included in a triangle by weak modularity, and by Proposition 4.8 we find that the gated hull of this edge is a 2-connected (weakly) bridged graph. Hence every elementary (= prime) graph is a 2-connected (weakly) bridged graph or an edge. This establishes the implication (ii)^(iii). To prove the implication (iii)^(i), we will use [15, Theorem 3.2.1] and [20, Theorem 5.1]. By Chastand [15, Theorem 3.2.1], any fiber-complemented graph G whose primes are moorable graphs is a retract of the Cartesian product of its primes. Note that elementary subgraphs of G, enjoying (iii), are edges and 2-connected weakly bridged graphs. To see this implication, we thus need to prove that weakly bridged graphs are moorable. Recall that given a vertex u of a graph G, an endomorphism f of G is a mooring of G onto u if f (u) = u and for any vertex v t u, vf (v) is an edge of G such that f (v) lie on a shortest path between v and u. A graph G is moorable if, for every vertex u of G, there exists a mooring of G onto u. Equivalently, mooring can be viewed as a combing property of graphs which comes from the geometric theory of groups [22]. Let u be a distinguished vertex ("base point") of a graph G. Two shortest paths P(x,u),P(y,u) in G connecting two adjacent vertices x,y to u are called 1-fellow travelers if d(x',y') < 1 holds for each pair of vertices x' e P(x,u),y' e P(y,u) with d(x,x') = d(y,y'). A geodesic 1-combing of G with respect to the base point u comprises shortest paths P(x,u) between u and all vertices x such that P(x,u) and P(y,u) are 1-fellow travelers for any edge xy of G. One can select the combing paths so that their union is a spanning tree Tu of G that is rooted at u and preserves the distances from u to all vertices. CM The neighbor f (x) of x t u in the unique path of Tb connecting x with the root will be called the father of x (set also f (u) = u). Then f is a mooring of G onto u (vice-versa, any mooring of G onto u can be viewed as a geodesic 1-combing with respect to u). A geodesic 1-combing of G with respect to u thus amounts to a tree Tu preserving the distances to the root b such that if x and y are adjacent in G then f (x) and f (y) either coincide or are adjacent in G. CO In [16,19] it is noticed (using [18]) that for bridged graphs every spanning tree returned by Breadth-First-Search starting from an arbitrary vertex u provides a geodesic 1-combing. More generally, it is shown in [20, Theorem 5.1] that for weakly bridged graphs every spanning tree returned by Lexicographic-Breadth-First-Search starting from an arbitrary vertex u provides a geodesic 1-combing, thus showing that weakly bridged graphs are also moorable. Thus, by [15, Theorem 3.2.1] G is a retract of the Cartesian product of its primes, establishing the implication (iii)^(i) of Theorem 2. Now, for finite graphs we show that (iv) ^^ (ii). As noticed above, bridged and weakly bridged graphs are weakly modular and do not contain induced K2,3, W4, and W4 . Bridged graphs additionally do not contain induced W5. Weakly modular graphs are closed by Cartesian products and gated amalgams. Moreover, if G is the Cartesian product or the gated amalgam of two graphs Gi and G2, then G contains an induced K2,3 (resp. W4, W4,W5) if and only if G1 or G2 does. Therefore (iv)^(ii). Conversely, suppose that G is a finite weakly modular graph satisfying the condition (ii) of Theorem 2. Then G is a pre-median graph. By [14, Theorem 4.13], any pre-median graph is fiber-complemented. Then according a o CM 00 CM CM CO CD $H CD o CM IN o CM i CM CM m u a CD U to [14, Theorem 5.4], G can be obtained from Cartesian products of elementary (=prime) graphs by a sequence of gated amalgamations. By Proposition 4.8, any elementary graph is either an edge, a 2-connected bridged graph, or a 2-connected weakly bridged graph. Thus the implication (ii)^(iv) in Theorem 2 holds. This concludes the proof of Theorem 2. 4.3. Proof of Proposition 3.1. Let G be a locally-finite bucolic graph and let Hi (i e I) be the prime graphs of G so that G is (isometrically) embedded in the (weak) Cartesian product H = □is/Hi as a retract. Note that by Theorem 2 each Hi is a weakly bridged graph. For each index i e I, let Si denote the projection of S in Hi, i.e., Si consists of all vertices vi of ^ Hi for each of which there exists a vertex v of G whose ith coordinate is vi. Since the set S is finite and the distance between any two vertices of S is finite, there exists a finite subset of indices I' of I such that for any i e I \ I', all vertices of S have the same projection in Hi, i.e., for all but a finite set I' of indices i the set Si is a single vertex. Note that each Hi is locally-finite since it is isomorphic to a gated subgraph of G. Since each set Si is finite, it is included in a ball, which is necessarily finite. Since the balls in weakly bridged graphs are convex, we conclude that for each Si, the convex hull convHi(Si) of Si in Hi is finite. The convex hull convH(S) of S in H is the Cartesian product of the convex hulls of the sets convHi(Si): convH(S) = □is/convHi(Si) (this equality holds for products of arbitrary metric spaces). All convHi(Si) for i e I \ I' are singletons, thus the size of convH(S) equals the size of □is/'convHi(Si), and thus is finite because I' is finite and each factor convHi(Si) in this product is finite by what has been shown above. Now, set A := V n convH (S). We claim that the set A is convex. Let x,y e A and pick 00 any vertex z of G in the interval I(x,y) of G. Since G is isometrically embedded in H, dG(x,y) = dH(x,y),dG(x,z) = dH(x,z), and dG(z,y) = dH(z,y), thus z also belongs to the interval between x and y in H, hence z belongs to convH (S), establishing that z belongs to A. Hence A is indeed convex in G. Since the set A is finite and it contains the set S, the convex hull of S in G is necessarily included in A, thus this convex hull is finite. This concludes the proof of Proposition 1. HH 5. Proof of Theorem 1 5.1. Auxiliary results. We start this section with several auxiliary properties of triangle-square flag complexes occurring in condition (ii) of Theorem 1. Throughout this and next subsections, we will denote such triangle-square complexes by X, assume that they are connected, and use the shorthand G := G(X). We denote by X(C3) and X(C4) the triangle-square complex consisting of a single triangle and a single square, respectively. Let X(H) = X(C3 + C4) be the complex consisting of a triangle and a square sharing one edge; its graph is the house H and with some abuse of notation, we call the complex itself a house. The twin-house X(2H) is the complex consisting of two triangles and two squares, which can be viewed as two houses glued along two incident edges or as a domino and a kite glued along two incident edges (for an illustration, see Fig. 4, left). Let also X(Wk) and X(W^) be the triangle-square complexes whose underlying graphs are Wk and W— the first consists of k triangles and the o u CD IN 0 o 1 CO ^ CO CO CO CD $H CD CO $H a CD Jh Figure 4. On the left, a twin-house (in black) included in a double prism (Lemma 5.2). On the right, a double house (in black) included in a prism (Lemma 5.3). second consists of k - 2 triangles and one square. The complex X(CW3) consists of three squares sharing a vertex and pairwise sharing edges (its graph is the cogwheel CW3). The triangular prism X(Pr) = X(C3 x K2) consists of the surface complex of the 3-dimensional triangular prism (two disjoint triangles and three squares pairwise sharing an edge). The double prism X(2Pr) consists of two prisms X(Pr) sharing a square (See Fig. 4, left). Finally, the double-house X(H + C4) = X(2C4 + C3) is the complex consisting of two squares and a triangle, which can be viewed as a house plus a square sharing with the house two incident edges, one from the square and another from the triangle (see Fig. 4, right). In the following results, we use the notation G = G(X). Lemma 5.1. If X is a triangle-square flag complex, then its 1-skeleton G does not contain induced K2,3 and W-. Proof. If G contains K2,3 or W-, then, since X is a flag complex, we will obtain two squares intersecting in two edges, which is impossible. □ Lemma 5.2. If X satisfies the house condition, then any twin-house X(2H) of X is included in X in a double prism X(2Pr). Proof. Let u,v,w,x\,x2 be the vertices of one house and u,v,w,y\,y2 be the vertices of another house, where the edge uv is common to the two squares uvx2x\ and uvy2y\, and where the edge vw is common to the two triangles vwx2 and vwy2. By the house condition, there exists a vertex a adjacent in G to x\,u,w that is not adjacent to x2, v. Analogously, there exists a vertex b adjacent to u,yi,w that is not adjacent to y2,v. If a t b, the graph induced by a,b,u,v,w is either K2,3 if a + b, or W- otherwise; in both cases, we get a contradiction with Lemma 5.1. Thus a = b, and since a + v,x2,y2, the vertices a,u,v,w,xl,x2,yl,y2 induce a double prism. □ Lemma 5.3. If X satisfies the house condition, then any double-house X(H + C4) in X is included in a prism X(Pr), i.e., G does not contain an induced double-house H + C4. Proof. Suppose by contradiction that G contains an induced double house having x, y, u, v, w, z as the set of vertices, where uvw is a triangle and xyvu and xuwz are two squares of this house. By house condition, there exists a vertex a different from z (since y + z) that is adjacent to x, y, w and that is not adjacent to u, v. Thus, the vertices z, a, w, u, x induce either K2,3 if a + z or W- otherwise. In both cases, we get a contradiction with Lemma 5.1. □ rO CD Lemma 5.4. If X satisfies the house condition and does not contain X(W4), then X does not contain X(Wj) for any k > 5. Proof. Suppose by way of contradiction that X contains X(Wj), where k is the smallest value for which this subcomplex exists. Since, by Lemma 5.1, G does not contain W4_, necessarily k > 5. Denote the vertices of X(W^) by q,x1,x2,... ,xk where x1,x2,... ,xk induce a cycle and where q is adjacent to x1,... ,xj_1 but not to xk. By the house condition applied to the house induced by q,xj_1,xj,x1,x2, there exists p in G such that p ~ xj_1,xj,x2 and p + q,x1. If p ~ x3, then the vertices x3,p,x2,q,xj_1 induce W4 if x3 ~ xj_1 (i.e., if k = 5), or W4 otherwise; in both cases, we get a contradiction. Thus p + x3. Let j be the smallest index greater than 3 such that p ~ xj. Since p ~ xj_1, j is well-defined. But then, the vertices q,p,x2,... ,xj induce Wj with j < k, contradicting the choice of k. □ 5.2. Construction of the universal cover and weak modularity. To prove the implication (ii)^(iii) of Theorem 1, from now on, we suppose that X is a connected (but not necessarily simply connected) triangle-square flag complex satisfying the (W4, W5), the house, and the cube conditions. Following the proof of Osajda [32, Theorem 4.5], we will construct the universal cover X of X as an increasing union Ui>1 Xi of triangle-square complexes. The complexes Xi are in fact spanned by concentric combinatorial balls BU in X. The covering map f is then the union Ui>1 fi, where fi : Xi ^ X is a locally injective cellular map such that fi\xx. = fj, for every j < i. We denote by Gi = G(Xi) the underlying graph of XXi. We denote by SU the set of vertices BU \ -Bi_1. Pick any vertex v of X as the basepoint. Define !X>0 = {U} := (v},i?1 := B1(v,G), and f1 :=IdBl(v G). Let X1 be the triangle-square complex spanned by B1(v,G). Assume that, for CM i > 1, we have constructed the sets B1,... BU, and we have defined the triangle-square complexes XX1,... XXi and the corresponding cellular maps f1,..., fi from XX1,... XXi, respectively, to X so that the graph Gi = G(XXi) and the complex XXi satisfies the following conditions: (Pi) BjCu,Gi) = Bj for any j < i; (Qi) Gi is weakly modular with respect to UU (i.e., Gi satisfies the conditions TC(U) and (Ri) for any U e B3i_1, fi defines an isomorphism between the subgraph of Gi induced by B1(u, and the subgraph of G induced by B1(fi(il), G); (Si) for any W,W' e B?i_1 such that the vertices w = fi(wo),w' = fi(wo') belong to a square ww'uu' of X, there exist u, u' e BU such that fi(ul) = u, f (u') = u' and WuWiU'Uuu' is a square of XXi. (Ti) for any W e Si := B s -Bi-1, fi defines an isomorphism between the subgraphs of Gi and of G induced by B^W, Gi) and fi(B1 (Wu, Gui)). u u u It can be easily checked that BX>1,G1 , X and f1 satisfy the conditions (P1),(Q1),(R1),(S1), and (T1). Now we construct the set -Bi+1, the graph G^ having Bui+1 as the vertex-set, the triangle-square complex XXi+1 having G^ as its 1-skeleton, and the map fi+1 : XXi+1 ^ X. Let r u a CD U Z = {(W,z) : W e Si and z e B1(fi(WU),G) s fi(B1(W;,Gi))}. i-H o ft IN CSI CSI s CO CO CO Jh a CD U On Z we define a binary relation = by setting (w, z) = (w', z') if and only if z = z' and one of the following two conditions is satisfied: (Z1) w and w' are the same or adjacent in Gi and z e Bi(fi(w),G) n Bi(fi(w'),G); (Z2) there exists û e I3i-i adjacent in Gi to w and w' and such that fi(û)fi(w)zfi(w') is a square-cell of X. Lemma 5.5. The relation = is an equivalence relation on Z. Proof. For any vertex w e Bi, we will denote by w = fi(wS) its image in X under /¿. Since the binary relation = is reflexive and symmetric, it suffices to show that = is transitive. Let (w,z) = (w',z') and (w',z') = (w'',z''). We will prove that (w,z) = (w" ,z''). By definition of =, we conclude that z = z ' = z''. By definition of =, z e B\(w, G) n B\(w', G) n B\(w'', G). If w ~ w'' (in Gi), then by definition of =, (w, z) = (w'', z) and we are done. If w + w'' and if there exists u e Bi-i such that u ~ w,w'', then by (Ri) applied to u, we obtain that u ~ w,w'' and w + w". Since (w,z), (w'',z) e Z, we have z ~ w,w''. Moreover, if z ~ u, then by (Ri) applied to u, there exists Ue B^ such that U~ u,w,w'' and fi('z) = z. Thus (w,z), (w',z) Z, which is a contradiction. Consequently, if w + wz" and if there exists u e Bi-\ such that u ~ w,w'' and fi(ii) = u, then uwzw'' is an induced square in G, and by condition (Z2), we are done. Therefore, in the rest of the proof, we will assume the following: (Ai) w + w''; (A2) there is no u e Si-i such that u ~ w,w i Claim 1. For any couple (w,z) e Z the following properties hold: 00 (A3) there is no neighbor u e Bi-i of w such that fi(u) = z; (A4) there is no neighbor u e I3i-1 of w such that u ~ z; (A5) there are no x,y e Bi-1 such that u ~ w,y and y ~ z. Proof. If w has a neighbor Je Bi-\ such that fiÇz) = z, then (w,z) i Z, a contradiction. This establishes (A3). If w has a neighbor zZ e Bi-\ such that u ~ z, then by (Ri) applied to ZZ, there exists zZ e B3i such that ZZ~ u,w. Thus (w,z) i Z, a contradiction, establishing (A4). If there exist x,y e B^i such that xz ~ w,y and y ~ z, then yxwz is an induced square in G. From (Si) applied to y,x, there exists Z e B-i such that Z~ y,w and fj,(z) = z. Thus (w, z) i Z, a contradiction, and therefore (A5) holds as well. □ We distinguish three cases depending of which of the conditions (Z1) or (Z2) are satisfied by the pairs (w,z) = (w',z') and (w',z') = (w'',z''). Case 1: w' is adjacent in Gi to both w and w". By (Qi), the graph Gi satisfies the triangle condition TC(Z), thus there exist two vertices u,u' e Si-i such that ZZ is adjacent to w,w' and ZZ' is adjacent to w',w''. By (A2), u + w'', xZ + w, UZ + Z'. If ZZ ~ UZ', then by (Ti) applied to w' and by (A3)&(A4), the vertices u,u',w,w',w'', z induce W5 in G. By TC(ZZ), there exists XZ e Si-2 such that ZZ ~ u,u'. By (Ri) applied to ZZ and ZZ', we get x £ {u,u',w,w',w''} and x ^ u, u . From (A4)&(A5), we get x t z and x f z. Since G satisfies the IF5-wheel condition, there exists a vertex y of G adjacent to x,u,u',w,w',w'', z. By (Ri) applied to u, there exists y ~ w,u, u and thus y e Bi_i, contradicting the property Suppose now that u f u'. Then i > 2 and by QC(v), there exists u e Si-2 such that ff ^ u, ff . From (A4)&(A5), x ^ z and x f z. Consequently, z,w,w', w'',u,u',x induce a W6 , 2 5H contradicting Lemma 5.4. CD IN Case 2: w and w ' are adjacent in Gi, and there exists u' e Bi_1 adjacent to w ' and w '' such that u'w'w''z is a square-cell of X. By (A1)&(A2), w f w'' and u' f w. By triangle condition TC(v) for Gj, there exists a vertex u e Bi-1 different from u' and adjacent to W and w'. By (A3)&(A4), u t z and u f z. By (A2), u f W''. If u ~ u', by (Tj) applied to w', z,w,w',u,u',w'' induce a W5-, contradicting Lemma 5.4. Thus u f u'. By quadrangle condition QC(v) for Gj, there exists a vertex x e Sj-2 adjacent to u and u'. From (A4)&(A5), x t z and x f z. By (Tj) applied to w' and by (Rj) applied ^ to u', we get that z,w,w',w'',u,u',x induce a twin-house. By Lemma 5.2 there exists y in G such that y ~ w,w'',u',x and y f u, z. By (Rj) applied to u', there exists y e Bj such that u ~ u',w '',u. By (Sj) applied to u,u and to the square uxyw, we get u ~ w. Consequently, u e Sj-1, u ~ w, w'', contradicting (A2). Case 3: There exist u,u' e Bi_1 such that the vertex u is adjacent in Gi to w,w ', the vertex u' is adjacent to w', w'', and uwzw' and u'w'zw'' are square-cells of X. 00 From (A1 )&(A2), w f w '', u t u', u f w '', and u' f w. From (A3), u t z t u' and z f u,u'. csr If u ~ u', by (Ti) applied to w' and by (Ri) applied to u,u', the vertices z,w,w',w'',u,u' induce a double-house, which is impossible from Lemma 5.3. Thus u f u'. By QC(v), there exists u e Si-2 such that u ~ u,u'. By (A4)&(A5), x t z and x f z. By (Ti) applied to w' and by (Ri) applied to u,u', the vertices z,w,w',w'',u,u',x induce CW3. Thus, by the cube condition, there exists a vertex y of G such that y ~ x,w,w'' and y f z,w',u,u'. By (Ri) applied to x, there is u e Bi such that u ~ u. By (Si) applied to and to the square uxyw, we have u~ w. By (Si) applied to u',^ and to the square u'xyw'', we get u~ w''. Consequently, u e Si_1, u ~ w, w'', contradicting (A2). □ Let Si+1 denote the equivalence classes of =, i.e., Si+1 = Z/=. For a couple (w, z) e Z, we will denote by [w, z] the equivalence class of = containing (w, z). Set Bi+1 := Bi u Si+1. Let Gi+1 be the graph having Bi+1 as the vertex set in which two vertices a, b are adjacent if and only if one of the following conditions holds: (1) a, b e Bi and ab is an edge of Gi, (2) a eBi;b e Si+1 and b = [a, z], (3) a, b e Si+1, a = [w, z], b = [w, z'] for a vertex w e Bi, and z ~ z' in the graph G. Finally, we define the map /i+1 : Bi+1 ^ V(X) in the following way: if a e Bi, then /i+1(a) = /i(a), otherwise, if a e Si+1 and a = [w,z], then /i+1(a) = z. Notice that /i+1 is well-defined because all couples from the equivalence class represented by a have one and the same vertex z in the second argument. In the sequel, all vertices of Bi+i will be denoted with a tilde and their images in G under /i+i will be denoted without tilde, e.g. if w e Bi+i, then w — /j+i(w). Lemma 5.6. Gi+i satisfies the property (Pi+i), i.e., Bj(v,Gi+i) — Bj for any j < i + 1. Proof. By definition of edges of Gi+i, any vertex b of Si+i is adjacent to at least one vertex of Bi and all such neighbors of b are vertices of the form w e Bi such that b — [w, z] for a couple (w, z) of Z. By definition of Z, w e Si, whence any vertex of Si+i is adjacent only to vertices of Si and Si+i. Therefore, the distance between the basepoint v and any vertex a e Bi is the same in the graphs Gi and Gi+i. On the other hand, the distance in Gi+i between v and any vertex b of Si+i is i + 1. This shows that indeed Bj(v, Gi+i) — Bj for any j < i + 1. □ IN o CM 00 CM CM Lemma 5.7. Gi+i satisfies the property (Qi+i), i.e., the graph Gi+i is weakly modular with respect to the basepoint v. Proof. First we show that Gi+i satisfies the triangle condition TC(v). Pick two adjacent vertices x, y having in Gj+i the same distance to y. Since by Lemma 5.6, Gj+i satisfies the property (Pi+i) and the graph Gi is weakly modular with respect to v, we can suppose that x,y e Si+i. From the definition of the edges of Gi+i, there exist two couples (w,z), (w, z') e Z such that w e Bi, z is adjacent to z' in G, and x — [w,z],y — [w, z']. Since w is adjacent in Gi+i to both x and y, the triangle condition TC(v) is established. CM Now we show that Gi+i satisfies the quadrangle condition QC(v). Since the properties (Pi+i) and (Qi) hold, it suffices to consider a vertex x e Si+i having two nonadjacent neighbors w, w' in Si. By definition of Gi+i, there exists a vertex z of X and couples (w, z), (w', z) e Z such that x — [w,z] and x — [w',z]. Hence (w,z) = (w',z). Since w and w' are not adjacent, by condition (Z2) in the definition of = there exists u e Bi—i adjacent to w and w', whence x, w, w' satisfy QC(v). □ CO We first prove that the mapping /i+i is a graph homomorphism (preserving edges) from Gi+i to G. In particular, this implies that two adjacent vertices of Gi+i are mapped in G to different vertices. [V ~ ~ Lemma 5.8. /i+i is a graph homomorphism from Gi+i to G, i.e., for any edge ab of Gi+i, ab is an edge of G. Proof. Consider an edge ab of Gi+i. If a, b e Bi, the lemma holds by (Ri) or (Ti) applied to a. Suppose that a e Si+i. If b e Bi, then a — [b,a], and ab is an edge of G. If b e Bi+i, then the fact that a and b are adjacent implies that there exists a vertex w e Bi such that a — [w, a], b — [w, b] and such that a ~ b in G. □ We now prove that /i+i is locally surjective for any vertex in Bi. Lemma 5.9. If a e Bi and if b ~ a in G, then there exists a vertex b of Gi+i adjacent to a such that /i+i(b) — b. ft Cu o CM si W u a CD U Proof. If a e Bi-1, the lemma holds by (R^). Suppose that a e S and consider b ~ a in G. If a has a neighbor b e Bj mapped to b by f, we are done. Otherwise (a, b) e Z, [a, b] ~ a in Gi+1 and [a, b] is mapped to b by fi+1. □ Before proving the local injectivity of fi+1, we formulate a technical lemma. Lemma 5.10. Let (w,a), (w',a) e Z be such that (iff, a) = (iff', a). If (w,b) e Z and b ~ w' in G, then w ~ w', (w', b) e Z and (w, b) = (w', b). Proof. First suppose that w f w'. Since (w,a) = (w',a), there exists of e Si_1 such that f ~ wo, wf' and wxw'a is an induced square in G. In G, b ~ w,w', thus b, w,x,a,w' induce K2,3 if b f a,x, W4 if b ~ a,x, or W4 otherwise. In any case, we get a contradiction. Suppose now that w ~ w'. If (wf', b) £ Z, then there exists b e Bj such that b ~ w' and fj(b) = b. In G, wbw' is a triangle, thus b ~ w by condition (Rj) applied to b. This implies that (w, b) £ Z. Consequently, (wf, b), (wf', b) e Z and (wf, b) = (wf', b) since w ~ w'. □ We can now prove that fi+1 is locally injective. Lemma 5.11. If a e Bi+1 and b,C are distinct neighbors of a in Gi+1, then b t c. Proof. First note that if b ~ C, the assertion holds by Lemma 5.8; in the following we assume that b + C. If a, b,Ce Bj, the lemma holds by (Rj) or (Tj) applied to a. Suppose first that a e Bj. If b,Ce Sj+1, then b = [a, b] and C = [a, c], and thus b t c. If b e Bj and C = [a, c] e Sj+1, then (a, b) £ Z, and thus c t b. Thus, let a e Sj+1. If b,c e Bj and a e Sj+1, then a = [b, a] = [c, a]. Since (b, a) = (c, a) and since b -f c, there exists w e Bj_1 such that w ~ b,c and abwc is an induced square of G. This implies that b t c. If a, b,ce Sj+1, then there exist w, w' e Bj such that b = [wf, b], c = [w', c], and a = [wf, a] = CM [w ',a]. If b = c, then [w,b] = [w ',b] = [w ',c] by Lemma 5.10, and thus b = c, which is impossible. If a, b e Sj+1 and ce Sj, then there exists w e Sj such that b = [wf, b] and a = [wf, a] = [c, a]. If w ~ c, then (wff, c) £ Z and thus, (w, c) t (w, b), i.e., b t c. If w f c, since [w, a] = [c, a], there exists f e Sj_1 such that f ~ wff,c and such that acxw is an induced square of G. Since w and care not adjacent, by (Rj) applied to x, w and c are not adjacent as well. Since w ~ b, this implies that b t c. □ Lemma 5.12. If a ~ b, c in Gj+1, then b ~ c if and only if b ~ c. Proof. By Lemma 5.11, b t c. If a, b,ce Bj, then the lemma holds by condition (Rj) applied to a. Note that from Lemma 5.8, if b ~ c, then b ~ c. Suppose now that b ~ c in G. Suppose that a e Bj. If b,ce Sj+1, b = [a, b] and c = [a, c]. Since b ~ c, by construction, we have b ~ c in Gj+1. Suppose now that b = [a, b] e Sj+1 and c e Bj. If there exists b' ~ c in Gj such that fj(b') = b, then by (Rj) applied to c, a ~ b' and (a, b) £ Z, which is a contradiction. Thus (c, b) e Z and since c ~ a, [c, b] = [a, b] = b, and consequently, c ~ b. Therefore, let a e Sj+1. _ _ _ _ _ If b,c e Bj and a e Sj+1, then a = [b, a] = [c, a] and either b ~ c, or there exists w e Sj_1 such that w ~ b,c and wbac is an induced square in G, which is impossible because b ~ c. If a, b e Si+1 and c e Bj, then there exists w e Bj such that b = [w, b] and a = [w, a] = [c, a]. By Lemma 5.10, (c, b) e Z and b = [w, b] = [c, b]. Consequently, C~ b. If a, b,ce 5i+1, there exist w, w' e Bj such that b = [w, b], c = [w', c] and a = [w, a] = [w',a]. If w ~ cor w' ~ b, then b ~ c because b ~ c. Suppose now that w f c, w' f b From previous case applied to a, b e 5j+1 (resp. a,ce 5j+1) and w' e Bj (resp. w e Bj), it follows that w f c and w' f b. If w ~ w', then a, b, w,w', c induce W4 in G, which is impossible. Since [w, a] = [w',a], there exists x e 5j_1, such that x ~ w, w' and such that awxw' is an induced square in G. If x ~ b, then by (R) applied to x, there exists b' e Bj mapped to b by / such that b' ~ x, w and thus (w, b) ^ Z, which is a contradiction. Using the same arguments, we have that x f c and thus, a, b, c,w',x,w induce W5- in G, which is impossible. □ We can now prove that the image under fj+1 of an induced triangle or square is an induced triangle or square. Lemma 5.13. If abc is a triangle in Gj+1, then abc is a triangle in G. If abcd is an induced .—■ .—■ square of Gj+1, then abcd is an induced square in G. In particular, the graph Gj+1 does not contain induced K2,3 and W-. Proof. For triangles, the assertion follows directly from Lemma 5.8. Consider now a square abcd. From Lemmas 5.8 and 5.11, the vertices a, b, c, and d are pairwise distinct and a ~ b, b ~ c, c ~ d, d ~ a. From Lemma 5.12, a f c and b f d. Consequently, abcd is an induced square in G. Now, if Gj+1 contains an induced K2,3 or W4, from the first assertion and Lemma 5.12 we conclude that the image under fj+1 of this subgraph will be an induced K2,3 or W,- in the graph G, a contradiction. □ The second assertion of Lemma 5.13 implies that replacing all 3-cycles and all induced 4-cycles of Gj+1 by triangle- and square-cells, we will obtain a triangle-square flag complex, which we denote by Xj+1. Then obviously Gj+1 = G(Xj+1). The first assertion of Lemma 5.13 implies that fj+1 can be extended to a cellular map from Xj+1 to X: fj+1 maps a triangle abc to the triangle abc of X and a square abcd to the square abcd of X. Lemma 5.14. fj+1 satisfies the conditions (Rj+1) and (Tj+1). Proof. From Lemmas 5.11 and 5.12, we know that for any w e Bj+1, fj+1 induces an isomorphism between the subgraph of Gj+1 induced by B1(w, Gj+1) and the subgraph of G induced by /j+1(B1(w,Gj+1)). Consequently, the condition (Tj+1) holds. From Lemma 5.9, we know that /j+1(B1(w, Gj+1)) = B1(w,G) and consequently (Rj+1) holds as well. □ Lemma 5.15. For any w,w' e Bj such that the vertices w = /j+1(w),w' = /j+1(w') belong to a square ww'u'u of X, there exist u, u' e Bj+1 such that /j+1 (u) = u, /j+1 (u') = u' and ww'u'x is a square of Xj+1, i.e., Xj+1 satisfies the property (Sj+1). Proof. Note that if w, w' e Bj_1, the lemma holds by condition (Sj). Let us assume further that w e Sj. By Lemma 5.14 applied to w and w', we know that in Gj+1 there exist u,u' such that x ~ w and u' ~ w'. CD ■ 1 J-H CD o CM rO CD CD m u a CD u Case 1. w' e Si- If u' e Bi-1, by (S,) applied to w' and uS, we conclude that ww'u'u is a square in Gi+1. If u' e Si and S e Si-1, then Lemma 5.14 applied to w, implies that S is not adjacent to w'. Thus, by quadrangle condition QC(u), there exists S e Si-2 such that S - u,w'. Hence, w,w',u,u',x induce in G a forbidden K2,3,W-, or W4, which is impossible. Suppose now that u',u e Si. By TC(u), there exists S e Si-1 different from w' such that S - S, W. Since G does not contain W- or W4, x + u',w' and the vertices u,w,w',u',x induce a house. By the house condition there exists y in G such that y - x,u',w' and y + u,w. Since x + w', by R, applied to w, x + w'. Applying QC(v), there exists Se Si-2 such that S- a,iu' and S + w. Since S e Si-2, S + u' and thus by Ri+1 applied to w', z + u'. Consequently, z t y. Thus, from Lemma 5.13, xzw'w is an induced square of G and y,x,z,w',w induce a K2,3 if z + y and W- otherwise, which is impossible. Note that if u' has a neighbor u2 in B, mapped to u , then, exchanging the roles of u' and w, we also get a contradiction. Suppose now that neither w nor u' has a neighbor in B, mapped to u. Thus, (w,u), (u',u) e Z and since w' e Si-1 is adjacent to w and u', (w,u) = (u',u). Consequently, ww'u'[w,u] is a square of Gi+1 which is mapped by fi+1 to the square ww'u'u. Case 2. w' e Si. If u e Si-1 or u' e Si-1, then, exchanging the roles of w,w',u and u', we are in the previous case. If u e Si, by TC(S) there exists S e Bi-1 such that S - w,u. Thus, in G there exists x - u,w CO and, since G does not contain W4 or W4 , x + u',w'. Applying the house condition, we get y CM in G such that y - u',w',x and y + u,w. Applying the previous case to w,u and the square wxyw' of G, we know that there exists S e B, such that wtSw' is an induced square in Gi+1. From Lemma 5.14 applied to w', we deduce that S- u'. Applying (S,) to x,y and to the square xyu'u, we get that u - u', thus ww'u'u is a square in Gi+1. If u' e Si, then exchanging the roles of w,w',u,u' we also get that ww'u'u is a square in Gi+1. Suppose now that w has no neighbor in B, mapped to u and that w' has no neighbor in B, mapped to u'. Thus, there exist [w,u] and [w',u'] in Si+1. By TC(S), there exists S e Si-1 such that S - w, w'. In G, x - w, w' and x + u,u' since G does not contain W- or W4. Applying the house condition, there is a vertex y in G such that y - u,u' and y + w,w'. By (R,) applied to S, there exists S in B, such that S- x and S + w,w'. If Shas a neighbor in B, HH ~ ~ mapped to u, then applying the previous case to w,u and the square wxyu, we conclude that w has a neighbor in B, mapped to u, which is impossible. Consequently, (y,u) e Z, and since there is S e Si-1 such that S - vj,i[and wxyu is an induced square in G, (S,u) = (w,u). Using the same arguments, one can show that there exists (S,u') e [w',u']. Since yuu' is a triangle in G, and since [w,u] = [S,u] and [w',u'] = \S},u'], there is an edge in Gi+1 between [w,u] and [w',u']. Consequently, ww'[w',u'][w,u] is a square of Gi+1 satisfying the lemma. □ Let Xsv denote the triangle-square complex obtained as the directed union Ui>o XQ with the vertex v of X as the basepoint. Denote by Gv the 1-skeleton of Xsv. Since each (S!i is weakly 1 u CD r i—i IN modular with respect to v, the graph Gv is also weakly modular with respect to v. Let also f = Ui>o fi be the map from Xv to X. Lemma 5.16. For any w e Xv, St(w, Xv) is isomorphic to St(w, X). Consequently, f : Xv ^ X is a covering map. Proof. In order to prove that f is a covering map from Xv to X, it is enough to prove that for any w e X , f Ist(s?x ) is an isomorphism between the stars St(wV,Xv) and St(w,X), where w = f (w). Note that, since Xv is a flag complex, a vertex V of Xv belongs to St(wv, Xv) if and only if either V e Bl(w,Gv) or V has two non-adjacent neighbors in Bl(w,Gv). Let w e Bi, i.e., i is the distance between v and w in Gv, and consider the set Bi+2. Then the vertex-set of St(w, Xv) is included in Bi+2. From (Ri+2) we know that f is an isomorphism between the graphs induced by Bl(w,Gv) and Bl(w,G). For any vertex x in St(w, X) \ Bl(w, G) there exists an induced square wuxu' in G. From (Ri+2), there exist u,u' ~ w in Gv such that V + u'. From (Si+2) applied to w,V and since w has a unique neighbor u' mapped to u', there exists a vertex V in Gv such that f (V) = x, x ~ u,u' and V + w. Consequently, f is a surjection from V(St (w, Xv)) to V(St(w, X)). Suppose by way of contradiction that there exist two distinct vertices u, u' of St(w, Xv) such that f (u) = f (u') = u. If u,u' ~ w, by condition (Ri+l) applied to w we get a contradiction. Suppose now that u ~ w and u' + w and let z ~ w,u'. This implies that w,u,z are pairwise adjacent in Gv. Since f is an isomorphism between the graphs induced by Bl(w,Gv) and Bl(w,G), we conclude that V~ u. But then f is not locally injective around V, contradicting the condition (Ri+2). Suppose now that u, u' + w. Let a, b ~ u,w and a', b' ~ u', w'. If a' = a CO or a' = b, then applying (Ri+2) to a', we get that f (u) t f (u'). Suppose now that a' £ {a, b}. Then the subgraph of G induced by a', w, a, b, u is either K2,3 if a' + a, b, or W4 if a' ~ a, b, or W- otherwise. In all cases, we get a contradiction. Hence f is a bijection between the vertex-sets of St(w, Xv) and St(w, X). By (Ri+2), a ~b in St(w, Xv) if and only if a ~ b in St(w, X). By (Ri+2) applied to w and since X and Xv are flag complexes, abw is a triangle in St(w, Xv) if and only if abw is a triangle in St(w, X). By __ -—- (Ri+2) and since X is a flag complex, if abcw is a square in St(w, X ), then abcw is a square in St(w, X). Conversely, by the conditions (Ri+2) and (Si+2) and flagness of Xv, we conclude that if abcw is a square in St(w,X), then abcw is a square in St(w,Xv). Consequently, for any w e Xv, f defines an isomorphism between St(w,Xv) and St(w,X), and thus f is a covering map. □ Lemma 5.17. Xv satisfies the house, the cube, and the W5-wheel conditions, and the graph Gv does not contain induced K2,3,W-, and W4. Moreover, if G is W5-free, then Gv is also W5-free. o CM 1 u _ Proof. Note that for any subgraph C e {house, cube, K2,3,W_ ,W-,W5} of Gv there exists a vertex w such that C is included in the star St(w, Xv) of this vertex. From Lemma 5.16, St(w , X v) is isomorphic to St(w, X), thus f(C) is isomorphic to C. Since G does not contain induced K2,3, W_, W^ the graph Gv also does not contains these graphs as induced subgraphs, and if G is W5-free, Gv is also W5-free. CO u a CD U Consider a house -u-u'w'wu in Xv where yu'w'w is a square and -uwu is a triangle. This house is mapped by f to the house uu'w'wx in X. By the house condition in X, there exists a vertex y e G such that y ~ u', w',x and y f u, w. Since f is locally bijective, there exists y ~ X such that f (y) = y. Since f is an homomorphism from St(x, Xv) to St(x, X), considering the squares xyu'u and xyw'w, we get that y ~ u',w' and y f u, w. Thus, Xv satisfies the house condition. Consider three squares xab''a', xa' 6a'', xa'' b'a in XX v. By cube condition, in G there exists a vertex y such that y ~ 6,6', 6'' and y f x,a, a',a''. Since f is locally bijective, there exists y ~ b such that f (y) = y. Since f is an isomorphism from St(6, Xv) to St(b, X), we get that y ~ b', b'' and y f a',a'',x. When considering St(b',Xv), we get that y f a. Thus, X also satisfies the cube condition. Finally suppose that X satisfies the ^5-wheel condition and consider W5 in Gv made of a 5-cycle (x1,x2,x3,x4,x5,x1) and a vertex Cadjacent to all vertices of this cycle. Suppose that there exists a vertex Xsuch that X~ x1,x2 and Xf x3,x4,x5,C. The vertices c,x1,x2,x3,x4,x5 are all distinct and they induce W5 in G. Since f is locally bijective and since x1 f x4, necessarily z $. {c,x1,x2,x3,x4,x5}. Since St(x1,Xv) is isomorphic to St(x1,X), z f x5,c. Considering St(x2,Xv), we get z f x3. If z ~ x4, x1zx4x5 is a square in St(x1,X), and this implies that X ~ x4, a contradiction. By the TU5-wheel condition for X, there exists y ~ c,z,x1 ,x2,x3,x4,x5 in G. Consider the neighbor y of C such that f(y) = y. Since St(C, Xv) is isomorphic to St(c, X), y ~ x1,x2,x3,x4,x5. Considering the star St(x1, Xv), we r conclude that y ~ X. Consequently, Xv satisfies the ^"5-wheel condition. □ CM The fact that the complex Xv is simply connected is a direct consequence of the following more general result. IN o CM 00 CM CM Lemma 5.18. Let Y be a triangle-square flag complex such that G(Y) satisfies the triangle and the quadrangle conditions TC(v) and QC(v), for some basepoint v. Then Y is simply connected. In particular, X v is simply-connected for any basepoint v e V(X). HH Proof. A loop in Y is a sequence (wi, w2,..., , w) of vertices of Y consecutively joined by edges. To prove the lemma it is enough to show that every loop Y can be freely homotoped to a constant loop v. By contradiction, let A be the set of loops in G(Y), which are not freely homotopic to v, and assume that A is non-empty. For a loop C e A let r(C) denote the maximal distance d(w,v) of a vertex w of C from the basepoint v. Clearly r(C) > 2 for any loop C e A (otherwise C would be null-homotopic). Let B ç A be the set of loops C with minimal r(C) among loops in A. Let r := r(C) for some C e B. Let D ç B be the set of loops having minimal number e of edges in the r-sphere around v, i.e. with both endpoints at distance r from v. Further, let E ç D be the set of loops with the minimal number m of vertices at distance r from v. Consider a loop C = (wi, w2,..., wk, wi) e E. We can assume without loss of generality that d(w2,v) = r. We distinguish two cases corresponding to the triangle or quadrangle condition that we apply to them. CO u a CD U Case 1: d(w^v) = r or d(w3, v) = r. Assume without loss of generality that d(w1, v) = r. Then, by the triangle condition TC(v), there exists a vertex w ~ w1, with d(w, v) = r - 1. Observe that the loop C' = (w1, w, w2,..., wk, w1) belongs to B - in Y it is freely homotopic to C by a homotopy going through the triangle ww1 w2. The number of edges of C' lying on the r-sphere around v is less than e (we removed the edge w1w2). This contradicts the choice of the number e. iH Case 2: d(w1,v) = d(w3,v) = r-1. By the quadrangle condition QC(v), there exists a vertex w ~ w1, w3 with d(w, v) = r-2. Again, the loop C' = (w1, w, w3,..., wk, w1) is freely homotopic to C (via the square w1w2w3w). Thus C' belongs to D and the number of its vertices at distance r from v is equal to m - 1. This contradicts the choice of the number m. IN o CM i CM CM m u a CD U In both cases above we get contradiction. It follows that the set A is empty and hence the lemma is proved. □ 5.3. Proof of Theorem 1. Since the hypercube condition implies the cube condition and the hyperhouse condition implies the house condition, if X is a bucolic, then its 2-skeleton X(2) satisfies (ii), thus (iWii). Using the results of previous subsection, we will show now that (ii)^(iii). Let X be a connected triangle-square flag complex satisfying the local conditions of (ii). By Lemma 5.16, f : X v ^ X is a covering map. By Lemma 5.18, Xv is simply connected, thus Xv is the universal cover X of X. Therefore the triangle-square complexes Xv , v e V(X), are all 00 universal covers of X, whence they are all isomorphic. Since for each vertex v of X, the graph Gv = G(Xv) is weakly modular with respect to the basepoint v, we conclude that the 1-skeleton G(X ) of X is weakly modular with respect to each vertex, thus G(X ) is a weakly modular graph. Since X is isomorphic to any X v, by Lemma 5.17, X satisfies the same local conditions as X. Thus X satisfies the (W^VFs), the house, and the cube conditions. If, additionally, X is simply connected, then the universal cover X is X itself. Therefore, X -—- coincides with Xv for any choice of the basepoint v e V(X). Therefore, by what has been proven above, G(X) is a weakly modular graph. This establishes the implication (ii)^(iii) of Theorem 1. Now we will establish the implication (iii)^(ii). Let X be a prism flag complex such that G := G(X) is a weakly modular graph not containing induced W4. Then G does not contain induced K2,3 and W4- because G is the 1-skeleton of a triangle-square cell complex x(2). From Lemma 5.18 we conclude that X(2) (and therefore X) is simply connected. Thus, it remains to show that X satisfies the house, the cube condition, and the W^-wheel conditions. First suppose that the triangle uvw and the square uvxy define in X a house. Then w is at distance 2 to the adjacent vertices x and y. By triangle condition, there exists a vertex w' adjacent to w,x, and y and different from u and v. If w' is adjacent to one or both of the vertices u,v, then we will get a forbidden W4 or W4 induced by u,v,x,y,w'. This establishes the house condition. IN To prove the cube condition, let xyuv, uvwz, and uytz be three squares of X pairwise intersecting in edges and all three intersecting in u. If x and w are adjacent, then the vertices v,x,w,u,y,z induce in X a double house, which is impossible by Lemma 5.3 because X satisfies the house condition. Hence x f w and analogously x f t and t f w. If x is adjacent to z, then x,y,u,t, z induce in G a forbidden K2,3. Thus x f z and analogously y f w and v f t. First suppose that d(x,z) = 2 in G. Since d(y,z) = 2, by triangle condition there exists a vertex s adjacent to x,y, and z. From what has been shown before, s t u,t, hence y,u, z,t,s induce K2,3, W_, or W4 depending of whether s is adjacent to none, one or two of the vertices u,t. Thus, d(x,z) = 3 and for the same reasons, d(y,w) = d(v,t) = 3. By quadrangle condition there exists a vertex s adjacent to x,w,t and distinct from previous vertices. Since d(x, z) = d(w, y) = d(t, v) = 3, s f z, y, v. If s is adjacent to u, then s, u, v, w, z induce a forbidden K2,3. This shows that in this case the vertices s,t,u,v,w,x,y,z define a 3-cube, establishing the cube condition. Finally, we establish the W5-wheel condition. Notice that we can suppose that X satisfies the cube and the house conditions and by Lemma 5.4 that X does not contain a X(W5_). Pick a 5-wheel defined by a 5-cycle (x1 ,x2,x3,x4,x5,x1) and a vertex c adjacent to all vertices of this cycle, and suppose that xo is a vertex adjacent to x1 and x5 and not adjacent to remaining vertices of this 5-wheel. If d(x0,x3) = 3, then by quadrangle condition QC(x0), there exists a vertex y adjacent to x0,x2,x4 and not adjacent to x3. Then the vertices c,y,x2,x3,x4 induce a W4 if y is adjacent to c, and a W4 otherwise. So, suppose that d(x0,x3) = 2. By triangle condition TC(x0), there exists a vertex z adjacent to x0,x2,x3. Suppose that z f c. If CM z ~ x1, then x2,x1 ,z,x3,c induce a forbidden W4. If z ~ x5, the vertices x1,x2, c,x5, z induce a forbidden W4 if z ~ x1 or a W4_ otherwise. If z f x1 ,x5, the vertices z,x2, c,x5 ,x0,x1 induce a forbidden W5. Thus, z ~ c. To avoid a forbidden W4_ or W4 induced by z,c,x1 ,x0,x5, the vertex z must be adjacent to x1 and x5. Finally, to avoid W4 induced by z,c,x3,x4,x5, the vertex z must be adjacent to x4 as well. As a result, we conclude that z is adjacent to x0 CO and to all vertices of the 5-wheel, establishing the W/5-wheel condition. This concludes the proof of the implication (iii)^(ii). Now, we will show that (ii)&(iii)^(i), i.e., that a flag prism complex X satisfying the conditions (ii) and (iii) also satisfies the hypercube and the hyperhouse conditions. First notice that any prism H (and in particular, any cube) of X induces a convex subgraph of G(X). Indeed, if H is not convex, then by local convexity, we can find two vertices x,y of H at distance 2 having a common neighbor outside H. Since x and y already have two common (non-adjacent) neighbors in H, we will obtain in G(X) a forbidden K2 3, W^, or W4. V Hypercube condition. Let q1,q2,q3 be three k-cubes of X that share a common (k - 2)-cube q and pairwise share common (k -1)-cubes qij. Note that qij \ q spans a (k - 2)-cube and qi x qij spans a (k - 1)-cube. For a vertex x of q let xij be the unique neighbor of x in qij \ q. Let xi be the second common neighbor in qi of the vertices xij and xik; xi is in qi \ (qij u qik). By the cube condition, there exists a vertex x* such that x* ~ x1,x2,x3 and x* f x12,x13,x23, and the vertices x*, x,x12,x13,x23 ,x1 ,x2,x3 constitute a 3-cube qx of X. Since x2 e I(x*, x12), o CM 00 CM CM w u a CD U since x2 £ ql and since the cubes are convex, x* £ ql. For similar reasons, x* £ q2, q3. Now, for another vertex y of q denote by yl2,yl3,y23,yl,y2,y3,y* the vertices defined in the same way as for x. From the definition of these vertices we immediately conclude that all xi,xij ,yi,yij are distinct and for all distinct i,j e {1,2,3}, xij ~ yij and xi ~ yi hold if and only if x ~ y. Using the convexity of cubes, we show in the next lemma that any of the vertices x,xl2,xl3,x23,xl,x2,x3 cannot be adjacent to any other vertex from the set 2 5H y,yi2,yi3,y23,yi ,V2,V3- CD Lemma 5.19. For any x,y e q, for any distinct i,j,k, x + yi,yij, xik + yi,yij, yj and xi + yj. Proof. If x (resp. xik) is adjacent to yi or yij, then since x ~ xij (resp. xik ~ xi), either qi contains a triangle, or qi \ qik is not convex. Since xik ~ x and x + yj, the convexity of qj ensures that xik + yj. Finally, the convexity of qi ensures that xi + yj, since yj ~ yij and xi + yij. □ Lemma 5.20. For any x,y e q, for any distinct i,j, x* + y,yi,yij. £ Proof. First suppose by way of contradiction that x* is adjacent to y or yij. Since x* £ qj,, since x* ~ xi, and since xi + y,yij by Lemma 5.19, we get a contradiction with the convexity of qi. Suppose now by way of contradiction that x* ~ yi. If x + y, then xi + yj, and since both xi,yi e qi are adjacent to x* £ qi, we obtain a contradiction with the convexity of the cube qi. Now, suppose that x ~ y. Then, xi ~ yi,xij ~ yij and the vertices xj, xij, yij, yi, xi, x * define a double-house; by Lemma 5.3, it implies that xj ~ yij, contradicting Lemma 5.19. Thus, x* + yi. □ i CM CO CM CM £ CO CO CO u a CD U Lemma 5.21. The set {x*: x e q} spans a (k-2)-cube q' of X and the vertices of qluq2uq3uq' span a (k + 1)-cube of X. Proof. First note that since yl ~ y* and yl + x* by Lemma 5.20, we have that x* t y*. To prove the first assertion of the lemma, since q is a (k - 2)-cube of X, it suffices to show that x* ~ y* if and only if x ~ y. First suppose that x is adjacent to y. Consider the three 2-cubes induced by the 4-cycles (xl,x*,x2,xl2,x\), (xl,yl,yl2,xl2,xl), and (x2,y2,yl2,xl2,x2) of G(X). By the cube condition, they are included in a 3-cube of X, i.e., there exists a vertex s adjacent to x*,yl, and y2. Since qy is a cube, (yl,yl2,y2,y*,yl) is an induced 4-cycle of G(X). Since G(X) does not contain induced K2,3, W_ or W^ we conclude that s = y* or s = yl2. Since x* ~ s and x* + yl2 from Lemma 5.20, s = y* and x* ~ y*. Conversely, suppose that x* ~ y* and assume that x + y. Then xi + yj, and xij + yij. Since xi, yi e qi and since the cube qi is convex, we conclude that d(xi,yi) = 2, (otherwise, (xi,x*,y*,yi) would be a shortest path from xi to yi). Since qi is a cube, it implies that d(x,y) = 2. Let z be a common neighbor of x and y in the cube q and let qz be the 3-cube defined by the vertices z,zl2,zl3,z23,zl,z2,z3,z*. Since z ~ x,y, zl ~ xl,yl and z* ~ x*,y*. Consequently, the vertices xl,zl,yl,y*,z*,x* define a double-house, and from Lemma 5.3, it implies that xl ~ yl, a contradiction. Therefore, x* ~ y* if and only if x ~ y, whence q' is a (k - 2)-cube. o CM IN Qï o CM 00 CM CM CO CO co From Lemmas 5.19 and 5.20, and since q' is a (k - 2)-cube, the vertices of q1 u q2 u q3 u q' span a (k + 1)-cube of X. □ Hyperhouse condition: Let q be a k-cube intersecting a simplex a in an edge (1-simplex) e = uv. Let G' be the subgraph of G(X) induced by conv(q u a). By Proposition 3.1, G' is a finite graph satisfying the condition (iii). Let q = qu u qv, where qu and qv are two disjoint (k - 1)-cubes of q, one containing u and another containing v. If a = e, then we are done. So, suppose a contains at least three vertices. Let H be the gated hull of a. Then H is a weakly bridged graph, thus H does not contain induced 4-cycles. On the other hand, the convex hull of any three vertices of a cube contains a 4-cycle. Since q n H is convex, we conclude that q n H = {u, v}. Next, we will use some tools from the decomposition of fiber-complemented graphs into prime graphs [4,14]. For a vertex a e V(H) let Fa be fiber of a with respect to H: recall that Fa is the set of all vertices of G' whose gate in H is the vertex a. Since G' is fiber-complemented, each fiber Fa(a e V(H)) is gated. For a vertex a e V(H), let Ua = {x e Fa : 3y e Fa,xy e E(G)}, and if b e V(H) is a neighbor of a, let Uab = {x e Fa : 3y e Fb,xy e E(G)}. Let qu,qv,Fa, and Ua also denote the subgraphs induced by these sets. Since cubes induce convex subgraphs of G(X), from the definition of the fibers Fu and Fv we infer that qu is included in Fu and qv is included in Fv. Moreover, since q is a cube and since u ~ v, any vertex of qu has a neighbor in qv, and we conclude that qu £ Uab and qv £ Uba- Since the graph G' is fiber-complemented, if a, b are adjacent vertices of H, then Uab = Ua. Moreover, since any x e Uab has exactly one neighbor in Uba, this gives rise to the following natural mapping /ab : Ua —> Ub that maps x e Ua to the neighbor of x in Ub. Furthermore, fiber-complementarity of G' implies that if a, b are adjacent vertices of H, then Ua and Ub are isomorphic subgraphs of G and /ab is an isomorphism between Ua and Ub. Then the subgraphs Ua are gated for all a e V(H) and are mutually isomorphic; their union is isomorphic to the graph H □ U, where U is any of Ua. Since Uu contains the (k - 1)-cube qu and Uv contains the (k - 1)-cube qv, U contains a (k - 1)-cube qo. Hence a u q is included in H □ U (and therefore in G') in the prism a □ q0. This establishes the hyperhouse condition and concludes the proof of the implication (ii)&(iii)^(i) of Theorem 1. Finally, we establish the last assertion of Theorem 1. Let X be a flag prism complex satisfying the (W4,VFs), the hypercube, and the hyperhouse conditions. Then its 2-skeleton Y := X(2) is a triangle-square flag complex satisfying (W4,VFs), the cube, and the house conditions. Let X be the universal cover of X. Then the 2-skeleton X(2) of X is a covering space of Y. But at the same time X (2) is simply connected (because the 2-skeleton carries all the information about the fundamental group), so X (2) is the universal cover of Y. Since X is the prism complex of X (2) and X (2) = Y satisfies the condition (ii) of Theorem 1, we conclude that X is a bucolic complex. This finishes the proof of Theorem 1. o CM o s CO CO 6. Proofs of Theorems 3 and 4 6.1. Proof of Theorem 3. Let X be a bucolic complex and let G = (V, E) be its 1-skeleton. Pick any vertex v0 of G and let Bk(v0,G) be the ball of radius k centered at v0. Since G is locally-finite, each ball Bk(v0,G) is finite. By Proposition 3.1 the convex hulls conv(Bfc(v0,G)),k > 1, are finite. Hence V is an increasing union of the finite convex sets conv(Bk(v0,G)),k > 1. A subgraph G' of G induced by a convex set of G satisfies the condition (ii) of Theorem 2, thus G' satisfies all other conditions of this theorem, whence G' is bucolic. Hence each subgraph Gk induced by conv(Bk(v0,G)) is bucolic. The prism complex X is an increasing union of the finite bucolic complexes X(G^) of the graphs Gk,k > 1. Thus, to show that X is contractible, by Whitehead theorem, it suffices to show that each complex X(G^) is contractible. By condition (iii) of Theorem 2, the graph Gk can be obtained via Cartesian products of finite weakly bridged graphs using successive gated amalgams. The clique complexes of bridged and weakly bridged graphs are exactly the systolic and weakly systolic complexes, therefore they are contractible by the results of [29] and [32]. Cartesian products of contractible topological spaces are contractible, thus the prism complexes resulting from the Cartesian products of prime graphs are contractible. Now, if a graph G is a gated amalgam of two finite bucolic graphs Gi,G2 with contractible prism complexes X(Gi), X(G2) along a gated subgraph G0 = Gi n G2 which also has a contractible prism complex X(G0), then by the gluing lemma [9, Lemma 10.3], the prism complex X(G') CM of the bucolic graph G' is also contractible. Therefore, for each k, the prism complex X(G^) is contractible. This concludes the proof of Theorem 3. 00 CM 6.2. Proof of Theorem 4. Let X be a bucolic complex and let G = (V, E) denote the 1-skeleton of X. Let F be a finite group acting by cell automorphisms on X (i.e., any f e F maps isometrically prisms onto prisms). Then for an arbitrary vertex v of X, its orbit Fv = {fv : f e F} is finite. Let Gv be the subgraph of G induced by the convex hull in G of the orbit Fv. Since Fv is finite, the graph Gv is finite by Proposition 3.1. Moreover, as a convex subgraph of G, Gv satisfies the conditions of Theorem 2(ii), hence Gv is bucolic. Clearly, the prism complex X(Gv) of Gv is F-invariant. Thus there exists a minimal by inclusion finite non-empty bucolic subgraph of G whose prism complex is F-invariant. Without loss of generality, we denote this subgraph of G also by G and we assert that X(G) is a single prism, i.e., G is the Cartesian product of complete graphs. We prove this assertion in two steps: first we show that G is a box, (i.e., a Cartesian product of prime graphs), and then we show that each prime graph must be a complete graph. By minimality choice of G as an F-invariant bucolic subgraph, we conclude that each proper bucolic subgraph of G is not F-invariant. Therefore, the first step of our proof is a direct consequence of the following result. Proposition 6.1. If G is a finite bucolic graph, then there exists a box that is invariant under every automorphism of G. Proof. If G is a box, then the assertion is trivially true. Suppose now that G is not a box and assume without loss of generality that each proper bucolic subgraph of G is not F-invariant. By Theorem 2(iv), G is a gated amalgam of two proper nonempty gated subgraphs G' and G'' along a common gated subgraph H0. Then we say that H0 is a gated separator of G. Following [10], we will call U' := G's H0 a peripheral subgraph of G if U' does not contain any gated separator of G. Since G is not a box, it contains at least one gated separator, and therefore G contains at least one peripheral subgraph (indeed, among all gated separators of G it suffices to consider a gated separator H0 so that G is the gated amalgam of G' and G'' along H0 and G' has minimum size; then G's H0 is a peripheral subgraph). Let U = {Ui : i e I} be the family of all peripheral subgraphs of G, such that G is the gated amalgam of Gj and Gj' along the gated separator Hi, where Ui = Gj -Hi and Gj't Hi. Note that any automorphism f e F of G maps peripheral subgraphs to peripheral subgraphs, thus the subgraph Uis/ Ui and the subgraph H = nis/ Gj' induced by the complement of this union are both F-invariant subgraphs of G. As an intersection of gated subgraphs of G, H is either empty or a proper gated subgraph of G. In the second case, since gated subgraphs of G are bucolic, we conclude that H is a proper bucolic F-invariant subgraph of G, contrary to minimality of G. So, H is empty. By the Helly property for gated sets of a metric space [21], we can find two indices i, j e I such that the gated subgraphs Gj' and Gj' are disjoint. Since Hi n Hj c Gj' n Gj', the gated separators Hi and Hj are disjoint. But in this case, since Ui = Gj s Hi is peripheral, we conclude that Hj is contained in Gj' (analogously, Hi is contained in Gj'). Thus Hi u Hj c Gj' n Gj', contrary CM to the choice of G'' and G''. Hence G is a box. □ j j CM So, suppose that G is a box. Then the second assertion in the proof of Theorem 4 is an IN CM £ CO CO CD u CD CO u a CD U immediate consequence of the following result. Proposition 6.2. The graph G is the Cartesian product of complete graphs, i.e., X(G) is a prism. Proof. Let G = G1 □ ••• □ G&, where each factor Gi, i = 1,..., k, is a 2-connected finite weakly bridged graph. By [20, Theorem B] every factor Gi is dismantlable. Since dismantlable graphs form a variety -cf. e.g. [31, Theorem 1], it follows that the strong Cartesian product G' = G1 ie ••• ie Gk is dismantlable. Observe that the finite group F acts by automorphisms on G'. By the definition of the strong Cartesian product, any clique of G' is included in a prism of X(G). By [33, Theorem A], there exists a clique a in G' invariant under the action of F. Since F acts by cellular automorphisms on X(G), it follows that F fixes the minimal prism containing all vertices of a (treated as vertices of G, and hence of X(G)). By the minimality choice of G it follows that X(G) is itself a prism. □ References [1] Richard P. Anstee and Martin Farber, On bridged graphs and cop-win graphs, J. Combin. Theory Ser. B 44 (1988), no. 1, 22-28. MR923263 (89h:05053) o CM & (Ö u CD IN 0 Ö o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO $H a CD U [2] Hans-Jürgen Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984), no. 4, 501-510, DOI 10.1002/jgt.3190080407. MR766499 (86c:05104) [3] Hans-Jürgen Bandelt and Victor Chepoi, A Helly theorem in weakly modular space, Discrete Math. 160 (1996), no. 1-3, 25-39. MR1417558 (97h:52006) [4] _, Decomposition and 11-embedding of weakly median graphs, European J. Combin. 21 (2000), no. 6, 701-714, DOI 10.1006/eujc. 1999.0377. Discrete metric spaces (Marseille, 1998). MR1791200 (2002i:05091) [5] _, The algebra of m.etric betweenness. I. S-ubdirect representation and retraction, European J. Combin. 28 (2007), no. 6, 1640-1661, DOI 10.1016/j.ejc.2006.07.003. MR2339492 (2008h:05038) [6] _, Metric graph theory and geom.etry: a survey, Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 49-86. MR2405677 (2009h:05068) [7] Hans-Jürgen Bandelt and Jarmila Hedlikova, Median algebras, Discrete Math. 45 (1983), no. 1, 1-30, DOI 10.1016/0012-365X(83)90173-5. MR700848 (84h:06015) [8] Hans-Jürgen Bandelt, Henry Martyn Mulder, and Elke Wilkeit, Quasi-median graphs and algebras, J. Graph Theory 18 (1994), no. 7, 681-703, DOI 10.1002/jgt.3190180705. MR1297190 (95h:05059) [9] Anders Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819-1872. MR1373690 (96m:52012) [10] Bostjan Bresar, Arboreal structure and regular graphs of median-like classes, Discuss. Math. Graph Theory 23 (2003), no. 2, 215-225. MR2070153 (2005f:05143) [11] Bostjan Bresar, Jeremie Chalopin, Victor Chepoi, Matjaz Kovse, Arnaud Labourel, and Yann Vaxes, Retracts of products of chordal graphs (2011), submitted, available at http://pageperso.lif.univ-mrs.fr/~ victor.chepoi/RetractsPCG.pdf. [12] Bostjan Bresar and Aleksandra Tepeh Horvat, Cage-amalgamation graphs, a common generalization of chordal and median graphs, European J. Combin. 30 (2009), no. 5, 1071-1081, DOI 10.1016/j.ejc.2008.09.003. MR2513910 (2010b:05128) [13] Martin R. Bridson and Andre Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR1744486 (2000k:53038) [14] Marc Chastand, Fiber-complemented graphs. I. Structure and invariant subgraphs, Discrete Math. 226 (2001), no. 1-3, 107-141, DOI 10.1016/S0012-365X(00)00183-7. MR1801065 (2002i:05095) [15] _, Fiber-complemented graphs. II. Retractions and endom.orph.ism.s, Discrete Math. 268 (2003), no. 1-3, 81-101, DOI 10.1016/S0012-365X(02)00682-9. MR1982390 (2004d:05169) [16] Marc Chastand, Francois Laviolette, and Norbert Polat, On constructible graphs, infinite bridged graphs and weakly cop-win graphs, Discrete Math. 224 (2000), no. 1-3, 61-78, DOI 10.1016/S0012-365X(00)00127-8. MR1781285 (2002g:05152) [17] Marc Chastand and Norbert Polat, On geodesic structures of weakly median graphs. I. Decomposition and octahedral graphs, Discrete Math. 306 (2006), no. 13, 1272-1284, DOI 10.1016/j.disc.2005.10.034. MR2237713 (2007c:05064) [18] Victor Chepoi, Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Theory Ser. B 69 (1997), no. 1, 97-100. MR1426753 (97g:05150) [19] _, Graphs of some CAT(0) complexes, Adv. in Appl. Math. 24 (2000), no. 2, 125-179. MR1748966 (2001a:57004) [20] Victor Chepoi and Damian Osajda, Dismantlability of weakly systolic complexes and applications (2009), submitted, available at arXiv:0910.5444v1[math.GR] . [21] Andreas W. M. Dress and Rudolf Scharlau, Gated sets in metric spaces, Aequationes Math. 34 (1987), no. 1, 112-120, DOI 10.1007/BF01840131. MR915878 (89c:54057) [22] David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR1161694 (93i:20036) o CM u CD IN 0 o CM 1 CM CO CM CM £ CO CO [23] Martin Farber and Robert E. Jamison, On local convexity in graphs, Discrete Math. 66 (1987), no. 3, 231-247. MR900046 (89e:05167) [24] Mikhail Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75-263. MR919829 (89e:20070) [25] Frederic Haglund, Complexes simpliciaux hyperboliques de grande dimension, Prepublication Orsay 71 (2003), preprint, available at http://www.math.u-psud.fr/~biblio/ppo/2003/fic/ppo_2003_71.pdf. [26] Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR1867354 (2002k:55001) [27] Wilfried Imrich and Sandi Klavzar, Product graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. Structure and recognition; With a foreword by Peter Winkler. MR1788124 (2001k:05001) [28] John R. Isbell, Median algebra, Trans. Amer. Math. Soc. 260 (1980), no. 2, 319-362, DOI 10.2307/1998007. MR574784 (81i:06006) [29] Tadeusz Januszkiewicz and Jacek Swiatkowski, Simplicial nonpositive curvature, Publ. Math. Inst. Hautes Etudes Sci. 104 (2006), 1-85, DOI 10.1007/s10240-006-0038-5. MR2264834 (2007j:53044) [30] Henry Martyn Mulder, The interval function of a graph, Mathematical Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam, 1980. MR605838 (82h:05045) [31] Richard Nowakowski and Peter Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983), 235-239. [32] Damian Osajda, A combinatorial non-positive curvature I: SDn property (2010), preprint, available at http://www.math.uni.wroc.pl/~dosaj/trav/cnpc100503.pdf. [33] Norbert Polat, Finite invariant simplices in infinite graphs, Period. Math. Hungar. 27 (1993), no. 2, 125-136, DOI 10.1007/BF01876637. MR1291160 (96a:05073) [34] _, On isom.etric subgraphs of infinite bridged graphs and geodesic convexity, Discrete Math. 244 (2002), no. 1-3, 399-416. Algebraic and topological methods in graph theory (Lake Bled, 1999). MR1844048 (2003c:05070) [35] Martin A. Roller, Poc sets, median algebras and group actions. An extended study of Dunwoody's construction and Sageev's theorem, Univ. of Southampton Preprint Ser. (1998), preprint. [36] Misha Sageev, Ends of group pairs and non-positively curved cube complexes, Proc. London Math. Soc. (3) 71 (1995), no. 3, 585-617. MR97a:20062 [37] Valeriu P. Soltan and Victor Chepoi, Conditions for invariance of set diameters under d-convexification in a graph, Kibernetika (Kiev) 6 (1983), 14-18 (Russian, with English summary); English transl., Cybernetics 19 (1983), no. 6, 750-756 (1984). MR765117 (86k:05102) [38] Marcel van de Vel, Matching binary convexities, Topology Appl. 16 (1983), no. 3, 207-235, DOI 10.1016/0166-8641(83)90019-6. MR722115 (85f:52026) [39] _, Theory of convex structures, North-Holland Mathematical Library, vol. 50, North-Holland Publishing Co., Amsterdam, 1993. MR1234493 (95a:52002) [40] Gunter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR1311028 (96a:52011) m CD $H CD m u a CD U