Szekeres proved in 1982 that the diameter (length of longest path) of a uniformly drawn labeled tree on n vertices normalized by the square root of n converges in distribution to an explicitly described distribution. This random tree is just a uniformly chosen spanning tree of the complete graph on n vertices. What if one changes the underlying graph from the complete graph to, say, the hypercube {0,1}^n, or an expander graph, or cubic lattices of fixed but high dimensions? Our result shows that one gets the same limiting distribution of the diameter. In fact much more is true: any reasonable "global" property of these random trees will have the same limiting distribution as a uniformly chosen labelled tree, moreover, these distributions can be explicitly described via Aldous' 1991 continuum random tree.
Joint work with Eleanor Archer and Matan Shalev.