A k-tree is a graph obtained as follows: A clique with k vertices is a k-tree. A k-tree with n+1 vertices is obtained from a k-tree with n-vertices by adding a new vertex and connecting it to all vertices of a k-clique. There is a beautiful formula by Beineke and Pippert (1969) for the number of k-trees with n labelled vertices. Their number is
If we count rooted k-trees where the root is a k-clique the formula becomes somewhat simpler.
In 1972, when I was a teenage undergraduate student I was very interested in various extensions of Cayley’s formula for counting labeled trees. I thought about the question of finding a Prüfer code for k-trees and how to extend the results by Beineke and Pippert when for every clique of size in the k-tree we specify its “degree”, namely, the number of k-cliques containing it. (I will come back to the mathematics at the end of the post.) I thank Miki Simonovits for the photos and description and very helpful comments.
Above, Kató Renyi, Paul Turan, Vera Sós, and Paul Erdős ; below Kató, Vera, and Lea Schönheim. Pictures: Jochanan (Janos) Schönheim.
From right, Rényi, Turán and Erdős and Grätzer.
While I was working on enumeration of -trees I came across a paper by Catherine Rényi and Alfréd Rényi that did everything I intended to do and quite a bit more.
What caught my eye was a heartbreaking footnote: when the paper was completed Catherine Rényi was no longer alive.
The proceedings where the paper appeared were of a conference in combinatorics in Hungary in 1969. This was the first international conference in combinatorics that took place in Hungary. The list of speakers consists of the best combinatorialists in the world and many young people including Laci Lovasz, Laci Babai, Endre Szemeredi, and many more who since then have become world-class scientists.
Years later Vera Sós told me the story of Alfréd Rényi’s lecture at this conference, the first international conference in combinatorics that took place in Hungary: “Kató died on August 23, on the day of arrival of the conference on “Combinatorial Theory and its Applications” (Balatonfured, August 24-29). Alfréd Renyi gave his talk (with the same title as the paper) on August 27 and his talk was longer than initially scheduled. They proved the results in the paper just the week before the conference. The paper appeared in the proceedings of the conference.”
Alfréd Renyi was one of the organizers of the conference and also served as one of the editors of the proceedings of the conference, which appeared in 1970. A few months after the conference, on February 1, 1970 Alfréd Rényi died of a violent illness. The proceedings are dedicated to the memory of Catherine Rényi and Alfréd Rényi.
Two pictures showing Alfréd and Catherine Rényi and a picture of Alfred Rényi and Paul Erdős.
Repeating a picture from last-week post. From left: Sándor Szalai, Catherine Rényi, Alfréd Rényi, András Hajnal and Paul Erdős (Matrahaza)
Going back to my story. I was 17 at the time and naturally I wondered if counting trees and similar things is what I want to do in my life. Shortly afterwards I went to the army. Without belittling the excitement of the army I quickly reached the conclusion that I prefer to count trees and to do similar things. My first result as a PhD student was another high dimensional extension of Cayley’s formula (mentioned in this post and a few subsequent posts). The question of how to generalize both formulas for -trees and for my hypertrees is still an open problem. We know the objects we want to count, we know what the outcome should be, and we know that we can cheat and use weighted counting, but still I don’t know how to make it work.
Some more comments on k-trees:
- Regarding the degree sequences for k-trees. You cannot specify the actual (k-2)-faces because those (in fact just the graph) determines the k-tree completely. So you need to count rooted k-trees and to specify the (k-2)-faces in terms of how they “grew” from the root.
- The case that all degrees are 1 and 2 that correspond to paths for ordinary trees and to triangulating polygons with diagonals for 2-trees are precisely the stacked (k-1)-dimensional polytopes. This is a special case of the Renyi & Renyi formula that was also found, with a different proof, by Beineke and Pippert.
- It is unlikely that there would be a matrix-tree formula for k-trees since telling if a graph contains a 2-tree is known to be NP complete. See this MO question. Maybe some matrix-tree formulas are available when we start with special classes of graphs.
- Regarding the general objects – those are simplicial complexes that are Cohen-Macaulay and their dual (blocker) is also Cohen-Macaulay.
This post is just about a single paper of Catherine Rényi and Alfréd Rényi mainly through my eyes from 45 years ago. Catherine Rényi’s main interest originally was Number theory, she was a student of Turàn, and soon she became interested in the theory of Complex Analytic Functions. Alfréd Rényi was a student of Frigyes Riesz and he is known for many contributions in number theory, graph theory and combinatorics and primarily in probability theory. Alfréd Rényi wrote several papers about enumeration of trees, and this joint paper was Catherine Rényi ‘s first paper on this topic.