Events
DMS Combinatorics Seminar |
| Time: Feb 04, 2026 (01:00 PM) |
| Location: 328 Parker Hall |
|
Details:
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.
|