Speaker: |
Kshitij Gajjar |

Organiser: |
Aditya Nema |

Date: |
Friday, 15 Jun 2018, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In this talk, we will prove Hansel's lemma using the probabilistic method, and follow it up with an application of the lemma to distance-preserving subgraphs. Specifically, we will show a separation between branching vertices and branching edges by exhibiting an interval graph on $n$ terminal vertices for which every distance-preserving subgraph has $O(n)$ branching vertices and $\Omega(n\log n)$ branching edges [joint work with Prof. Jaikumar].