Title: Separation Dimension of Graphs and Hyper Graphs
| Speaker: | L. Sunil Chandran |
| Affiliation: | Indian Institute of Science, Bangalore |
| Room: | MC 6486 |
Abstract:
The
separation
dimension
of
a
hyper
graph
G
is
the
smallest
natural
number
k for
which
the
vertices
of
G
can
be
embedded
in
R_k
such
that
any
pair
of disjoint
edges
in
G
can
be
separated
by
a
hyperplane
normal
to
one
of
the
axes. Equivalently,
it
is
the
smallest
possible
cardinality
of
a
family
F
of
total orders
of
the
vertices
of
G
such
that
for
any
two
disjoint
edges
of
G,
there exists
at
least
one
total
order
in
F
in
which
all
the
vertices
in
one
edge precede
those
in
the
other.
It
can
be
shown
that
the
separation
dimension
of
a hyper
graph
G
equals
the
boxicity
of
the
line
graph
of
G,
where
boxicity
of
a graph
H
is
defined
as
the
smallest
integer
d
such
that
H
can
be
represented
as the
intersection
graph
of
d-dimensional
axis
parallel
boxes.
In
this
talk
we discuss
the
relation
of
separation
dimension
with
various
other
graph
theoretic
parameters.
We
will
also
mention
some
of
the
recently
introduced
variants
of separation
dimension:
Induced
separation
dimension
(from
the
team
of
Martin Golumbic)
and
fractional
separation
dimension
(D.
B.
West
and
S.
Loeb).
Note: Sunil is visiting the Dept. on Monday Aug.8th, 2016 (arriving around 11am), and his office is room MC 5463.
Please feel free to meet up with him