A Turán-type extremal problem for the number of spanning trees in $C_4$-free graphs

Source abstract

For a graph $F$, the Turán number \(\ex(n,F)\) is the maximum number of edges in an $F$-free graph on $n$ vertices. Let $q\ge 2$ be an integer and set $n=q^{2}+q+1$. Brown and Erdős, Rényi and Sós independently proved that $\ex(n,C_{4})\ge \frac12 q(q+1)^{2}$ for every prime power $q$, and Füredi subsequently established the upper bound $\frac12 q(q+1)^{2}$ for $\ex(n,C_{4})$ whenever $q\notin\{1, 7,9,11,13\}$. In this article, we prove that every $C_{4}$-free graph $G$ on $n$ vertices with at most $\frac12 q(q+1)^{2}$ edges satisfies $τ(G)\le n^{(n-3)/2}$, where $τ(G)$ denotes the number of spanning trees of $G$. In particular, for every prime power $q\notin\{7,9,11,13\}$, the above upper bound on $τ(G)$ is attained precisely by the orthogonal polarity graphs, thereby proving London's conjecture for all such $q$.