Seminar
Parent Program: | |
---|---|
Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
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