A reminder: this is today.
-----------------------------------------------------
On 2025-10-19 11:06, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 23 October, given by Marek Skrzypczyk. Please find the talk details below.
Best regards, Misha Tyomkyn.
Antidirected paths in oriented graphs Marek Skrzypczyk Jagiellonian University
October 23, 2025, 12:20 in S6 Abstract
An antidirected path is an orientation of a path such that for each vertex v we have either d^-(v)=0 or d^+(v)=0. In this talk I will show that for any integer k > 3, every oriented graph with minimum semidegree bigger than k/2+\sqrt{k}/2 contains an antidirected path of length k. Consequently, every oriented graph on n vertices with more than (k+\sqrt{k})n edges contains an antidirected path of length k. This asymptotically proves the antidirected path version of a conjecture of Stein and of a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, respectively.
This is joint work with Andrzej Grzesik
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz