W&M Featured Events

Location

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.

This Event Appears On

• W&M Featured Events
• Arts & Sciences Events
• Mathematics Events