On the diameter of Eulerian orientations of graphs

ABSTRACT

We compare the diameter of a graph with the directed diameter of its Eulerian orientations. We obtain positive results under certain symmetry conditions.An Eulerian orientation of a graph is an orientation such that each vertex has the same indegree and outdegree. A graph is vertex-transitive if its vertices are equivalent under automorphisms.We show that the directed diameter of an Eulerian orientation of a finite vertex-transitive graph cannot be much larger than the undirected diameter; our bound on the directed diameter is O (dΔ ln n) where d is the undirected diameter, Δ is the (out)degree of the vertices, and n is the number of vertices. This implies that for Eulerian orientations of vertex-transitive graphs-of bounded degree, the gap between the two diameters is at most quadratic.As a consequence, we are able to compare the word length and the positive word length of elements of a finite group in terms of a given set of generators; we show that the gap is at most nearly quadratic, where the term "nearly" refers to a factor, polylogarithmic in the order of the group.It follows that recent polynomial bounds on the diameter of certain large classes of Cayley graphs of the symmetric group and certain linear groups automatically extend to directed Cayley graphs. The result also shows that the directed and undirected versions of long standing conjectures regarding the diameter of Cayley graphs of various classes of groups, including transitive permutation groups and finite simple groups, are equivalent.We also show that for edge-transitive digraphs, the directed diameter is O(d ln n).On the other hand, if we weaken the condition of vertex-transitivity to regularity (all vertices have the same degree), then the directed diameter is no longer polynomially bounded in terms of the undirected diameter and the maximum degree (and In n = O(d ln Δ)).Our upper bounds on the diameter raise the algorithmic challenge to find paths of the length guaranteed by these results. While for undirected graphs, most (but not all) relevant proofs are algorithmic, our bounds for the directed diameter are obtained via a pigeon-hole argument based on expansion and yield existence only.

REFERENCES

• 1: {Al} D. Aldous: On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probability in Engineering and Information Sciences 1 (1987), 33--46.
• 2: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 3: {Ba1} L. Babai: On the length of subgroup chains in the symmetric group. Communications in Algebra14 (1986), 1729--1736.
• 4: László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103440]
• 5: {Ba3} L. Babai: Asymptotic Inequality. Lecture Notes, 2005. http://people.cs.uchicago.edu/~laci/asymp
• 6: {BHKLS} L. Babai, G. Hetyei, W. M. Kantor, A. Lubotsky, Á. Seress: On the diameter of finite groups. in: Proc. 31st FOCS, IEEE Computer Society, 1990, pp. 857--865.
• 7: {BSz} L. Babai, M. Szegedy: Local Expansion of Symmetrical Graphs. Combinatorics, Probability and Computing 1 (1992), 1--11.
• 8: László Babai , Robert Beals , Ákos Seress, On the diameter of the symmetric group: polynomial bounds, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 9: {BE} L. Babai, P. Erdő: Representation of group elements as short products. In: "Theory and Practice of Combinatorics" (A. Rosa, G. Sabidussi, J. Turgeon eds.) Annals of Discrete Math.12 (1982), 27--30.
• 10: László Babai , Thomas P. Hayes, Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: László Babai , Ákos Seress, On the diameter of Cayley graphs of the symmetric group, Journal of Combinatorial Theory Series A, v.49 n.1, p.175-179, Sept. 1988 [doi>10.1016/0097-3165(88)90033-7]
• 12: László Babai , Ákos Seress, On the diameter of permutation groups, European Journal of Combinatorics, v.13 n.4, p.231-243, July 1992 [doi>10.1016/S0195-6698(05)80029-0]
• 13: {Dix} J. D. Dixon: The probability of generating the symmetric group. Math. Z.110 (1969), 199--205.
• 14: {EG} S. Even, O. Goldreich: The minimum length generator sequence is N P-hard. J. Algorithms 2 (1981), 311--313.
• 15: {He} H. A. Helfgott: Growth and Generation in SL2(Z/pZ). http://arxiv.org/abs/math/050924.
• 16: Mark R. Jerrum, The complexity of finding minimum-length generator sequences, Theoretical Computer Science, v.36 n.2-3, p.265-289, June 1985
• 17: {Ko} R. E. Korf: Finding optimal solutions to Rubik's Cube using pattern databases. In: Proc. 14th Nat. Conf. on Artificial Intelligence (AAAI-97), Amer. Assoc. for Artificial Intelligence, 1997, pp. 700--705.
• 18: {KMS} D. Kornhauser, G. L. Miller and P. Spirakis: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: Proc. 25th FOCS, IEEE Computer Society Press, 1986, pp. 292--302.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory