ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 14 (2018) 445-454 https://doi.org/10.26493/1855-3974.1107.1c8 (Also available at http://amc-journal.eu) A note on extremal results on directed acyclic graphs Alvaro Martinez-Perez * Departamento de Análisis Económico y Finanzas, Universidad de Castilla-La Mancha, Avda. Real Fabrica de Seda, s/n. 45600 Talavera de la Reina, Toledo, Spain Luis Montejano Deborah Oliveros * Instituto de Matematicas, Universidad Nacional Autonoma de México, Area de la Investigation Científica, Circuito Exterior, C.U., Coyoacan 04510, Mexico D.F., Mexico Received 17 May 2016, accepted 31 May 2017, published online 6 February 2018 This paper studies the maximum number of edges of a Directed Acyclic Graph (DAG) with n vertices in terms of it's longest path £. We prove that in general this number is the Turan number t(n, l +1), the maximum number of edges in a graph with n vertices without a clique of size £ +2. Furthermore, we find the maximum number of edges in a DAG which is either reduced, strongly reduced or extremely reduced and we relate this extremal result with the family of intersection graphs of families of boxes with transverse intersection. Keywords: Directed graphs, Turan numbers, intersection graphs of families of boxes. Math. Subj. Class.: 05C20, 52C99 1 Introduction One of the fundamental results in extremal graph theory is the Theorem of Turan (1941) which states that a graph with n vertices that has more than t(n, k) edges, will always contain a complete subgraph of size k + 1. The Turan graph T(n, k), is a k-partite graph on n vertices whose partite sets are as nearly equal in cardinality, and has the property * Partially supported by MTM 2015-63612P. t Supported by CONACyT 166306. * Partially supported by PAPIIT 104915 and CONACyT 166306. E-mail address: alvaro.martinezperez@uclm.es (Alvaro Martinez-Perez), luis@matem.unam.mx (Luis Montejano), dolivero@matem.unam.mx (Deborah Oliveros) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 446 Ars Math. Contemp. 14 (2018) 267-284 that contains the maximum posible number of edges t(n, k) of any graph not containing a clique of size k + 1. It is known that t(n, k) < (1 - 2)\, and equality holds if k divides n. In fact, tnfr = 1 - m. See [1]. Turan numbers for several families of graphs have been studied in the context of extremal graph theory, see for example [3] and [4]. In ([2, 7]) the authors analyze, among other things, the intersection graphs of boxes in Rd proving that, if T(n, k, d) denotes the maximal number of intersection pairs in a family F of n boxes in Rd with the property that no k + 1 boxes in F have a point in common (with n > k > d > 1), then T(n, k, d) = T(n - k + d, d) + T(n, k - d +1,1), with T(n, k, 1) = (n2) - (n-2+1) being the precise bound in dimension 1 for the family of interval graphs. Turan numbers have played and important role for several variants of the Turan Theorem and its relation with the fractional Helly Theorem (see [5, 6]). The purpose of this paper is to study the maximum number of edges in directed acyclic graphs with n vertices with respect to it's longest path. That turns out to be related with the extremal behavior of the family of intersection graphs for a collection of boxes in R2 with transverse intersection. The first result, Theorem 2.10, states that in a directed acyclic graph with n vertices, if the longest path has length then the maximal number of edges is the Turan number t(n, I +1). Theorem 3.19 and its Corollaries state that given a directed acyclic graph G with n vertices such that the longest path has length I, then if G is either reduced, strongly reduced or extremely reduced, G has at most t(n - I + 1,2) + T(n, 1) edges, where again T(n, 1) denotes the maximal number of intersecting pairs in a family F of n intervals in R with the property that no I +1 intervals in F have a point in common. In fact, this bound is best possible. The bound is reached by the intersection graph of a collection of boxes in R2 with transverse intersection (see Proposition 4.6). This graph is extremely reduced (and thus is also strongly reduced and reduced, see Proposition 4.4). 2 Directed acyclic graphs By a directed acyclic graph, DAG, we mean a simple directed graph without directed cycles. A DAG, G = (V, 5), with vertex set V and directed edge set E is transitive if for every x, y, z G V, if {x, y}, {y, z} G E then {x, z} G 5. Definition 2.1. A topological order of a directed graph G is an ordering O of its vertices {v1, v2,..., vn} so that for every edge {vj, Vj} then i < j. The following proposition is a well known result: Proposition 2.2. A directed graph G is a DAG if and only if G has a topological order. Given any set X, by |X | we denote the cardinal of X. Definition 2.3. The indegree, deg- (v), of a vertex v is the number of directed edges {x, v} with x G V. The outdegree, deg+ (v), of a vertex v is the number of directed edges {v, x} with x g V. Notice that each directed edge {v, w} adds one outdegree to the vertex v and one indegree to the vertex w. Therefore, J2veV deg+ (v) = J2veV deg- (v) = | (5) |. The degree of a vertex is deg(v) = deg (v) + deg+(v). A. Martinez-Perez et al.: A note on extremal results on directed acyclic graphs 447 Definition 2.4. A vertex v such that deg (v) =0 is called source. A vertex v such that deg+(v) =0 is called sink. It is well known that every DAG G has at least one source and one sink. Definition 2.5. Given a DAG, G = (V, £), a directed path 7 in G is a sequence of vertices {v0,..., vn} such that {vi-1, vj} G £ for every 1 < i < n. Here, 7 has length n, and endpoint vn. Observe that since DAG's are acyclic, all the vertices on a directed path are different. Definition 2.6. Given a DAG, G = (V, £), let r: V ^ N be such that r(v) = k if there exists a directed path 7 in G of length k with endpoint v and there is no directed path 7' with endpoint v and length greater than k. Definition 2.7. Given a DAG, G = (V, £) suppose that i = max{k | r(v) = k for every v G V}. Notice that, since G has no directed cycle, i < |V|. Then, let us define a partition Pr = {V0,..., V«} of V such that Vj := {v G V | r(v) = i} for every 0 < i < i. Notice that V0 is exactly the set of sources in G and V is contained in the set of sinks in G. Lemma 2.8. V is nonempty for every 0 < i < i. Proof. Let {v0,..., v«} be a directed path of maximal length in G. Clearly, for every 0 < i < i, vj G Vj if j < i. Suppose vj G Vj with i < j < i. Then, there is a directed path {v0,..., vj = vj} with j > i and {v0,..., vj, vj+1,..., v«} is a directed path with length j + l - i > i which contradicts the hypothesis. □ Lemma 2.9. The induced subgraph with vertices Vj, G[Vj], is independent (has no edges) for every i. Proof. Let vj, vj G Vj and suppose {vj, v'} G £. Let {v0,..., vj} be apath of length i with endpoint v j. Then, {v0,..., v j, v'} defines a directed path of length i +1 which contradicts the fact that v' G Vj. □ Recall that T(n, i) denote the i-partite Turan graph with n vertices and t(n, i) denote the number of edges of T(n, i). Theorem 2.10. Let G = (V, £) be a DAG with n vertices such that the longest directed path has length i. Then, G has at most t(n, i + 1) edges. Proof. Consider the partition Pr = {V0,..., V^} of V. By Lemma 2.9, this defines an (i+1) -partite directed graph. Thus, neglecting the orientation we obtain a complete (i+1) -partite graph with partition sets V0,..., V^. Therefore, the number of edges is at most t(n,i +1). □ Remark 2.11. It is readily seen that the bound in Theorem 2.10 is best possible. Consider the Turan graph T(n, i +1) and any ordering of the i +1 independent sets V0,..., V«. Then, for every edge {vj, vj} in T(n, i) with vj G Vj, vj G Vj and i < j let us assume the orientation {vj, vj}. It is trivial to check that the resulting graph is a DAG with t(n, i +1) edges. 448 Ars Math. Contemp. 14 (2018) 267-284 3 Reduced, strongly reduced and extremely reduced DAGs Let O be a topological ordering in a DAG G. Given any two vertices v, w, and two directed paths in G, 7,7', from v to w, let us define 7 UO 7' as the sequence of vertices defined by the vertices in 7 U 7' in the order given by O. Of course, this need not be, in general, a directed path from v to w. Let r(u, v) be the set of all directed paths from u to v. Let UO{7 | 7 € r(u, v)} represent the sequence of all the vertices from the paths in r(u, v) ordered according to O. Definition 3.1. A finite DAG G is strongly reduced if for any topological ordering O of G, every pair of vertices, v, w, and every pair of directed paths, 7,7', from v to w, then 7 UO 7' defines a directed path from v to w. Remark 3.2. Let G be DAG. Given any two vertices v, w, and two directed paths in G, 7,7', from v to w, let us define 7 < 7' if every vertex in 7 is also in 7'. Clearly, "<" is a partial order. Definition 3.3. A vertex w is reachable from a vertex v if there is a directed path from v to w. Proposition 3.4. Given a finite DAG G = (V, E), the following properties are equivalent: i) For every pair of vertices v, w and every pair of paths, 7,7', from v to w, there exists a directed path from v to w, 7'', such that 7,7' < 7''. ii) For every pair of vertices v, w such that w is reachable from v, there is a directed path from v to w, ym , such that for every directed path, 7, from v to w, 7 < ym . iii) For every topological ordering O of G and any pair of vertices v, w, UO {7 | 7 € r(u, v)} defines a directed path from v to w. Proof. Since the graph is finite and the relation '<' is transitive, i) and ii) are trivially equivalent. If ii) is satisfied, then it is trivial to see that UO{7 | 7 € r(u, v)} = ym and iii) is satisfied. Also, it is readily seen that iii) implies ii) taking ym := UO{7 | 7 € r(u, v)}. □ Definition 3.5. We say that a finite DAG G is reduced if it satisfies any of the properties from Proposition 3.4. Proposition 3.6. If a finite DAG G is strongly reduced, then G is reduced. Proof. Since the graph is finite, it is immediate to see that being strongly reduced implies iii). □ Remark 3.7. The converse is not true. The graph in the left from Figure 1 is clearly reduced. Notice that the directed path ym := {vi, v2, v3, v4, v5} is an upper bound for every directed path from v1 to v5. However, if we consider the directed paths 7 = {v1, v2, v5} and 7' = {v1, v4, v5} with the topological order O = {v1, v2, v3, v4, v5}, then 7 UO 7' = {v1, v2, v4, v5 } which is not a directed path. A. Martinez-Perez et al.: A note on extremal results on directed acyclic graphs 449 Figure 1: Being reduced does not imply being strongly reduced and being strongly reduced does not imply being extremely reduced. Definition 3.8. Given a finite DAG G and a vertex v G V we say that w is an ancestor of v if there is a directed path {w = v0,..., vk = v} and w is a descendant of v if there is a directed path {v = v0,..., vk = w}. Definition 3.9. We say that a finite DAG G is extremely reduced if for every pair of non-adjacent vertices x, y, if x, y have a common ancestor, then they do not have a common descendant. Proposition 3.10. If a DAG G = (V, £) is extremely reduced, then it is strongly reduced. Proof. Let 7 = {v, vi,..., vn, w} and 7' = {v, w0,..., wm, w} be two directed paths in G from v yo w. Let O be any topological order in G and consider 7UO 7' = {v, z1,..., zk, w}. First, notice that z1 is either v1 or w1. Therefore, {v, z1} G £. Also, zk is either vn or wm, and {zk, w} G £. Now, for every 1 < i < k, let us see that {zi_1, zj G £. If zi-1,zi G y or zi_1, zi G 7', then they are consecutive vertices in a directed path and we are done. Otherwise, since zi-1, zi have a common ancestor v and a common descendant w, then there is a directed edge joining them and, since zi-1, zi are sorted by a topological order, {zi-1, zi} G £. □ Remark 3.11. The converse is not true. The graph in the right from Figure 1 is strongly reduced. However, vertices w2 and w4 are not adjacent and have a common ancestor and a common descendent. Proposition 3.12. If G is transitive, then the following properties are equivalent: • G is extremely reduced, • G is strongly reduced, • G is reduced. Proof. By Proposition 3.10 if (5 is extremely reduced, then it is strongly reduced. By Proposition 3.6, if G is strongly reduced, then it is reduced. Suppose G is reduced and suppose that two vertices x, y have a common ancestor, v, and a common descendant, w. Then, there are two directed paths 7,7' from v to w such 450 Ars Math. Contemp. 14 (2018) 267-284 that x G y and y G y'- By property i) in Proposition 3.4, there exists a path 7" in G from v to w such that 7,7' < 7''. Inparticular, x, y G 7''. Therefore, either x is reachable from y or y is reachable from x in G. Since G is transitive, this implies that x, y are adjacent. Therefore, G is extremely reduced. □ Definition 3.13. Given a DAG G = (V, ?), the graph with vertex set V and edge set 5' := 5 U {{v, w} | w is reachable from v} is called the transitive closure of G, T[G]. It is immediate to check the following: Proposition 3.14. Given any DAG G, T [G] is transitive. Proposition 3.15. If a DAG G is reduced, then the transitive closure T [G ] is also reduced. Proof. Suppose G satisfies i) in Proposition 3.4 and let 7 = {v = v0,..., vn = w}, 7' = {v = w0,..., wm = w} be any pair of paths from v to w in T[G]. Therefore, vj is reachable from vj_i in G for every 1 < i < n and wj is reachable from wj_i in G for every 1 < i < m. Thus, there exist a path y0 in G such that 7 < y0 and a path y0 in G such that y' < y0. By property i), there is a directed path from v to w such that y0, y0 < y0'-Therefore, 7,7' < y0' and T[G] satisfies i). □ Then, from Propositions 3.6, 3.10, 3.12, 3.14 and 3.15: Corollary 3.16. If a DAG G is reduced, then the transitive closure T [G] is extremely reduced and strongly reduced. In particular, if G is extremely reduced or strongly reduced, then T [G] is extremely reduced and strongly reduced. Let us recall that t(„,U)=(;;) - (n-2+1)=(n - <+i)(i - D+i^)^ (3.1) As it was proved in [7]: Lemma 3.17. For n > i and d > 1, T(n + d, i, 1) - T(n, i, 1) = d(i - 1). In particular, T(n + 2, i, 1) - T(n, i, 1) = 2(i - 1). Also, from [7]: Lemma 3.18. For 1 < d < n, t(n + d, d) - t(n, d) = (d - 1)n + ^ In particular, t(n + 2, 2) - t(n, 2) = n +1. Theorem 3.19. Let G = ( V, ?) be a DAG with n vertices and such that the longest directed path has length i > 1. If G is extremely reduced, then G has at most t(n - i +1, 2) + T(n, i, 1) edges. A. Martinez-Perez et al.: A note on extremal results on directed acyclic graphs 451 Proof. Let us prove the result by induction on n. Suppose that the longest directed path has length £. First, let us see that the result is true for n = £ +1 and n = £ + 2. If n = £ +1 then G has at most = (£-2)2(£-1) + 2(£ - 1) + 1 = T(n, £, 1) + t(n - £ +1,2) edges. The last equation follows immediately from (3.1) and the fact that t(2, 2) = 1. If n = £ +2 then there are £ +1 vertices which define a directed path y = {v0,..., v^} and one vertex w such that neither {w, v0} nor {v^, w} is a directed edge. Then, the partition Pr = {V0,..., V^} of G satisfies that vj G Vj for every 0 < i < £. Also, w G Vj for some 0 < j < £ and {w, vj}, {vj, w} are not directed edges. Hence, deg(w) < £. Therefore, G has at most ^f11 + £ = (£-2)2(£-1) + 3(£ - 1) + 2 = T(n, £, 1) + t(n - £ + 1, 2) edges. The last equation follows immediately from (3.1) and the fact that t(3,2) = 2. Suppose the induction hypothesis holds when the graph has n vertices and let #(V) = n + 2. Also, by Proposition 3.15 we may assume that the graph is transitive. Consider the partition Pr = {V0,..., V^} of V. Let #(Vj) = r». Let v G V0 and w be any sink of G. Consider any pair of vertices vj, v- G Vj. Since G is extremely reduced and every two vertices in Vj are non-adjacent, v», vj can not be both descendants of v and ancestors of w simultaneously. Hence, the number of edges joining the sets {v, w} and Vj are at most rj + 1. Therefore, there are at most n + £ - 1 edges joining {v, w} and G \ {v,w} Since G \ {v, w} has n vertices, by hypothesis, it contains at most t(n - £ +1, 2) + T(n, £, 1) edges. Finally, there is at most 1 edge in the subgraph induced by {v, w}. Therefore, by Lemmas 3.17 and 3.18, |E(G) | < t(n - £ +1, 2) + T(n, £, 1) + n + £ = t(n - £ +3, 2)+ T(n + 2, £, 1). □ By Corollary 3.16 we know that the extremal graph for reduced and strongly reduced graphs is transitive. Thus, from Theorem 3.19 and Proposition 3.12 we obtain the following. Corollary 3.20. Let G = (V, 5) be a DAG with n vertices and such that the longest directed path has length £ > 1. If G is reduced, then G has at most t(n - £ +1, 2) + T(n, £, 1) edges. Corollary 3.21. Let G = (V,5) be a DAG with n vertices and such that the longest directed path has length £ > 1. If G is strongly reduced, then G has at most t(n - £ + 1, 2) + T(n, £, 1) edges. 4 Directed intersection graphs of boxes Definition 4.1. Let R be a collection of boxes with parallel axes in R2. Let G = (V,5) be a directed graph such that V = R and given R, R' gR with R = I x J, R' = I' x J' then {R, R'} G 5 if and only if I c I' and J' C J (i.e. there is an edge if and only if the intersection is transverse and the order is defined by the subset relation in the first coordinate). Let us call G the directed intersection graph of R. Definition 4.2. Let R be a collection of boxes with parallel axes in R2. We say that R is a collection with transverse intersection if for every pair of boxes either they are disjoint or their intersection is transverse. 452 Ars Math. Contemp. 14 (2018) 267-284 R=|xJ R'=I J' I Figure 2: The transverse intersection above induces a directed edge {R, R'}. J Proposition 4.3. Let R be a collection of boxes with parallel axes in R2 and G be the induced directed intersection graph. If two vertices v, w have both a common ancestor and a common descendant in G, then the corresponding boxes Rv, Rw intersect. Proof. Let a be a common ancestor and Ra = Ia x Ja be the corresponding box. Let b be a common descendant and Rb = Ib x Jb be the corresponding box. Then if Rv = Iv x Jv, Rw = Iw x Jw are the boxes corresponding to v and w respectively, it follows by construction that Ia C Iv ,Iw and Jb C Jv, Jw. Therefore, Ia x Jb c Rv ,Rw and Rv n Rw = 0. □ Proposition 4.4. If R is a collection of boxes with parallel axes in R2 with transverse intersection, then the induced directed intersection graph G is extremely reduced and transitive. Proof. First notice that the transitivity holds simply by the transverse intersection property. Let v, w be two vertices such that there is no edge joining them. This means, by construction, that their corresponding boxes do not have a transverse intersection. Since R has transverse intersection, this implies that these boxes do not intersect. Thus, by Proposition 4.3, if v, w have a common ancestor, then they can not have a common descendant. □ Remark 4.5. Consider the bipartite graph G from Figure 3 with the partition given by {letters, numbers} and assume all directed edges go from letters into numbers. Note that G is extremely reduced, transitive and acyclic. Notice that the induced subgraphs given by the sets Ci := {1, 2, A, B}, C2 := {3,4, C, D} and C3 := {5, 6, E, F} are three cycles of length 4. Furthermore the induced subgraph given by the set of vertices {1, 2,3,4,8, 9, A, B, C, D, H, I} is realizable as boxes in R2 (see Figure 4) note, that contains C1 and C2 and its realization force one of them to be inside the other say C1 inside C2. Similarly the induced subgraphs given by the set of vertices {1, 2, 5,6, A, B, E, F, 7,12, G, L} and the set of vertices {3,4,5,6, C, D, E, F, 10,11, J, K} forces necessarily a system of tree squares one inside the other. However, intervals given by {7,8,9,10,11,12} and {G, H, I, J, K, L} are forced to have more intersections that those given by the graph. In A. Martinez-Perez et al.: A note on extremal results on directed acyclic graphs 453 Figure 3: The bipartite, transitive, and extremely reduced DAG, G with partition given by {letters, numbers} and edges directed from letters into numbers. This graph is not realizable as a family of boxes in R2. other words, there is no family of boxes (or intervals) that realizes such a graph or for which it is induced the graph G. Then, the converse of Proposition 4.4 is not true. - 3 — H — 9 1 1 1 D 8 1 C 1 2 1 A I B 4 Figure 4: Realization in R2 of the induced subgraph with vertices {1,2,3,4, 8,9, A, B, C, D, H, I} of the graph shown in Figure 3. Let G[r, l, s] be the graph, G(V, E), such that: • V = {xi, . . . ,Xr ,yi, . . . , yi-1 ,Z1, . . . ,Zs} • {xj, xj} E for any i = j, • {zi,Zj} i Efor any i = j, • {xi,yj} i Efor every i,j, • {yi, yj } i Efor every i < j, • {yi,Zj } i Efor every i,j, • {xi, Zj} i E for every i, j. This is the directed intersection graph from the collection of boxes in Figure 5. 454 Ars Math. Contemp. 14 (2018) 267-284 C, Cm 1 | 1 | B B Vo V, V,., V, Figure 5: The graph G[r, l, s] corresponds to the directed intersection graph of the collection in the figure where Xj ~ Aiy yj ~ Cj and zk ~ Bk. Notice that the graph is transitive although not every edge is represented in the figure. By Proposition 4.4, G[r, l, s] is a transitive extremely reduced DAG. In particular, G[r,l, s] is strongly reduced and reduced. Now, to prove that the bound obtained in Theorem 3.19 and its corollaries is best possible, it is immediate to check the following: Proposition 4.6. If n -t is even, G[^,t, ^] has t(n -t +1,2) + T(n, t, 1) edges. If n - t is odd, G[,t, ] has t(n - t+ 1, 2) + T(n, t, 1) edges. References [1] M. Aigner and G. M. Ziegler, Proofs from THE BOOK, Springer-Verlag, Berlin, 1998, doi: 10.1007/978-3-662-22343-7. [2] I. Barany, F. Fodor, A. Martinez-Perez, L. Montejano, D. Oliveros and A. P6r, A fractional Helly theorem for boxes, Comput. Geom. 48 (2015), 221-224, doi:10.1016/j.comgeo.2014.09.007. [3] B. Bollobas, Extremal Graph Theory, Dover Publications, Mineola, New York, 2004. [4] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer-Verlag, Berlin, 3rd edition, 2005, http://diestel-graph-theory.com/. [5] G. Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984), 161-174, doi:10.1007/ bf02761162. [6] M. Katchalski and A. Liu, A problem of geometry in Rn, Proc. Amer. Math. Soc. 75 (1979), 284-288, doi:10.2307/2042758. [7] A. Martinez-Perez, L. Montejano and D. Oliveros, Extremal results on intersection graphs of boxes in Rd, in: K. Adiprasito, I. Barany and C. Vilcu (eds.), Convexity and Discrete Geometry Including Graph Theory, Springer, volume 148 of Springer Proceedings in Mathematics & Statistics, pp. 137-144, 2016, doi:10.1007/978-3-319-28186-5_11, papers from the conference held in Mulhouse, September 7 - 11, 2014.