Events

DMS Combinatorics Seminar

Time: Feb 04, 2026 (01:00 PM)
Location: 328 Parker Hall

Details:

spiro 

Speaker: Sam Spiro  (Georgia State University) 

Title: The Small Quasikernel Conjecture

 
Abstract: Given a digraph \(D\), we say that a set of vertices \(Q\subseteq V(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 Szemerédi from 1976 states that every \(n\) -vertex source-free digraph \(D\) contains a quasikernel of size at most \(\frac{1}{2}n\).  Despite being posed nearly 50 years ago, very little is known about this conjecture, with the only non-trivial upper bound of \(n-\frac{1}{4}\sqrt{n\log n}\) being proven very recently by ourself.  We discuss this together with a number of other related results and open problems around the Small Quasikernel Conjecture.