Unexpectedly, a Symmetry on Unlabeled Graphs
Florian Fürnsinn, Moritz Gangl, Martin Rubey · 2025
Read Unexpectedly, a Symmetry on Unlabeled Graphs by Florian Fürnsinn, Moritz Gangl, Martin Rubey (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03665.txt.
Introduction
Florian Furnsinn, Moritz Gangl, and Martin Rubey find a surprise symmetry between two measures on unlabeled graphs, in work from twenty twenty-five. The graphs are simple and connected, with labels stripped away. One measure counts the most leaves hanging off a single vertex.
The second measure counts the largest set of vertices that share the same closed neighborhood, minus one. The two measures turn out to share the exact same joint distribution across all such graphs of a fixed size. The authors call it the first natural case of its kind for unlabeled connected graphs. Their proof counts structures with species theory. A direct one to one swap between the measures stays an open problem.
Catalog record
| CREATOR | Florian Fürnsinn, Moritz Gangl, Martin Rubey |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-03665
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unexpectedly, a Symmetry on Unlabeled Graphs Florian Fürnsinn, Moritz Gangl, Martin Rubey Abstract . We exhibit the joint symmetric distribution of the following two parameters on the set of unlabeled simple connected graphs with n n vertices. The first parameter is the maximal number of leaves attached to a vertex. The second parameter is the size of the largest set of vertices sharing the same closed neighborhood minus 1 1 . Apparently, this is the first example of a natural non-trivial equidistribution of graph parameters on unlabeled simple connected graphs with a fixed set of vertices. Our proof is enumerative, using the theory of species. Exhibiting an explicit bijection interchanging the two parameters remains an open problem. 1. Introduction Symmetries are an essential part of human life. Some seem obvious to us now, such as the rotational symmetry of a wheel, or the reflective symmetry of a balance scale. Other symmetries, such as the symmetry between area and bounce on Dyck paths are still mysterious [ MR2371044 , Open Problem 3.11] . 1 1 1 Even in 2026, some people still ask why mirrors reflect horizontally but not vertically. In mathematical terms, a symmetry is a bijection on a set of objects. As the preceding example demonstrates, in some cases, we know about the existence of a symmetry but are unable to exhibit it explicitly. There are many known bijections on sets classically studied in combinatorics, such as permutations, integer partitions or Dyck paths. However, to the best of our knowledge 2 2 2 https://mathoverflow.net/questions/313532 , there is not a single known ‘natural’ bijection from the set of all unlabeled simple connected graphs with a given finite set of vertices to itself. Enlarging the domain to all graphs we are aware of taking the complement of a graph. Alternatively, we can restrict the domain to three-connected planar graphs and remove the constraint that the number of vertices is preserved. Then a celebrated result of Whitney shows that mapping a graph to its planar dual is an involution [ 10 , Thm. 11] . Of course, it is possible to modify these maps to obtain involutions preserving connectivity, but such a modification does not seem to be a very natural thing to do. In fact 3 3 3 https://mathoverflow.net/questions/312823 , we do not even know of any pair of ‘natural’ equidistributed parameters on unlabeled simple connected graphs appearing in the literature. This may be surprising, since many graph parameters have been considered and studied, albeit mostly in terms of inequalities satisfied among them. The www.findstat.org database, as of 2025, lists about 300 such statistics, without any conjectural equidistributions. Note that any equidistribution implies the existence of a bijection that maps one of the parameters to the other. Thus, our aim is to present a pair of non-trivial graph parameters which have the same distribution on the set of unlabeled simple connected graphs with a fixed number of vertices. We consider only finite simple graphs. A graph G consists of a set of vertices V(G) and a set of edges E(G) . Given a vertex v , the (open) neighborhood of v is the set \Nhd(v)\coloneqq\{u\in V(G)\mid u\text{ adjacent to }v\}, whereas the set \cNhd(v)\coloneqq\{v\}\cup\Nhd(v) is the closed neighborhood of v . Two vertices are siblings if they share the same closed neighborhood. Finally, a leaf or endpoint is a vertex of degree one. We consider the following two parameters on graphs. The sibling number s(G)\coloneqq\max_{v\in V(G)}\left\lvert\{u\in V(G)\setminus\{v\}\mid\cNhd(u)=\cNhd(v)\}\right\rvert is the maximal number of other vertices sharing the same closed neighborhood with any given vertex. The tuft number 4 4 4 www.findstat.org/St001826 t(G) is the maximal number of leaves adjacent to the same vertex. An unlabeled graph is an isomorphism class of graphs. Figure 1 displays all unlabeled connected graphs with four vertices, together with their sibling and tuft numbers. Among all graphs with n>2 vertices, the graph with maximal sibling number is the complete graph K_{n} , which has sibling number n-1 and tuft number 0 . On the other hand, the unique graph maximizing the tuft number is the star graph S_{n} , which has n-1 leaves adjacent to a single vertex, and no siblings. s(G)=0 t(G)=3 s(G)=0 t(G)=1 s(G)=0 t(G)=0 s(G)=1 t(G)=1 s(G)=1 t(G)=0 s(G)=3 t(G)=0 Figure 1 . Sibling and tuft numbers of all unlabeled connected graphs with 4 vertices. Our main theorem, initially conjectured by Per Alexandersson and the third author, exhibits a non-trivial equidistribution among graph parameters. Theorem 1 . The sibling number and the tuft number have joint symmetric distribution on the set of unlabeled connected graphs with n vertices. Put differently, the isomorphism type generating series \sum_{G}x^{s(G)}y^{t(G)} , where the sum is taken over all unlabeled connected graphs with n vertices, is symmetric in x and y . The sibling number and tuft number of a graph are the maximum sibling number and tuft number, respectively, of its connected components. Therefore, equidistribution of the parameters on connected graphs is a stronger property than equidistribution on the set of all graphs. The maximal number of vertices sharing the same open neighborhood and the tuft number do not have joint symmetric distribution. To illustrate Theorem 1 , the graphs with six vertices with sibling number 1 and tuft number 2 and those with sibling number 2 and tuft number 1 are displayed in Figure 2 . s(G)=1 t(G)=2 s(G)=1 t(G)=2 s(G)=2 t(G)=1 s(G)=2 t(G)=1 Figure 2 . The two unlabeled connected graphs with 6 vertices with sibling number 1 and tuft number 2 , and the two unlabeled connected graphs with 6 vertices with sibling number 2 and tuft number 1 . Graphs without siblings and graphs without vertices sharing the same open neighborhood were studied previously by several authors. Apparently, Sumner [ 9 ] was the first to formally introduce terminology. He calls a graph point determining if all of its vertices have distinct open neighborhoods, and point distinguishing if all of its vertices have distinct closed neighborhoods. He also notes that a graph is point distinguishing if and only if its complement is point determining. Bull and Pease [ 2 ] re-introduced point determining graphs as ‘mating graphs’, to describe possible mating types of biological species. They provide the number of unlabeled point determining graphs with at most ten vertices, and ask for a general formula. Soon after, such a formula was supplied by Read [ 8 ] , using the cycle index of graphs. Jovović 5 5 5 cf. comments in www.oeis.org/A004108 then observed that the number of unlabeled connected point determining graphs with n vertices coincides with the number of unlabeled connected leafless graphs with n vertices, if n\neq 2 . This was shown bijectively by Kilibarda [ 7 ] . A proof using combinatorial species building on Read’s idea was then provided by Gessel and Li [ 4 ] . In fact, they show the following. Theorem 2 (Kilibarda 2007, Gessel and Li 2011) . The number of unlabeled connected point determining graphs with n vertices, the number of unlabeled connected point distinguishing graphs with n vertices, and the number of unlabeled connected leafless graphs with n vertices, coincide for n\neq 2 . Gessel and Li used the language of combinatorial species