AAECC DOI 10.1007/s00200-014-0245-0 ORIGINAL PAPER

Topology of acyclic complexes of tournaments and coloring Zakir Deniz

Received: 17 February 2014 / Revised: 23 July 2014 / Accepted: 28 July 2014 © Springer-Verlag Berlin Heidelberg 2014

Abstract We prove that the acyclic complex Acy(T ) of any trisectionable tournament T is homotopy equivalent to a wedge of spheres, and show that there exists a fix number 0 <  < 1 such that if T is a trisectionable tournament and d is the highest dimension of a sphere occurring in such a decomposition for Acy(T ), then the (acyclic) chromatic 1 number of T satisfies χ (T )  c(d + 1)  −1 − 1 for some 1.62 < c  2, and by way of an example, we verify that the provided upper bound is tight. Keywords

Acyclic complex · Acyclic coloring · Tournament

Mathematics Subject Classification

13F55 · 05C15 · 05C20

1 Introduction The (vertex) coloring theory of undirected graphs can be naturally extended to directed graphs by replacing the notion of an independent set with that of a transitive (acyclic) set in the digraph. The coloring of directed graphs in that manner brings new problems that have no interesting counterparts in the undirected case. For instance, if we only consider the colorings of tournaments, complete graphs whose edges are directed, there exist nontrivial tournaments H for which every H -free tournament has a bounded chromatic number (depending on H ). Such tournaments are called heroes in [2], where Berger et al. have provided a characterization of heroes in detail.

The author is supported by TÜB˙ITAK, Grant No: 111T704. Z. Deniz (B) Department of Mathematics, Suleyman Demirel University, Isparta 32260, Turkey e-mail: [email protected]

123

Z. Deniz

In the topological side, one can associate a simplicial complex, the acyclic complex Acy(G), to any digraph G whose faces are transitive subsets of the digraph that exactly corresponds to the independence complex of an undirected graph through such an extension. Unlike the independence complexes, the acyclic complex of a digraph may not need to be a flag complex, that is, such a complex can contain minimal non faces of order greater than two. The topological study of acyclic complexes seems not to be new, at least those of tournaments. Burzio and Demaria [4] provide a complete combinatorial characterization of tournaments whose acyclic complexes have nontrivial fundamental groups (they choose to call them as simply disconnected tournaments). The simply disconnected tournaments have a natural decomposition in the sense that if T is such a tournament, then T ∼ = Rm (P 1 , . . . , P m ) for some tournaments P 1 , . . . , P m , where Rm is a highly regular tournament on m vertices (see Sect. 2 for details). We have a particular interest to the case where m = 3 in which we introduce inductively a class of tournaments by declaring that a tournament T is trisectionable if either T is transitive or T ∼ = R3 (P, R, K ) for some trisectionable tournaments P, R and K . We note that trisectionable tournaments are not heroes in general. This is mostly due to the fact that the trisectionable tournament R3 (C3 , C3 , 1) is not a hero, and every subtournament of a hero is a hero, where C3 denotes the 3-dicycle. We determine the homotopy type of the acyclic complexes of trisectionable tournaments, and the following is one of our main result: Theorem 4.4 Let T = R3 (P, R, K ) be a trisectionable tournament. Then there exists a sequence {d2 , d3 , . . . , dk } of non negative integers such that Acy(T )  S 1 ∨

d 2  i=1

 S2 ∨

d 3  i=1



⎛

S3 ∨ · · · ∨ ⎝

dk 

⎞ Sk ⎠ .

i=1

We remark that the sequence {d2 , d3 , . . . , dk } satisfies that di = 0 whenever dk = 0 for any 2  i  k − 1. When T is a trisectionable tournament, if we define the largest dimension of a sphere occurring in the wedge decomposition of Acy(T ) as the dept of T , and denoted it by dept(T ), we derive the second main result of this paper: Theorem 4.9 If T is a trisectionable tournament, there exist 0 <  < 1 and 1.62 < 1 c  2 such that χ (T )  c(dept(T ) + 1)  −1 − 1. 2 Preliminaries A tournament T is a (finite) directed graph on a set V = V (T ) such that either uv or vu is an edge (but not both) of T for each pair of distinct vertices u and v. For a given subset S ⊆ V , the sets N + (S) := {v ∈ V : uv for some u ∈ S} and N − (S) := {w ∈ V : wu for some u ∈ S} are called the set of out-neighbors and in-neighbors of S in T respectively. Furthermore, d + (x) := |N + (x)| and d − (x) := |N − (x)| are called out-degree and in-degree of the vertex x.

123

Topology of acyclic complexes x1

x1 x7

x6

x3

x5

x2

x7

x2

x6

x4

x3

x5

x4

Fig. 1 A highly decomposable tournament and its decomposition

