Fault Tolerance of Cayley Graphs

It is a difficult problem in general to decide whether a Cayley graph Cay(G; S) is connected where G is an arbitrary finite group and S a subset of G. For example, testing primitivity of an element in a finite field is a special case of this problem but notoriously hard. In this paper, it is shown that if a Cayley graph Cay(G; S) is known to be connected then its fault tolerance can be determined in polynomial time in |S|log(|G|). This is accomplished by establishing a new structural result for Cayley graphs. This result also yields a simple proof of optimal fault tolerance for an infinite class of Cayley graphs, namely exchange graphs. We also use the proof technique for our structural result to give a new proof of a known result on quasiminimal graphs. Received March 10, 2006     

Strongly regular Cayley graphs from partitions of subdifference sets of the Singer difference sets

In this paper, we give a new lifting construction of “hyperbolic” type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference sets of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to m-ovoids and i-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.     

On Cayley graphs of rectangular groups

In this paper, we first give a characterization of Cayley graphs of rectangular groups. Then, vertex-transitivity of Cayley graphs of rectangular groups is considered. Further, it is shown that Cayley graphs Cay(S,C) which are automorphism-vertex-transitive, are in fact Cayley graphs of rectangular groups, if the subsemigroup generated by C is an orthodox semigroup. Finally, a characterization of vertex-transitive graphs which are Cayley graphs of finite semigroups is concluded.     

The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.     

The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings

In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of coherent mixed subdivisions of a Minkowski sum ?₁+...+? _r of point configurations and of coherent polyhedral subdivisions of the associated Cayley embedding ?(?₁,...,? _r ). In this paper we extend this correspondence in a natural way to cover also non-coherent subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos. Received February 18, 1999 / final version received January 25, 2000?Published online May 22, 2000     

On a combinatorial method for counting smooth numbers in sets of integers

In this paper we develop a method for determining the number of integers without large prime factors lying in a given set S. We will apply it to give an easy proof that certain sufficiently dense sets A and B always produce the expected number of “smooth” sums a+b, a∈A, b∈B. The proof of this result is completely combinatorial and elementary.     

Vertex-transitive graphs that are not Cayley graphs. II

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. Marus˘ic˘ asked, “For what values of n does there exist such a graph on n vertices?” We give several new constructions of families of vertex-transitive graphs that are not Cayley graphs and complete the proof that, if n is divisible by p² for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p², p³, or 12. © 1996 John Wiley & Sons, Inc.     

Cayley graphs and automatic sequences

We study those automatic sequences which are produced by an automaton whose underlying graph is the Cayley graph of a finite group. For 2-automatic sequences, we find a characterization in terms of what we call homogeneity, and among homogeneous sequences, we single out those enjoying what we call self-similarity. It turns out that 2-self-similar sequences (viewed up to a permutation of their alphabet) are in bijection with many interesting objects, for example dessins d’enfants (covers of the Riemann sphere with three points removed). For any p, we show that, in the case of an automatic sequence produced “by a Cayley graph,” the group and indeed the automaton can be recovered canonically from the sequence. Further, we show that a rational fraction may be associated with any automatic sequence. To compute this fraction explicitly, knowledge of a certain graph is required. We prove that for the sequences studied in the first part, the graph is simply the Cayley graph that we start from, and so calculations are possible. We give applications to the study of the frequencies of letters.     

A note on shifted convolution of cusp-forms with $$\theta $$-series

Recently Lachterman, Schayer, and Younger published an elegant proof of the Ramanujan congruences for the partition function p(n). Their proof uses only the classical theory of modular forms as well as a beautiful result of Choie, Kohnen, and Ono, without the need for Hecke operators. In this paper, we give a method for generalizing Lachterman, Schayer, and Younger’s proof to include Ramanujan congruences for multipartition functions \(p_k(n)\) and Ramanujan congruences for p(n) modulo certain prime powers.     

Cayley digraphs with normal adjacency matrices

In this paper we give a criterion for the adjacency matrix of a Cayley digraph to be normal in terms of the Cayley subset S. It is shown with the use of this result that the adjacency matrix of every Cayley digraph on a finite group G is normal iff G is either abelian or has the form for some non-negative integer n, where Q₈ is the quaternion group and is the abelian group of order 2ⁿ and exponent 2.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

Infinite Hamiltonian paths in Cayley digraphs

