Home /  EC Seminar: Erdős–Pósa of cycles that are far apart

Seminar

EC Seminar: Erdős–Pósa of cycles that are far apart May 06, 2025 (09:30 AM PDT - 10:30 AM PDT)
Parent Program:
Location: SLMath: Baker Board Room
Speaker(s) Vida Dujmovic (Unversity of Ottawa)
Description No Description
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video
No Video Uploaded
Abstract/Media

Zoom Link

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.

No Video Files Uploaded