A tournament T is said to be regular if d + (v) = d − (v) for any v ∈ V , and an nvertex regular tournament Tn is called highly-regular if n = 2k +1 for some k  1 and there exists a cyclic ordering v1 , v2 , . . . , v2k+1 of the vertices such that vi v j ∈ E(Tn ) for any i ∈ [n] and j ≡ i + l (mod n) for some l ∈ [k]. For each k  3, we denote the directed cycle (or dicycle) by Ck , where it is the directed graph on an ordered set of vertices u 1 , u 2 , . . . , u k such that u i u i+1 ∈ E(Ck ) in the cyclic fashion, and a subdigraph C of a tournament T is called a dicycle of T whenever C ∼ = Ck for some k  3. A subset S ⊆ V is said to be an acyclic (or transitive) set in T if the induced subtournament T [S] contains no dicycle, and a tournament T is called transitive whenever V is itself a transitive set in T . A map μ : V → [k] is said to be a k-coloring of a tournament T , if the set {v ∈ V : μ(v) = i} is transitive in T for each i ∈ [k], and the chromatic number of T is defined to be the least integer k for which T admits a k-coloring. For any given A, B ⊆ V , we write A ⇒ B provided that ab ∈ E(T ) for any a ∈ A and b ∈ B, and a tournament T is reducible if there exist disjoint subsets A, B ⊂ V satisfying V = A ∪ B such that either A ⇒ B or B ⇒ A holds in T ; otherwise it is irreducible. For a given subset P ⊆ V , we say that P has an equivalent set of vertices, if for any q ∈ V \P, we have either q ⇒ P or P ⇒ q. If the vertices of T can be partitioned into disjoint subtournaments P 1 , P 2 , . . . , P m such that each P i has an equivalent set of vertices, and Q m is a tournament on w1 , w2 , . . . , wm in which wi w j ∈ E(Q m ) if and only if P i ⇒ P j , then we write T = Q m (P 1 , P 2 , . . . , P m ) and call T as the composition of the components P 1 , P 2 , . . . , P m with the quotient Q m . In particular, a tournament Tn is said to be simple, if Tn = Q m (P 1 , P 2 , . . . , P m ) implies that either m = 1 or m = n. Note that every nontrivial tournament has precisely one nontrivial simple quotient tournament [6]. Furthermore, if T = Q m (P 1 , P 2 , . . . , P m ), then there exists a digraph homomorphism ΓT,Q : T → Q defined by ΓT,Q (P i ) = wi for any i ∈ [m]. We say that a tournament T is highly decomposable if its nontrivial simple quotient is highly regular, that is, T = Rm (P 1 , P 2 , . . . , P m ), where Rm is a highly regular tournament for some m  3 (see Fig. 1).

123

Z. Deniz

