Expansion and random walks in : II
Expansion in finite simple groups of Lie type
We show that random Cayley graphs of finite simple (or semisimple) groups of Lie type of fixed rank are expanders. The proofs are based on the Bourgain-Gamburd method and on the main result of our companion paper [BGGT].
Expansion in , square-free
Let be a fixed symmetric finite subset of that generates a Zariski dense subgroup of when we consider it as an algebraic group over by restriction of scalars. We prove that the Cayley graphs of with respect to the projections of is an expander family if ranges over square-free ideals of if and is an arbitrary numberfield, or if and .
Explicit Cayley covers of Kautz digraphs.
Extending the dual of the Petersen graph.
Extensions of Foster's averaging formula to infinite networks with moderate growth.
Fast Fourier analysis for over a finite field and related numerical experiments.
Finite planar vertex-transitive graphs of the regularity degree three
Finite simple groups of Lie type as expanders
We prove that all finite simple groups of Lie type, with the exception of the Suzuki groups, can be made into a family of expanders in a uniform way. This confirms a conjecture of Babai, Kantor and Lubotzky from 1989, which has already been proved by Kassabov for sufficiently large rank. The bounded rank case is deduced here from a uniform result for which is obtained by combining results of Selberg and Drinfeld via an explicit construction of Ramanujan graphs by Lubotzky, Samuels and Vishne.
Finite Vertex-Transitive Planar Graphs of the Regularity Degree Four or Five
Fixing numbers of graphs and groups.
Fixpunkteigenschaften von automorphismen spezieller, endlicher, ebener, dreifach-knotenzusammenhängender graphen
Free inverse semigroups
Front-divisors of trees.
Frucht’s Theorem for the Digraph Factorial
To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms a group,...
Fundamental groupoids of digraphs and graphs
We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.
-Invariant tensors and graphs
We describe a correspondence between -invariant tensors and graphs. We then show how this correspondence accommodates various types of symmetries and orientations.
Generalized graph cordiality
Hovey introduced A-cordial labelings in [4] as a simultaneous generalization of cordial and harmonious labelings. If A is an abelian group, then a labeling f: V(G) → A of the vertices of some graph G induces an edge-labeling on G; the edge uv receives the label f(u) + f(v). A graph G is A-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. Research on A-cordiality...
Generalized Hantzsche-Wendt flat manifolds.
We study the family of closed Riemannian n-manifolds with holonomy group isomorphic to Z2n-1, which we call generalized Hantzsche-Wendt manifolds. We prove results on their structure, compute some invariants, and find relations between them, illustrated in a graph connecting the family.
Graph Cohomology, Colored Posets and Homological Algebra in Functor Categories
The homology theory of colored posets, defined by B. Everitt and P. Turner, is generalized. Two graph categories are defined and Khovanov type graph cohomology are interpreted as Ext* groups in functor categories associated to these categories. The connection, described by J. H. Przytycki, between the Hochschild homology of an algebra and the graph cohomology, defined for the same algebra and a cyclic graph, is explained from the point of view of homological algebra in functor categories.