Graphs of maximal complexity

Complexity of a graph is the number of its spanning trees. A change of basis in symmetric functions yields a graded description of graphs of maximal complexity in terms of traces of powers of the Laplacian, within the class of all graphs with a fixed number of vertices and edges. Vast classes of graphs, such as (up to complementation) strongly regular and distance regular graphs are shown to have maximal complexity. Recognizable among these are the Petersen, Platonic solids, Schlafli, Hoffman-Singleton, Mesner, Higman-Sims, Cameron graphs and many others. Symmetries of the Mesner and Higman-Sims graphs are associated with the Mathieu and Higman-Sims sporadic simple groups.