2.1 Simplicial complexes An (abstract) simplicial complex Δ on a finite set X is a family of subsets of X satisfying the following properties. (i) {x} ∈ Δ for all x ∈ X . (ii) If F ∈ Δ and H ⊂ F, then H ∈ Δ. The elements of Δ are called faces; the dimension of a face F is dim(F) := |F|−1, and the dimension of Δ is defined to be dim(Δ) := max{dim(F) : F ∈ Δ}. The 0 and 1-dimensional faces of Δ are called vertices and edges while maximal faces are called facets, and the set of facets of Δ is denoted by F(Δ). A subset C of X is called a circuit of Δ if C is a minimal non-face of Δ. If G = (V, E) is a (simple) undirected graph, a subset F ⊆ V is said to be a complete of G, if the induced subgraph G[F] is isomorphic to a complete graph, and the simplicial complex Δ(G) on the set V whose faces are completes of G is called the clique complex of G. A graph G is called chordal if it contains no induced cycle on k vertices for any k  4. In many cases, we will appeal to an induction on the cardinality of the vertex set by a particular choice of a vertex accompanied by two subcomplexes. To be more / F} explicit, if x is a vertex of Δ, then the subcomplexes delΔ (x) := {F ∈ Δ : x ∈ / R and R ∪ {x} ∈ Δ} are called the deletion and link and link Δ (x) := {R ∈ Δ : x ∈ of x in Δ respectively. The simplicial join of two complexes Δ1 and Δ2 on disjoint sets of vertices, denoted by Δ1 ∗ Δ2 , is the simplicial complex defined by Δ1 ∗ Δ2 = {σ ∪ τ | σ ∈ Δ1 , τ ∈ Δ2 } In the particular case, the join of a simplicial complex Δ with a 0-dimensional sphere S 0 = {∅, {a}, {b}} is the suspension of Δ, that is, ΣΔ = S 0 ∗ Δ, and similarly, the join of Δ with the simplicial complex {∅, {v}} is the cone over Δ with apex v. The disjoint union and the wedge product of two simplicial complexes Δ1 and Δ2 are denoted by Δ1  Δ2 and Δ1 ∨ Δ2 , respectively. A simplicial complex is said to be simply connected if its fundamental group is trivial, otherwise, it is called simply disconnected. Proposition 2.1 [10] Let Δ1 , Δ2 and Δ3 be simplicial complexes on disjoint vertex sets. Then the followings hold: (i) (ii) (iii) (iv)

Δ1 ∗ Δ2 ∼ = Δ2 ∗ Δ1 , Δ1 ∗ (Δ2 ∗ Δ3 ) ∼ = (Δ1 ∗ Δ2 ) ∗ Δ3 , Δ1 ∗ (Δ2 ∨ Δ3 ) ∼ = (Δ1 ∗ Δ2 ) ∨ (Δ1 ∗ Δ3 ), Σ(Δ1  Δ2 )  ΣΔ1 ∨ S 1 ∨ ΣΔ2 ,

We remark that the homotopy equivalences Σ(Δ1 ∗ Δ2 )  (ΣΔ1 ) ∗ Δ2 and Δ ∗ S n  Σ n+1 Δ hold by Proposition 2.1 and the fact that the k-fold join (S 0 )∗k = S 0 ∗ S 0 ∗ · · · ∗ S 0 is homeomorphic to S k−1 for any k  2.

123

Topology of acyclic complexes

Lemma 2.2 [9] Let Δ be a simplicial complex. If link Δ (x) is contractible in delΔ (x) for some vertex x, then Δ  delΔ (x) ∨ Σ link Δ (x). The notion of an edge-contraction on a simplicial complex seems firstly studied by Hoppe [8], and it was later investigated in the language of independence complexes by Ehrenborg and Hetyei [7] (see also [1]). Let Δ be a simplicial complex on the vertex set V (Δ), and consider x, y ∈ V (Δ) / V (Δ). The edge contraction x y → wx y can be such that {x, y} ∈ Δ and wx y ∈ defined to be a map f : V (Δ) → (V (Δ)\{x, y}) ∪ {wx y } by f (v) :=

v, if v ∈ / {x, y}, wx y , if v ∈ {x, y}.

We then extend f to all simplices F = {v0 , v1 , . . . , vk } of Δ by setting f (F) := { f (v0 ), f (v1 ), . . . , f (vk )}. The simplicial complex Δ // x y := { f (F) : F ∈ Δ} is called the contraction of Δ with respect to the edge {x, y}. Observe that the contraction of an edge may not need to preserve the homotopy type of the complex in general. However, under a suitable restriction on the contracted edge, we can guarantee this to happen. Theorem 2.3 [1, Theorem 1], [7, Theorem 2.4] Let Δ be a simplicial complex and let {x, y} ∈ Δ be an edge. Then, the simplicial complexes Δ and Δ // x y are homotopy equivalent provided that the edge {x, y} is contained by no circuit in Δ. 3 Acyclic complexes of tournaments In this section, we introduce our main object of study, the acyclic complexes. Definition 3.1 The acyclic complex Acy(T ) of a given tournament T is defined to be the simplicial complex on the vertex set V (T ) whose faces are transitive subset of T (see Fig. 2).

x1

x4

x2

x3

x1 x3

x4

x2

Fig. 2 A tournament and its acyclic complex

123

Z. Deniz

We remark that when T = Q m (P 1 , P 2 , . . . , P m ), the homomorphism ΓT,Q : T → Q extends to a simplicial map between Acy(T ) and Acy(Q), which we continue to denote by ΓT,Q . Lemma 3.2 If T = Q m (P 1 , P 2 , . . . , P m ), then ΓT,Q (F) ∈ F(Acy(Q)) provided that F ∈ F(Acy(T )), and any facet of Acy(Q) is of this form. / Proof Assume otherwise that there exists F ∈ F(Acy(T )) such that ΓT,Q (F) ∈ F(Acy(Q)). It follows that there exists a vertex wi ∈ V (Q)\ΓT,Q (F) such that ΓT,Q (F) ∪ {wi } ∈ Acy(Q). However, this forces F  ∪ F ∈ Acy(T ) for any F  ∈ Acy(P i ), a contradiction. Suppose now that D = {wi1 , . . . , wit } ∈ F(Acy(Q)). If we let Di j ∈ F(Acy(P i j )) for each j ∈ [t] and consider D  := Di1 ∪ · · · ∪ Dit , then we have D  ∈ F(Acy(T ))   and ΓT,Q (D  ) = D as claimed. Definition 3.3 Let C be a dicycle of a tournament T . (i) C is said to be coned by a vertex v ∈ V \V (C) provided that either v ⇒ C or C ⇒ v holds in T . Otherwise, C is said to be a non-coned dicycle. (ii) C is called shrinkable if either q ⇒ C or C ⇒ q for any q ∈ V \V (C) holds in T . Otherwise, C is said to be an unshrinkable dicycle. We remark that a dicycle C is shrinkable if and only if it has an equivalent set of vertices in T , and each shrinkable dicycle is also coned. An edge of a tournament T is called saturated if there exists a 3-dicycle in T containing it; otherwise such an edge is said to be unsaturated, and we say that T is a saturated tournament if every edge of T is saturated in T . In a series of papers, Burzio and Demaria [4,5] have given a complete combinatorial characterization of simply disconnected tournaments. We next state some of their results which will be in use in the sequel. Proposition 3.4 [5] Each 3-dicycle of a highly regular tournament is non-coned. Theorem 3.5 [5] For a given tournament T , the acyclic complex Acy(T ) is simply disconnected if and only if there exists a non-coned 3-dicycle in T and all the coned 3-dicycles are shrinkable. Theorem 3.6 [4] For a given tournament T , the acyclic complex Acy(T ) is simply disconnected if and only if T is highly decomposable. Our next task is to analyze the effect of edge contractions on acyclic complexes of tournaments. Corollary 3.7 Acy(T )  Acy(T ) // uv for any unsaturated edge uv in a tournament T. Proof Note that since the edge uv is unsaturated, no circuit of Acy(T ) can contain the edge {u, v}, so the claim follows from Theorem 2.3.   Lemma 3.8 Any highly regular tournament is saturated.

123

Topology of acyclic complexes

Proof Let R = R2k+1 be a highly regular tournament, and let vi v j be an edge of R. If we choose r = j + k (mod 2k + 1), then the set {vi , v j , vr } induces a 3-dicycle containing the required edge.   Lemma 3.9 Let Rm be a highly regular tournament. Then there is a vertex v ∈ V (Rm ) such that the tournament Rm − v has precisely one unsaturated edge. Proof Assume that m = 2k + 1 and let {v1 , v2 , . . . , v2k+1 } be the set of vertices of Rm ordered in the required cyclic fashion, and we let v = vk+1 and write R  := Rm − v. We then claim that only the edge v2k+1 v1 is unsaturated in R  . Observe first that the edge v2k+1 v1 is unsaturated in R  , since if v1 v j ∈ E(R  ), then j  k so that / E(R  ). The uniqueness of v2k+1 v1 follows from Lemma 3.8.   v j v2k+1 ∈ Definition 3.10 Let uv be an unsaturated edge in a tournament T . Then we define a tournament Tuv on (V \{u, v}) ∪ {wuv } such that E(Tuv ) consists of edges in E(T [V \{u, v}]), and for any x ∈ (V \{u, v}), (i) xwuv ∈ E(Tuv ), if xu ∈ E(T ) and xv ∈ E(T ), (ii) wuv x ∈ E(Tuv ), if ux ∈ E(T ) and vx ∈ E(T ), (iii) wuv x ∈ E(Tuv ), if either ux is an unsaturated edge or both edges ux and xv are saturated in T , (iv) xwuv ∈ E(Tuv ), if either xu is an unsaturated edge or both edges xu and vx are saturated in T , (v) xwuv ∈ E(Tuv ), if the edge ux is saturated while xv is an unsaturated edge in T , (vi) wuv x ∈ E(Tuv ), if the edge xu is saturated while vx is an unsaturated edge in T , Corollary 3.11 Acy(T ) // uv ∼ = Acy(Tuv ) for any unsaturated edge uv in a tournament T . Proof This is an easy consequence of Lemma 3.2 of [7], since both complexes have the same blocking systems.   Lemma 3.12 Let R = R2k+1 be a highly regular tournament. Then there exist vertices x, u, v in R such that (R − x)uv is a highly regular tournament. Proof Following Lemma 3.9, if we choose x = vk+1 , u = v1 and v = v2k+1 , then the edge uv is unsaturated in R  = R − x so that (R  )uv is well-defined. Furthermore, the ordering wuv , v2 , v3 , . . . , vk , vk+2 , . . . , v2k of vertices in (R  )uv satisfies the required cyclic ordering condition.   Theorem 3.13 Acy(Rm )  S 1 for any highly regular tournament Rm . Proof If m = 3, we readily have Acy(R)  S 1 so that we may assume m > 3. We let x = vk+1 , and consider the subcomplex link Acy(R) (x). Note that since every 3-dicycle in a highly regular tournament is non-coned by Proposition 3.4, any circuit of link Acy(R) (x) has exactly two elements, that is, link Acy(R) (x) is the clique complex Δ(G x ) of a graph G x on {v1 , v2 , . . . , vk , vk+2 , . . . , v2k+1 }. We claim that G x is a chordal graph so that link Acy(R) (x) = Δ(G x ) is contractible (see Corollary 4.5 in [3]). Observe that the sets N − (x) = {v1 , . . . , vk } and N + (x) = {vk+2 , . . . , v2k+1 } must be

123

Z. Deniz v1

v2k+1

.. .

.. .

vi1 .. . vi2

v j2 .. .

.. .

.. .

v j1

vk+2

vk

vk+1

Fig. 3 Chordality of the graph Gx

cliques of G x , that is, G x could only contain an induced 4-cycle (see Fig. 3). Suppose that {vi1 , vi2 , v j1 , v j2 } induces such a cycle with edges vi1 vi2 , v j1 v j2 , vi1 v j2 and vi2 v j1 , where 1  i 1 < i 2  k and k + 2  j1 < j2  2k + 1. Since vi1 , vi2 ∈ N − (x) and v j1 , v j2 ∈ N + (x), we need to have that both edges vi1 v j2 and vi2 v j1 belong to R. However, this forces vi1 v j1 ∈ E(R), that is, vi1 v j1 ∈ E(G x ) so that any such cycle has a chord, a contradiction. Now, since link Acy(R) (x) is contractible, it follows that Acy(R)  Acy(R − x) by Lemma 2.2. Now, if we write u = v1 and v = v2k+1 , the edge vu is unsaturated in R − x, and (R − x)uv is a highly regular tournament. On the other hand, we have Acy(R − x)  Acy(R − x) // uv ∼ = Acy((R − x)uv ), where the homotopy equivalence is due to Corollary 3.7, and the isomorphism follows from Corollary 3.11. We may therefore apply to the induction to conclude that Acy((R − x)uv )  S 1 , that is,   Acy(R)  Acy(R − x)  Acy((R − x)uv )  S 1 that completes the proof. Corollary 3.14 Acy(T )  S 1 if T = Rm (P 1 , P 2 , . . . , P m ) such that Rm is a highly regular tournament and P i is transitive for any i ∈ [m]. Proof Note that if each P i consists of a single vertex, then the claim follows from Theorem 3.13. Assume otherwise that |P 1 |  2, and let u, v ∈ V (P 1 ) such that uv ∈ E(P 1 ). Observe that such an edge uv is necessarily unsaturated in T so that Acy(T )  Acy(T ) // uv by Corollary 3.7. On the other hand, we then have Acy(T ) // uv ∼ = 1 , P 2 , . . . , P m ) and the Acy(Tuv ) by Corollary 3.11. Moreover, since Tuv = Rm (Puv 1 is also transitive, the result follows from the induction on the order tournament Puv of T .   4 Trisectionable tournaments This section is devoted to the proofs of our main results.

123

Topology of acyclic complexes

v

P1 R1

K1

P2 Rs 1

Ks 1

Ps

R

K

Fig. 4 A trisectionable tournament

Definition 4.1 Let Tn be a tournament. We say that Tn is a trisection tournament if Tn = R3 (P, R, K ), where each of P, R and K has an equivalent set of vertices in Tn . In particular, we call Tn as a trisectionable tournament if either Tn is transitive or n  3 and Tn = R3 (P, R, K ) for the highly regular tournament R3 and trisectionable tournaments P, R, K . We remark that any trisectionable tournament of the form T = R3 (P, R, K ) is never transitive. Suppose that Tn = R3 (P, R, K ) is a trisectionable tournament such that P is a non-transitive tournament. Then there exists a sequence P i , R i , K i of trisectionable tournaments for some 1  i  s such that P i+1 = R3 (P i , R i , K i ), and P = P s , R = R s , K = K s , and P 1 = R3 . The greatest possible integer s for which there exists such a sequence is called the length of Tn with respect to P, denoted by l(Tn , P). We note that in the degenerate case, where the subtournament P is transitive, we set l(Tn , P) = 0. We then define the height of Tn to be h(Tn ) := max{l(Tn , P), l(Tn , R), l(Tn , K )} + 1 (see Fig. 4). Lemma 4.2 Let T = R3 (P, R, K ) be a trisectionable tournament. Then there exists a vertex x ∈ V (P) such that link Acy(T ) (x) ∼ = link Acy(P) (x) ∗ (Acy(R)  Acy(K )). Proof We may assume that l(T, P) = s > 1, since otherwise the claim is obvious. Then there exists a sequence P i , R i , K i of trisectionable tournaments for 1  i  s such that P i+1 = R3 (P i , R i , K i ) for any i < s and P = P s , R = R s , K = K s . In particular, we have P 1 = R3 . We claim that if we choose a vertex, say x ∈ V (P 1 ),

123

Z. Deniz

the stated claim holds for the vertex x. Observe first that since x ⇒ R, R ⇒ K and K ⇒ x in T , for any face F in link Acy(T ) (x), at least one of the intersection F ∩ R and F ∩ K must be empty. Furthermore, if S ∈ link Acy(P) (x), then we have S ∪ L ∈ link Acy(T ) (x) (resp. S ∪ H ∈ link Acy(T ) (x)) for any L ∈ Acy(R) (resp. for any H ∈ Acy(K )) from which the claim follows.   Lemma 4.3 Let T = R3 (P, R, K ) be a trisectionable tournament. Then the following homotopy equivalence holds:



Acy(Tn )  S 1 ∨ Σ Acy(P) ∨ Acy(R) ∨ Acy(K ) ∨ Acy(P) ∗ Acy(R)



∨ Acy(P) ∗ Acy(K ) ∨ Acy(R) ∗ Acy(K ) Proof Firstly, if each of P, R and K is transitive, the claim follows from Corollary 3.14. We may therefore assume without loss of generality that P is a nontransitive tournament. Then there exists a sequence P i , R i , K i of trisectionable tournaments for 1  i  s such that P i+1 = R3 (P i , R i , K i ) for any i < s and P = P s , R = R s , K = K s . In particular, we have P 1 = R3 . We let V (P 1 ) = {v, u, w}, and consider the subcomplex link Acy(T ) (v). We claim that link Acy(T ) (v) is contractible in delAcy(T ) (v). Note that the edge {u, w} is contained by no circuits of delAcy(T ) (v) so that delAcy(T ) (v)  delAcy(T ) (v) // uw. However, this implies that link Acy(T ) (v) becomes a cone in delAcy(T ) (v) // uw with apex x, the vertex to which the edge {u, w} is contracted; hence, it is contractible. Then we have Acy(T )  delAcy(T ) (v) ∨ Σ link Acy(T ) (v) by Lemma 2.2. Now, since delAcy(T ) (v) ∼ = Acy(T − v), and T − v = Rm (P − v, R, K ) is a trisectionable tournament, we may apply induction on the order of T so that the homotopy equivalence



Acy(T −v)  S 1 ∨ Σ Acy(P −v)∨Acy(R) ∨ Acy(K ) ∨ Acy(P −v) ∗ Acy(R)



∨ Acy(P − v) ∗ Acy(K ) ∨ Acy(R) ∗ Acy(K ) holds. It then follows that



Acy(T )  S 1 ∨ Σ Acy(P − v) ∨ Acy(R) ∨ Acy(K ) ∨ Acy(P − v) ∗ Acy(R)



∨ Acy(P −v) ∗ Acy(K ) ∨ Acy(R) ∗ Acy(K ) ∨ Σ link Acy(T ) (v). By Lemma 4.2 and repeated use of Proposition 2.1, we conclude that



Acy(T )  S 1 ∨ Σ Acy(P − v) ∨ Acy(R) ∨ Acy(K ) ∨ Acy(P − v) ∗ Acy(R)



∨ Acy(P − v) ∗ Acy(K ) ∨ Acy(R) ∗ Acy(K )



 ∨ Σ link Acy(P) (v) ∗ Acy(R)  Acy(K ) , (by Lemma 4.2)



 S 1 ∨ Σ Acy(P − v) ∨ Acy(R) ∨ Acy(K ) ∨ Acy(P − v) ∗ Acy(R)



∨ Acy(P − v) ∗ Acy(K ) ∨ Acy(R) ∗ Acy(K )

∨ link Acy(P) (v) ∗ Σ Acy(R)∨ S 1 ∨ Σ Acy(K ) , (by Prop. 2.1. (iv))



 S 1 ∨ Σ Acy(P − v) ∨ Acy(R) ∨ Acy(K ) ∨ Acy(P − v) ∗ Acy(R)

123

Topology of acyclic complexes





∨ Acy(P − v) ∗ Acy(K ) ∨ Acy(R) ∗ Acy(K )

∨ Σ link Acy(P) (v) ∗ Acy(R) ∨ Σ 2 link Acy(P) (v))

