Line arrangements and geometric representations of graphs

Line arrangements and geometric representations of graphs

Tue, 14/02/2012
14:30 		Tobias Mueller, Amsterdam Combinatorial Theory Seminar Add to calendar L3
Line arrangements and geometric representations of graphs
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)