Martin Rubey: An Unexpected Symmetry on Graphs
An Unexpected Symmetry on Graphs
Martin Rubey (University of Vienna)
(joint work with Florian Fürnsinn and Moritz Gangl)
Abstract: Hardly any natural bijections on unlabeled (connected, simple) graphs on a fixed number of vertices are known. In fact, we are not even aware of any non-trivial equidistributions of graph parameters. In this talk I will present a very natural symmetry on this set. More precisely, I will show that the maximum number of degree one vertices connected to a single vertex, and the maximum number of vertices sharing the same closed neighborhood, minus one, have joint symmetric distribution. This result generalizes works of Kilibarda and Gessel & Li. Our proof uses combinatorial species. Finding the involution that interchanges the two statistics remains an open problem.