Seminar series
Date
Tue, 14 Feb 2012
Time
14:30 -
15:30
Location
L3
Speaker
Tobias Mueller, Amsterdam
A dot product representation of a graph assigns to each vertex $s$ a vector $v(s)$ in ${\bf R}^k$ in such a way that $v(s)^T v(t)$ is greater than $1$ if and only $st$ is an edge. Similarly, in a distance representation $|v(s)-v(t)|$ is less than $1$ if and only if $st$ is an edge.
I will discuss the solution of some open problems by Spinrad, Breu and Kirkpatrick and others on these and related geometric representations of graphs. The proofs make use of a connection to oriented pseudoline arrangements.
(Joint work with Colin McDiarmid and Ross Kang)