Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Gregory 307
- Date
- Apr 16, 2024 1:00 pm
- Speaker
- Karthik Chandrasekaran
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 56
- Originating Calendar
- Combinatorics Research Area Calendar
Speaker: Karthik Chandrasekaran (UIUC)
Title: Approximate version of Woodall’s conjecture
Abstract:
In a digraph, a dicut is a partition of the vertices into two non-empty parts such that all arcs crossing the partition do so in one direction. A dijoin is a subset of arcs that contains at least one arc from every dicut. By definition, the maximum number of arc disjoint dijoins is at most the minimum size of a dicut. Woodall (1976) conjectured that these two quantities are equal. In this talk, we will prove an approximate version of Woodall’s conjecture: max number of arc disjoint dijoins is at least (1/6) min size of a dicut. The talk will be based on a recent paper due to Cornuejols, Liu, and Ravi: https://arxiv.org/pdf/2311.04337.pdf.