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.