Graph Theory and Combinatorics Seminar: Strong complete minors in digraphs
- Event Type
- Seminar/Symposium
- Sponsor
- N/A
- Virtual
- Date
- Mar 29, 2022 1:00 pm
- Speaker
- Maria Aksenovich (KIT)
- Contact
- Sean English
- Views
- 22
Kostochka and Thomason independently showed that any graph with average degree Omega (r sqrt{log r}) contains a K_r minor. We consider strong minors in digraphs and ways to force them. A strong →K_r minor is a digraph whose vertex set is partitioned into r parts such that each part induces a strongly-connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We show that any tournament with dichromatic number at least 2r contains a strong →K_r minor, and any tournament with minimum out-degree Omega(r sqrt{log r}) also contains a strong →K_r minor. The latter result is tight up to the implied constant, and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function f: N to N such that any digraph with minimum out-degree at least f(r) contains a strong →K_r minor, but such a function exists when considering dichromatic number.
This is a joint work with Antonio Girao, Richard Snyder, and Lea Weber.
For Zoom information, please contact Sean at SEnglish (at) illinois (dot) edu.