Seminar
Parent Program: | |
---|---|
Location: | SLMath: Baker Board Room |
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
We establish the following theorem: There exists functions 𝑓,𝑔:ℕ→ℕ such that for all nonnegative integers 𝑘 and 𝑑, for every graph 𝐺, either 𝐺 contains 𝑘 cycles where the distance between each pair of cycles is greater than 𝑑, or there exists a subset 𝑋 of vertices of 𝐺 with |𝑋|≤𝑓(𝑘) such that every cycle in 𝐺 is within distance 𝑔(𝑑) of some vertex in 𝑋. The theorem answers a question by Chudnovsky and Seymour, and independently by Ahn, Gollin, Huynh, and Kwon. This is joint work with Gwenaël Joret, Piotr Micek and Pat Morin.