In 1975, P. Erd\H os proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast}(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast}(n)$. Let $mc(n)$ be the maximum cycle length for all $G \in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\leq \frac{15}{16}n.$ \par We make the following conjecture: \par \bigskip \noindent{\bf Conjecture.} $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$

In this paper, we prove a CLT for the sample canonical correlation coefficients between two high-dimensional random vectors with finite rank correlations. More precisely, consider two random vectors $\wt{\bx}=\mathbf x + A \mathbf z $ and $\wt{\by}=\mathbf y + B \mathbf z $, where $\mathbf x \in \R^p$, $\mathbf y \in \R^q$ and $\mathbf z\in \R^r$ are independent random vectors with i.i.d.\;entries of mean zero and variance one, and $A \in \R^{p\times r}$ and $B\in \R^{q\times r}$ are two arbitrary deterministic matrices. Given $n$ samples of $\wt{\bx}$ and $\wt{\by}$, we stack them into two matrices $\cal X= X+AZ$ and $\cal Y= Y+BZ$, where $X\in \R^{p\times n}$, $Y\in \R^{q\times n}$ and $Z\in \R^{r\times n}$ are random matrices with i.i.d.\;entries of mean zero and variance one. Let $\wt\lambda_1 \ge \wt\lambda_2\ge \cdots \ge \wt\lambda_{r}$ be the largest $r$ eigenvalues of the sample canonical correlation (SCC) matrix $\cal C_{\cal X\cal Y}=(\cal X\cal X^\top)^{-1/2}\cal X\cal Y^\top (\cal Y\cal Y^\top)^{-1}\cal Y \cal X^\top (\cal X\cal X^\top)^{-1/2}$, and let $t_1\ge t_2 \ge \cdots\ge t_r$ be the squares of the population canonical correlation coefficients between $\wt{\bx}$ and $\wt{\by}$. Under certain moment assumptions, we show that there exists a threshold $t_c \in(0, 1)$ such that if $t_i>t_c$, then \smash{$\sqrt{n} (\wt\lambda_i-\theta_i)$} converges weakly to a centered normal distribution, where $\theta_i $ is a fixed outlier location determined by $t_i$. Our proof uses a self-adjoint linearization of the SCC matrix and a sharp local law on the inverse of the linearized matrix.

Consider two random vectors $\wt{\bx} \in \R^p$ and $\wt{\by} \in \mathbb R^q$ of the forms $\wt{\bx}=A \mathbf z + \bC_1^{1/2}\mathbf x $ and $\wt{\by}=B \mathbf z + \bC_2^{1/2}\mathbf y $, where $\mathbf x \in \R^p$, $\mathbf y \in \R^q$ and $\mathbf z\in \R^r$ are independent random vectors with i.i.d. entries of zero mean and unit variance, $\bC_1$ and $\bC_2$ are $p \times p$ and $q\times q$ deterministic population covariance matrices, and $A$ and $B$ are $p \times r$ and $q\times r$ deterministic factor loading matrices. With $n$ independent observations of $(\wt{\mathbf x},\wt{\mathbf y})$, we study the sample canonical correlations between $\wt{\bx} $ and $\wt{\by}$. We consider the high-dimensional setting with finite rank correlations, that is, ${p}/{n}\to c_1$ and ${q}/{n}\to c_2$ as $n\to \infty$ for some constants $c_1\in (0,1)$ and $c_2\in (0,1-c_1)$, and $r$ is a fixed integer. Let $t_1\ge t_2 \ge \cdots\ge t_r\ge 0$ be the squares of the nontrivial population canonical correlation coefficients between $\wt {\bx}$ and $\wt{\by}$, and let $\wt\lambda_1 \ge \wt\lambda_2\ge \cdots \ge \wt\lambda_{p\wedge q}\ge 0$ be the squares of the sample canonical correlation coefficients. If the entries of $\mathbf x$, $\mathbf y$ and $\mathbf z$ are i.i.d. Gaussian, then the following dichotomy has been shown in \cite{CCA} for a fixed threshold $t_c \in(0, 1)$: for any $1\le i \le r$, if $t_i < t_c$, then $\wt\lambda_i$ converges to the right-edge $\lambda_+$ of the limiting eigenvalue spectrum of the sample canonical correlation matrix, and moreover, $n^{2/3}(\wt\lambda_i-\lambda_+)$ converges weakly to the Tracy-Widom law; if $t_i>t_c$, then $\wt\lambda_i$ converges to a deterministic limit $\theta_i \in (\lambda_+, 1)$ that is determined by $c_1$, $c_2$ and $t_i$. In this paper, we prove that these results hold universally under the sharp fourth moment conditions on the entries of $\mathbf x$, $\mathbf y$ and $\mathbf z$. Moreover, we prove the results in full generality, in the sense that they also hold for near-degenerate $t_i$'s and for $t_i$'s that are close to the threshold $t_c$. Finally, we also provide almost sharp convergence rates for the sample canonical correlation coefficients under a general $a$-th moment assumption.

We consider Green's functions $G(z):=(H-z)^{-1}$ of Hermitian random band matrices $H$ on the $d$-dimensional lattice $(\Z/L\Z)^d$. The entries $h_{xy}=\overline h_{yx}$ of $H$ are independent centered complex Gaussian random variables with variances $s_{xy}=\mathbb E|h_{xy}|^2$, which satisfy a banded profile so that $s_{xy}$ is negligible if $|x-y|$ exceeds the band width $W$. For any fixed $n\in \N$, we construct an expansion of the $T$-variable, $T_{xy}=|m|^2 \sum_{\alpha}s_{x\alpha}|G_{\alpha y}|^2$, with an error $\OO(W^{-nd/2})$, and use it to prove a local law on the Green's function. This $T$-expansion was the main tool to prove the delocalization and quantum diffusion of random band matrices for dimensions $d\ge 8$ in part I \cite{PartI_high} of this series.

We consider Hermitian random band matrices $H=(h_{xy})$ on the $d$-dimensional lattice $(\Z/L\Z)^d$. The entries $h_{xy}$ are independent (up to Hermitian conditions) centered complex Gaussian random variables with variances $s_{xy}=\mathbb E|h_{xy}|^2$. The variance matrix $S=(s_{xy})$ has a banded structure so that $s_{xy}$ is negligible if $|x-y|$ exceeds the band width $W$. In dimensions $d\ge 8$, we prove that, as long as $W\ge L^\e$ for a small constant $\e>0$, with high probability most bulk eigenvectors of $H$ are delocalized in the sense that their localization lengths are comparable to $L$. Denote by $G(z)=(H-z)^{-1}$ the Green's function of $H$. For $\im z\gg W^2/L^2$, we also prove a widely used criterion in physics for quantum diffusion of this model, namely, the leading term in the Fourier transform of $\E|G_{xy}(z)|^2$ with respect to $x-y$ is of the form $(\im z + a(p))^{-1}$ for some $a(p)$ quadratic in $p$, where $p$ is the Fourier variable. Our method is based on an expansion of $T_{xy}=|m|^2 \sum_{\alpha}s_{x\alpha}|G_{\alpha y}|^2$ and it requires a self-energy renormalization up to error $W^{-K}$ for any large constant $K$ independent of $W$ and $L$. We expect that this method can be extended to non-Gaussian band matrices.