Preskoči na glavno vsebino

Martin Rubey: An Unexpected Symmetry on Graphs

Datum objave: 11. 1. 2025
Seminar za diskretno matematiko
torek
14
januar
Ura:
10.15
Lokacija:
Predavalnica 1.01 (Jadranska 21)

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.