Title: Erdös-Rényi Graphs
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
These
might
not
be
the
Erdös-Rényi
graphs
you
first
thought
of. Let
V
be
a
3-dimensional
vector
space
over
a
field
of
odd
order
q.
The
vertices
of
the
Erdös-Rényi
graph
are
the
1-dimensional
subspaces
of
V
and
the
subspaces
spanned
by
non-zero
vectors
x
and
y
are
adjacent
if
xT
y
=
0.
Under
this
definition,
exactly
q
+
1
vertices
of
the
graph
have
loops,
and
we
usually
deal
with
these
loops
by
deleting
them;
the
resulting
simple
graph
we
denote
by
ER(q).
Classically
these
graphs
ER(q)
are
of
interest
because
they
have
have
no
4-cycles
and,
given
this,
the
maximum
possible
number
of
edges.
More
recently,
Mancinska
and
Roberson
showed
that
the
cone
over
ER(3)
had
chromatic
number
5
and
quantum
chromatic
number
4,
and
they
suspect
that
this
is
the
smallest
example
where
these
parameters
differ.
I
will
give
an
introduction
to
the
properties
of
these
graphs,
including
their
spectra.
(No
vertices
will
be
coloured
or
quantum
coloured
in
the
course
of
the
lecture.)