Subgraph counting problems

Kitty Meeks (University of Glasgow)

Monday 10th November, 2014 16:00-17:00 Maths 326

Abstract

Given a graph on n vertices, what can we say about the number of k-vertex subgraphs having a particular property, when k is much smaller than n?  Are there efficient algorithms to count the number of k-vertex subgraphs that have the desired property?  I will give an overview of the situations in which we do and do not know good answers to these questions, and also of the methods involved, which give rise to some beautiful connections between extremal combinatorics and computational complexity.  My hope is that the audience will help me identify further connections to geometry and topology! This talk will not assume any specialist knowledge, and should be accessible to a general mathematical audience.

Add to your calendar

Download event information as iCalendar file (only this event)