max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | Erdos Posa Property in Digraphs |
---|---|

Speaker: | Saeed Amiri |

coming from: | Max-Planck-Institut für Informatik - D1 |

Speakers Bio: | I did my Ph.D at TU-Berlin, my thesis focus was on connecting and covering problems in Graphs, in particular, I worked on Erdos Posa-property, dominating sets in the distributed model of computation, disjoint paths and flow rerouting problems. Currently, I'm a postdoc fellow at MPII. |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1 We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Tuesday, 9 January 2018 |
---|---|

Time: | 13:00 |

Duration: | 30 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 024 |

In 1965 Erdos and Posa show that any graph either has many pairwise disjoint cycles or it has a small feedback vertex set. This is known as Erdos-Posa property.
There still is room for generalization for Erdos and Posa property. Let H be a fixed graph, is there any relation between the number of disjoint minor models of H in any graph G and the size of a minimum set which hits all minor models of H in G? |

Name(s): | Saeed Amiri |
---|---|

EMail: | samiri@mpi-in.mpg.de |

Video Broadcast: | No | To Location: |
---|

Keywords: | erdos posa property; digraphs; structural graph properties |
---|---|

Note: | This will be a very elementary talk on the topic, we just explain the problem statement and few ideas. It does not need any prerequisites and we are not going to any technical detail. However, if anyone is interested in the topic, I suggest the following papers to take a look at it: 1. Last section of Graph Minor V: http://www.sciencedirect.com/science/article/pii/0095895686900304 2. P. Erdos and L. Pósa. On independent circuits contained in a graph. ˝ Canadian Journal of Mathematics, 1965. 3. https://arxiv.org/abs/1603.02504 The latter has not been updated for a while, I could hand in my thesis which includes this papaer in more details and it is more accurate, so if you want please don't hesitate and just email me. |

Attachments, File(s): |

Created: | Saeed Amiri, 01/05/2018 01:07 PM |

Last modified: | Uwe Brahm/MPII/DE, 01/09/2018 04:01 AM |

- Saeed Amiri, 01/05/2018 01:20 PM
- Saeed Amiri, 01/05/2018 01:07 PM -- Created document.