∨ Σ link Acy(P) (v) ∗ Acy(K ) , (by Prop. 2.1. (iii))



  S 1 ∨ Σ Acy(P − v) ∨ Σ link Acy(P) (v) ∨ Acy(R) ∨ Acy(K )

∨ Acy(P − v) ∨ Σ link Acy(P) (v) ∗ Acy(R)

∨ Acy(P − v) ∨ Σ link Acy(P) (v) ∗ Acy(K )

∨ Acy(R) ∗ Acy(K ) , (by Prop. 2.1. (iii)) Finally, a similar argument as above ensures that link Acy(P) (v) is contractible in Acy(P − v) ∼ = delAcy(P) (v) so that Acy(P)  delAcy(P) (v) ∨ Σ link Acy(P) (v) from which the claim follows.   Theorem 4.4 Let T = R3 (P, R, K ) be a trisectionable tournament. Then there exists a sequence {d2 , d3 , . . . , dk } of non negative integers such that Acy(T )  S 1 ∨

d 2  i=1

 S2 ∨

d 3 



⎛

S3 ∨ · · · ∨ ⎝

i=1

dk 

⎞ Sk ⎠ .

(4.1)

i=1

Proof This follows from the induction on the order of T together with Lemma 4.3 and the fact that S n ∗ S m  S n+m+1 for any pair of non negative integers n and m.   Definition 4.5 Let T = R3 (P, R, K ) be a trisectionable tournament. We call the largest dimension of a sphere occurring in the wedge decomposition of Acy(T ) as the dept of T , and denoted it by dept(T ). The following is a consequence of Lemma 4.3: Corollary 4.6 Let T = Tn = R3 (P, R, K ) be a trisectionable tournament with n > 1. Then we have dept(T ) = max{dept(P)+dept(R)+1, dept(P)+dept(K )+1, dept(R)+dept(K )+1}. Example 4.7 We recall from [2] that the trisection tournaments of the form R3 (H, S1 , Sk ) or R3 (H, Sk , S1 ) are heroes whenever the tournament H is a hero, where S j is the transitive tournament on j vertices. In this guise, we define inductively a class, the perfect heroes, of trisectionable tournaments that are also heroes. Now, the tournaments R3 (S1 , S1 , Sk ) and R3 (S1 , Sk , S1 ) are perfect heroes, and in general we say that a tournament T is a perfect hero if there exists a perfect hero H such that T is isomorphic to one of R3 (H, S1 , Sk ) and R3 (H, Sk , S1 ) for some k  1. It then follows from Theorem 4.4 that Acy(T )  S 1 ∨ S 2 ∨ · · · ∨ S m for any perfect hero T , where m = h(T ). In the rest of this section, we prove Theorem 4.9. Having this in mind, we first state a technical result related to colorings of trisection tournaments.

