Page 1

Displaying 1 – 10 of 10

Showing per page

Finite simple groups of Lie type as expanders

Alexander Lubotzky (2011)

Journal of the European Mathematical Society

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 S L 2 which is obtained by combining results of Selberg and Drinfeld via an explicit construction of Ramanujan graphs by Lubotzky, Samuels and Vishne.

Frucht’s Theorem for the Digraph Factorial

Richard H. Hammack (2013)

Discussiones Mathematicae Graph Theory

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

Alexander Grigor'yan, Rolando Jimenez, Yuri Muranov (2018)

Czechoslovak Mathematical Journal

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.

Currently displaying 1 – 10 of 10

Page 1