Sparsity

winter term 2017/18

Instructors

Classes

Lectures: | Mondays, 14^{15} - 15^{45}, room 4060 |

Tutorials: | Mondays, 16^{00} - 17^{30}, room 4060 |

Documents

Homeworks

Homework 1: | Measuring sparsity | Deadline: October 23^{rd} |

Homework 2: | Still measuring sparsity | Deadline: November 6^{th} |

Homework 3: | Generalized coloring numbers | Deadline: November 20^{th} |

Homework 4: | Other structural measures | Deadline: December 4^{th} |

Homework 5: | Uniform quasi-wideness | Deadline: December 18^{th} |

Homework 6: | VC dimension and polynomial expansion | Deadline: February 1^{st} |

Lecture notes

Chapter 1: | Measuring sparsity | (Lectures 1, 2, and 3) |

Chapter 2: | Structural measures | (Lectures 4, 5, 6, and 7) |

Chapter 3: | Uniform quasi-wideness | (Lectures 8, 9, and 10) |

Chapter 4: | An outlook on dense graphs | (Lectures 11 and 12) |

Chapter 5: | Polynomial expansion | (Lectures 13 and 14) |

Epilogue: | Sparsity in infinite graphs | (Lecture 15) |

Tutorials

Tutorial 1: | Measuring sparsity 1 | Selected solutions |

Tutorial 2: | Measuring sparsity 2 | Selected solutions |

Tutorial 3: | Measuring sparsity 3 | Selected solutions |

Tutorial 4: | Generalized coloring numbers 1 | Selected solutions |

Tutorial 5: | Generalized coloring numbers 2 | Selected solutions |

Tutorial 6: | Treedepth, treewidth | Selected solutions |

Tutorial 7: | DPs, neighborhood complexity | Selected solutions |

Tutorial 8: | Uniform quasi-wideness 1 | Selected solutions |

Tutorial 9: | Uniform quasi-wideness 2 | Selected solutions |

Tutorial 10: | Continuation of lecture plus homework | |

Tutorial 11: | Stability and VC dimension | Selected solutions |

Tutorial 12: | VC dimension and approximation | Selected solutions |

Tutorial 13: | Polynomial expansion | Selected solutions |

Tutorial 14: | Approximation schemes | Selected solutions |

Tutorial 15: | Sparsity in infinite graphs | Selected solutions |