123

Z. Deniz 3 i Lemma 4.8 Let T = R3 (P 1 , P 2 , P a trisection  tournament. If χ (P ) = ri for  )r1be +r2 +r3  , ri . each 1  i  3, then χ (T )  max 2

Proof Suppose that P 1 , P 2 and P 3 are colored using colors from the disjoint sets A = {a1 , a2 , . . . , ar1 }, B = {b1 , b2 , . . . , br2 }, and C = {c1 , c2 , . . . , cr3 } respectively. We analyze the relations among r1 , r2 and r3 , and provide in each case three plates of colors from which the tournaments P 1 , P 2 and P 3 can be colored respectively, and the resulting coloring creates a legal coloring for T using at most the claimed number of colors for which we may assume without loss of generality that r1  r2  r3 . Case 1. r1 = r2 = r3 = r . In this case, we consider the following color plates {b1 , b2 , . . . , br/2 , c1 , c2 , . . . , {a1 , a2 , . . . , ar/2 , b1 , b2 , . . . , br/2 }, cr/2 } and {a1 , a2 , . . . , ar/2 , c1 , c2 , . . . , cr/2 }. Note that this provides a legal coloring of T , since each color appears in exactly two plates so that each directed triangle receives at least two colors. Case 2. r1  r2 + r3 . Then, we consider A, {a1 , a2 , . . . , ar2 } and {ar2 +1 , ar2 +2 , . . . , ar2 +r3 }. Case 3. r1 < r2 + r3 and r2  r1 + r3 . Assume  with out loss of generality r2 + r3 − r1 . Now, consider the plates A, that r2  r3 , and let w := 2 {a1 , a2 , . . . , ar2 −w , b1 , b2 , . . . , bw } and {ar2 −w+1 , . . . , ar1 −(r2 −w) , b1 , b2 , . . . , bw }. r  3 , and consider the plates A, Case 4. r1 = r2 > r3 . We define w = 2 {a1 , a2 , . . . , ar1 −w , c1 , c2 , . . . , cw } and {c1 , c2 , . . . , cw , ar1 −w+1 , ar1 −w+2 ,   . . . , ar1 }. We are now ready to prove our second main result. Theorem 4.9 If T = R3 (P 1 , P 2 , P 3 ) is a trisectionable tournament, there exist 0 < 1  < 1 and 1.62 < c  2 such that χ (T )  c(dept(T ) + 1)  −1 − 1. 2 Proof We write dept(T ) = d and fix  = ln ln 3 . Note that the stated claim is equivalent  log(d+1)  − 1, where the logarithm has two as its base. to verifying that χ (T )  c 3 d+1 We proceed by an induction on the order of T . If |V (T )| = 3, then T is just a 3-dicycle so that χ (T ) = 2 = 2 23 − 1 in which we have c = 2. In the general case where |V (T )| > 3, we write dept(Pi ) = di , and assume that there exist ci ∈  log(d i +1) 3 i − 1 for each 1  i  3. We also note (1.62, 2] such that χ (P )  ci di +1 that d = max{d1 + d2 + 1, d1 + d3 + 1, d2 + d3 + 1} by Corollary 4.6, and set c := max{c1 , c2 , c3 }. Observe that the claim trivially holds if χ (T )  χ (P i ) for some i ∈ [3]. Otherwise, we suppose that d = d1 + d2 + 1 and d1  d2  d3 . Case 1. d1 = d2 . We apply to Lemma 4.8 that

