Time and Place: 22 September 2006, 10:00 am, KED
B015, University of
Ottawa
First speaker: Gabriel Verret,
University of
Ottawa
Title: Shifts in Cayley Graphs
Abstract:
An automorphism of a finite undirected simple graph is called a shift
if it maps every vertex to an adjacent one. A graph without a shift is
called shiftless. We consider which Cayley graphs have shifts, and
classify the finite groups by the type of shiftless Cayley graphs they
admit. In particular, we classify the groups on which all non-edgeless
Cayley graphs admit a shift.
Second speaker: Mateja Šajna, University of
Ottawa
Title: On Regular and
Vertex-Transitive Self-Complementary Hypergraphs
Abstract:
A k-uniform hypergraph (V,E) is
a collection E of k-subsets (called edges) of the vertex set
V. The complement of a k-uniform hypergraph (V,E) is the
k-uniform
hypergraph (V,E'), where E' is the complement
of E in the set of all k-subsets of V. A k-uniform
hypergraph X=(V,E) is called self-complementary
if it is isomorphic to its complement, t-subset-regular
if every t-subset of V lies in the same number
of elements of E, and vertex-transitive if the automorphism
group of X acts transitively on the vertex set V.
In
the
first part of this talk, we discuss some necessary
conditions
on the number of vertices of a t-subset-regular
self-complementary k-uniform hypergraph. These necessary
conditions
are known to be sufficient for graphs, that is, in the case
k=2. We show that they are also sufficient in the case t=1
and k=3; that is, we show that there exists a
1-subset-regular
self-complementary 3-uniform hypergraph of order n if
and only if n is congruent to 1 or 2 modulo 4.
In
the
second part of the talk we present some analogous results on
the
existence of vertex-transitive self-complementary uniform
hypergraphs
of certain orders and ranks.