Let Cay(S:H) be the Cayley digraph of the generators S in the group H. A one-way infinite Hamiltonian path in the digraph G is a listing of all the vertices [ν_i:1⩽i<∞], such that there is an arc from ν_i to ν₁₊₁. A two-way infinite Hamiltonian path is similarly defined, with i ranging from −∞ to ∞. In this paper, we give conditions on S and H for the existence of one- and two-way infinite Hamiltonian paths in Cay(X:H). Two of our results can be summarized as follows. First, if S is countably infinite and H is abelian, then Cay(S:H) has one- and two-way Hamiltonian paths if and only if it is strongly connected (except for one infinite family). We also give necessary and sufficient conditions on S for Cay(S:H) to be strongly connected for a large class of Cayley digraphs. Second, we show that any Cayley digraph of a countable locally finite group has both one- and two-way infinite Hamiltonian paths. As a lemma, we give a relation between the strong connectivity and the outer valence of finite vertex-transitive digraphs.     

Integral Cayley graphs over dihedral groups

In this paper, we give a necessary and sufficient condition for the integrality of Cayley graphs over the dihedral group \(D_n=\langle a,b\mid a^n=b^2=1,bab=a^{-1}\rangle \). Moreover, we also obtain some simple sufficient conditions for the integrality of Cayley graphs over \(D_n\) in terms of the Boolean algebra of \(\langle a\rangle \), from which we find infinite classes of integral Cayley graphs over \(D_n\). In particular, we completely determine all integral Cayley graphs over the dihedral group \(D_p\) for a prime p.     

Singular sets of planar hyperbolic billiards are regular

Many planar hyperbolic billiards are conjectured to be ergodic. This paper represents a first step towards the proof of this conjecture. The Hopf argument is a standard technique for proving the ergodicity of a smooth hyperbolic system. Under additional hypotheses, this technique also applies to certain hyperbolic systems with singularities, including hyperbolic billiards. The supplementary hypotheses concern the subset of the phase space where the system fails to be C ² differentiable. In this work, we give a detailed proof of one of these hypotheses for a large collection of planar hyperbolic billiards. Namely, we prove that the singular set and each of its iterations consist of a finite number of compact curves of class C ² with finitely many intersection points.     

t-Balanced Cayley maps of dihedral groups

A Cayley map is an embedding of a Cayley graph where the cyclic ordering of generators around every vertex is the same. The involution indicating the position of mutually inverse generators in the cyclic ordering is called the distribution of inverses of a Cayley map. The Cayley maps whose distribution of inverses is linear (modulo the degree of the map) with 'slope' t are called t-balanced. An exponent of a Cayley map is a number e with the property that, roughly speaking, the Cayley map is isomorphic to its 'e-fold rotational image'.In the contribution we present results related to the construction of t-balanced Cayley maps which are not regular and do not have t as an exponent.     

On loxodromic actions of Artin–Tits groups

Artin–Tits groups act on a certain delta-hyperbolic complex, called the “additional length complex”. For an element of the group, acting loxodromically on this complex is a property analogous to the property of being pseudo-Anosov for elements of mapping class groups. By analogy with a well-known conjecture about mapping class groups, we conjecture that “most” elements of Artin–Tits groups act loxodromically. More precisely, in the Cayley graph of a subgroup G of an Artin–Tits group, the proportion of loxodromically acting elements in a ball of large radius should tend to one as the radius tends to infinity. In this paper, we give a condition guaranteeing that this proportion stays away from zero. This condition is satisfied e.g. for Artin–Tits groups of spherical type, their pure subgroups and some of their commutator subgroups.     

On normal 2-geodesic transitive Cayley graphs

We investigate connected normal 2-geodesic transitive Cayley graphs Cay(T,S). We first prove that if Cay(T,S) is neither cyclic nor K_4[2], then 〈a〉?{1}??S for all a∈S. Next, as an application, we give a reduction theorem proving that each graph in this family which is neither a complete multipartite graph nor a bipartite 2-arc transitive graph, has a normal quotient that is either a complete graph or a Cayley graph in the family for a characteristically simple group. Finally we classify complete multipartite graphs in the family.     

A Simple Proof of Dieudonn-Manin Classification Theorem

The Dieudonn-Manin classification theorem on φ-modules (φ-isocrystals) over a perfect field plays a very important role in p-adic Hodge theory. In this note, in a more general setting we give a new proof of this result, and in the course of the proof, we also give an explicit construction of the Harder-Narasimhan filtration of a φ-module.