⎡ χ (T )  ⎢ ⎢ ⎢

123

3c ·

3log(d1 +1) d1 +1

2

−3

⎢ ⎢ ⎢ 3c · ⎥=⎣ ⎥ ⎥ ⎤

3log(d1 +1) d1 +1

2

⎥ ⎥ − 3 + 1⎥ ⎦,

Topology of acyclic complexes

   3log(d+1) 3log(2d1 +2) −1 = c· −1  c· 2d1 + 2 d +1 

c·

3log(d+1) − 1, d +1

where the last equality is due to the fact that d = 2d1+ 1 in such  a case. d1 +d2 +2 for j = 1, 2 so that Case 2. d1 = d2 . In this case, we let t j := log d j +1 0 < t1 < 1, and again apply to Lemma 4.8: ⎡

c1 ·

χ (T )  ⎢ ⎢ ⎢ ⎢ ⎢ ⎢c · ⎣ ⎢ ⎢ ⎢c · ⎣

3log(d1 +1) d1 +1

+ c2 ·

3log(d2 +1) d2 +1

+ c3 ·

3log(d3 +1) d3 +1

−3

2 3log(d1 +1) d1 +1

+c·

3log(d2 +1) d2 +1

+c·

3log(d3 +1) d3 +1

2 3log(d1 +1) d1 +1

