Arts & Sciences Events
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Sarah Loeb (William & Mary)
Access & Features
- Open to the public
Mathematics Colloquium and EXTREEMS-QED Lecture: Sarah Loeb (William & Mary)
Title: Fractional Separation Dimension
Abstract: Given a linear ordering \sigma of the vertices of a graph, say that a pair of non-incident edges is separated by \sigma if both vertices of one edge precede both vertices of the other. The separation dimension is the minimum
size of a set of vertex orders needed to separated every pair of non-incident edges. The t-separation dimension \pi_t(G) of a graph G is the minimum size of a multiset of vertex orders needed to separate every pair of non-incident edges of G t times. Finally, the fractional separation dimension \pi_f(G) of a graph G is \liminf_t \pi_t(G)/t.
While separation dimension can grow with the size of the graph, we show that the fractional separation dimension is at most 3 for every graph. Furthermore, equality holds if and only if G contains a complete graph on 4 vertices. On the
other hand, there is no sharper upper bound for graphs without K_4; we show the fractional separation dimension can be arbitrarily close to 3 in the family of complete balanced bipartite graphs. Our proofs use an interpretation of the fractional separation dimension as a matrix game.
This is joint work with Douglas West.