Thursday 24 September 2020, 12:45-13:15 via zoom
Stijn Cambie (RU)
Asymptotic resolution of a problem of Plesník
Fix \(d \ge 3\). We show the existence of a constant \(c>0\) such that any graph of diameter at most \(d\) has average distance at most \(d-c \frac{d^{3/2}}{\sqrt n}\), where \(n\) is the number of vertices. Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of \(c\). This constitutes an asymptotic solution to a longstanding open problem of Plesník.