The last paper of Catherine Rényi and Alfréd Rényi: Counting k-Trees

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

{{n} \choose {k}}(k(n-k)+1)^{n-k-2}.

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 k-1 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 k-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 k-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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

This entry was posted in Combinatorics, People and tagged , , . Bookmark the permalink.

8 Responses to The last paper of Catherine Rényi and Alfréd Rényi: Counting k-Trees

    • Jon Awbrey says:

      It was Trees and Parentheses and Catalans that drew me into the Wonderland of Combinatorics, and coding and counting that drew me deeper, from Prüfer codes to Gödel codes to Riffs and Rotes, from trees to cacti to a calculus for differential logic.

  1. igorpak says:

    When working on our paper with Gorodezky, we tried about a dozen different notions of “hypertrees” before settling on a directed version which was the only definition where Wilson’s LERW generalized. These different notions are assembled in §10.2 in our paper, more as an indication of past frustration than anything else.

  2. Gil Kalai says:

    Regarding the Prufer sequence itself. Suppose that the root is the k-clique {1,2,…,k}. when you grow the k-tree from the root (or direct every k+1 clique from a vertex towards the root) every new vertex x (there are n-k new vertices) contributes k k-cliques that we can order according to the ordering on 1,2,…,n. and call them x^1,\dots , x^k. when we delete the smallest leave like in Prufer code it is contained in a unique (k+1)-clique and thus describes a k-clique x^j that we add to the sequence. This is the generalized Prufer code and we can determine the tree back from the sequence.

  3. Alexander Woo says:

    Here is another generalization of these formulas that I would like:

    Take any of the basically equivalent combinatorial constructions of the irreducible representations of the symmetric group. (For example, take the polynomials from Specht’s paper.) These constructions create some number of elements in the representation, and then there is some straightening procedure to show that a certain subset of these elements forms a basis.

    Instead of privileging this basis, we can instead study the matroid given by all of the original elements. (John Wiltshire-Gordon, Magdalena Zajaczkowska and I tried to do this in arXiv:1701.05277)

    Now we might want to count the number of bases of this matroid! (For every ordering of {1,…,n}, there is a basis given by the young tableaux that are standard with respect to this ordering, but there are even more bases.)

    When the representation is the one associated to a hook, then the bases of this matroid are in fact precisely the spanning k-dimensional hypertrees on an n-simplex, so the answer (with appropriate weights) was given by Professor Kalai. (John Wiltshire-Gordon and I independently observed this not long after writing our paper.) As far as I know, no one has worked on the other partitions.

    • Gil Kalai says:

      Dear Alexander, this is a very exciting connection and question. Maybe one should count certain filtrations of simplicial complexes which somehow respect the associated diagram.

  4. Gil Kalai says:

    Let me also mention that Dominique Foata gave in 1971 a beautiful proof for the formula for the number of k-trees.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s