+ 2c · 2

3log(d2 +1) d2 +1

⎥ ⎥ ⎥ − 1⎦ ,

⎤ ⎥, ⎥ ⎥

⎥ ⎥ ⎥ − 1⎦ ,



 1 3log(d1 +1) 3log(d2 +1)  c· +c· −1 , 2 d1 + 1 d2 + 1   ! ! 1 3 log(d1 +1)+t1 −t1 3 log(d2 +1)+t2 −1  c· +c· −1 , 2 2 2   ! ! ! 1 2 t1 3 log(d1 +d2 +2) 3 log(d1 +d2 +2) 2  c· + c· −1 , 2 3 2 3 2   ! 2t1 −1 + 2 3log(d1 +d2 +2) c· −1 ,  3 d1 + d2 + 2   3log(d1 +d2 +2) 3log(d+1)  c· −1 c· − 1, d1 + d2 + 2 d +1 where we use the fact that

2t1 −1 +2 3

 1, since 0 < t1 < 1. This completes the proof. 

Example 4.10 We define T (1) := R3 and T (n) := R3 (T (n − 1), T (n − 1), T (n − 1)) for any n" > 1. We claim that there exists a number c ∈ (1.62, 2] such that # 1 χ (T (n)) = c · (dept(T (n)) + 1)  −1 − 1 for any n  3 so that provided upper   bound in Theorem 4.9 is tight. Note that we have χ (T (n))  23 χ (T (n − 1)) by Lemma 4.8. In fact, we first show that the chromatic number  of T (n) exactly attains this bound. To verify that let χ (T (n − 1)) = r and k := 3r2 . Suppose otherwise that T (n) can be properly (k − 1)-colorable, and let κ : V (T (n)) → [k − 1] be such a coloring. We denote by Vi , the set of vertices of T (n) contained in the ith-component,

