The Small Quasikernel Conjecture

Series
Combinatorics Seminar
Time
Friday, September 20, 2024 - 3:15pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Sam Spiro – Rutgers University – sas703@scarletmail.rutgers.eduhttps://samspiro.xyz/
Organizer
Jiaxi Nie

Given a digraph D, we say that a set of vertices QV(D) is a quasikernel if Q is an independent set and if every vertex of D can be reached from Q by a path of length at most 2.  The Small Quasikernel Conjecture of P.L. Erdős and Székely from 1976 states that every n-vertex source-free digraph D contains a quasikernel of size at most 12n.  Despite being posed nearly 50 years ago, very little is known about this conjecture, with the only non-trivial upper bound of n14nlogn being proven recently by ourself.  We discuss this result together with a number of other related results and open problems around the Small Quasikernel Conjecture.