Home /  EC Seminar:The Small Quasi-kernel Conjecture

Seminar

EC Seminar:The Small Quasi-kernel Conjecture April 15, 2025 (11:00 AM PDT - 12:00 PM PDT)
Parent Program:
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Speaker(s) Sam Spiro (Rutgers University)
Description No Description
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video
No Video Uploaded
Abstract/Media

Zoom Link

Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a quasi-kernel 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 Quasi-kernel Conjecture of P.L.\ Erd\H{o}s and Sz\'ekely from 1976 states that every $n$-vertex source-free digraph $D$ contains a quasi-kernel 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 recently by ourself.  We discuss this result together with a number of other related results and open problems around the Small Quasi-kernel Conjecture.

No Notes/Supplements Uploaded No Video Files Uploaded