123

Z. Deniz

which induces T (n − 1) for each i ∈ [3], and define a multiset Bi := {κ(v) : v ∈ Vi }. If we set B := B1 ∪ B2 ∪ B3 , note that the multiplicity of each color in B is at most two, and we need  to have 2(k −1)  3r = |B| (up to the multiplicity) which  in turn implies  that 2 r2 −2  r , a contradiction. We therefore have χ (T (n)) = 23 χ (T (n − 1)) . We note that the integer sequence {χ (T (n)) : n  1} appears in the work of Odlyzko and Wilf [11] (which is also recorded in" the Sloane’s list [12] as A061419), and 3 n # , where c0 ≈ 1.62227. On the they have an exact formula χ (T (n)) = c0 · 2 other hand, we can easily compute the depth of T (n) following Corollary 4.6

n that so dept(T (n)) = 2 dept(T (n − 1)) + 1 = 2n − 1. Now, if we let c := c0 + 23 , we " # n # " 3 n = c · 2 − 1 . We therefore have c ∈ (1.62, 2] since n  3; hence, c0 · 23 conclude that ! % " # $ 1 3 n −1  c(dept(T (n)) + 1) −1 = c· − 1 = χ (T (n)), 2 where  =

ln 2 ln 3

as earlier.

Acknowledgments I would like to thank Professor Yusuf Civan for his invaluable comments and generous encouragement and also the referee for useful suggestions and comments that improved the presentation of this work.

References 1. Attali, D., Lieutier, A., Salinas, D.: Efficient data structure for representing and simplifying simplicial complexes in high dimensions. Int. J. Comput. Geom. 22, 279–303 (2012) 2. Berger, E., Choromanski, K., Chudnovsky, M., Fox, J., Loebl, M., Scott, A., Seymour, P., Thomass, S.: Tournaments and colouring. J. Comb. Theory Ser. B 103, 1–20 (2013) 3. Biyikoglu, T., Civan, Y.: Four-cycled graphs with topological applications. Ann. Comb. 16, 37–56 (2012) 4. Burzio, M., Demaria, D.C.: On simply disconnected tournaments. Ars Comb. 24, 149–161 (1987) 5. Burzio, M., Demaria, D.C.: Characterization of tournaments by coned 3-cycles. Acta Univ. Carol. Math. Phys. 28, 25–30 (1987) 6. Demaria, D.C., Kiihl, J.C.S.: On the complete digraphs which are simply disconnected. Publ. Math. 35, 517–525 (1991) 7. Ehrenborg, R., Hetyei, G.: The topology of the independence complex. Eur. J. Comb. 27, 906–923 (2006) 8. Hoppe, H.: Progressive meshes. Proc. 23rd Annual Conf. Computer Graphics and Interactive Techniques, pp. 99–108. ACM, New York (1996) 9. Marietti, M., Testa, D.: Cores of simplicial complex. Discrete Comput. Geom. 40, 444–468 (2008) 10. Matoušek, J.: Using the Borsuk–Ulam theorem. Lectures on Topological Methods in Combinatorics and Geometry. University text, Springer, Heidelberg (2003) 11. Odlyzko, A.M., Wilf, H.S.: Functional iteration and the Josephus problem. Glasgow Math. 33, 235–240 (1991) 12. Sloane, N.J.A.: The on-line encyclopedia of integer sequences. https://oeis.org

123