| [home] - [up] |
Abstract: How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic number. This solution is widely believed to be optimal. We show, however, that it is exponentially far from optimal by giving explicit constructions with an overhang of Omega(n^{1/3}). We also prove some upper bounds on the overhang that can be achieved. Joint work with Mike Paterson.
Colloquium - 16 Uhr s.t.
Abstract: A graph G = (V,E) is an intersection graph of pseudosegments in the plane IG(PS) if there exists a set of pseudosegments PS of this kind such that V=PS and two vertices v,w in V are adjacent if and only if the corresponding pseudosegments pv and pw intersect exactly once and no three pseudosegments do have a common point.
With reference to the representation itself, a direct question is wether all interval graphs INT were in IG(PS). It can easily be shown that they are a subclass of IG(PS). This leads us to the class of chordal graphs CH and I will show that chordal graphs CH and intersection graphs of pseudosegments IG(PS) do not contain each other.
For the investigation of the set of graphs, that chordal graphs and intersection graphs of pseudosegments IG(PS) do have in common, observe that chordal graphs can be characterised as vertex intersection graphs of subtrees of a tree, denoted by VTT. A graph G is in VTT if there exists a set of subtrees of a tree such that every vertex corresponds to a subtree and two vertices are adjacent if and only if the corresponding subtrees share a vertex in T. According to this characterisation, interval graphs INT form the subclass VPP, where each vertex corresponds to a subpath of path P.
I will show, that the subclass VPT of chordal graphs, i.e. the class of vertex intersection graphs of subpaths in a tree T, is also a subclass of intersection graphs of pseudosegments in the plane IG(PS).