Consider all possible forms of a digraph with 2 , 3 , 4 , … n vertices.Now let f(A) be the number of edges in A.Also, let A 2 be the transitive of A , A 3 the transitive of A twice, A 4 the transitive of A three times, and so on.Prove that f ( A ) , f ( A 2 ) , f ( A 3 ) … f ( A n ) converges to a single number, ie doesn't oscillate.

Question

Consider all possible forms of a digraph with   2  ,     3  ,     4  ,     …  n vertices.Now let f(A) be the number of edges in A.Also, let       A    2   be the transitive of   A  ,         A    3   the transitive of A twice,       A    4   the transitive of A three times, and so on.Prove that   f  (  A  )  ,     f  (      A    2    )  ,  f  (      A    3    )  …  f  (      A    n    ) converges to a single number, ie doesn&#039;t oscillate.

Zayden Dorsey · Accepted Answer

Step 1Let   G  =  (  V  ,  E  ) be a graph. Let&#039;s define the transitivity-operation as  f  (  (  V  ,  E  )  )  :=  (  V  ,      E    ′    ) , with       E    ′    :=  {  (  x  ,  y  )  ∈      V    2    ∣  ∃  a  ∈  V  :  (  x  ,  a  )  ,  (  a  ,  y  )  ∈  E  }The key property is that if      x    1    →      x    2    →  .  .  .  →      x    n  is a path in G, then      x    1    →      x    3    →  .  .  .  →      x          n      −      1      is a path in f(G).Let&#039;s call   x  →  y path connected, if there exists some path   x  →  yIf at some iteration a path connection   x  →  y is lost, then it is impossible to restore it.The path connection only is maintained into the next iteration if there is a path of even length from x to y.For a path connection   x  →  y to never be lost, one needs to be able to construct an arbitrarily long path from   x  →  y (in E) with even length. This is possible exactly if there&#039;s a path   x  →  y that passes through a circle with an odd number of vertices.An edge   x  →  y will exist permanently after some iteration exactly if we can create a path of length 2n for all   n  ≥  k for some k.Partial result: Any graph G without odd cycle has      lim          n      →      ∞        M  (      f    n    (  G  )  )  =  0Partial result:Let P be the adjacency matrix of the graph. Then we have  (      P    n        )          i      ,      j        &amp;gt;  0  ⇔      There&#039;s a path from           i         to           j         with length     nEspecially this means that   M  (  f  (      G    n    )  ) converges exactly if the number of zero-fields in Pn is at some point constant.

Answered question

Answer & Explanation

New Questions in Upper Level Math