Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdos raised the problem of determining $f(n)$ (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). Given a graph $H$, what is the maximum number of edges of a graph with $n$ vertices not containing $H$ as a subgraph? This number is denoted $ex(n,H)$, and is known as the Turan number. Erdos conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\geq cn^{1+1/k}$(see P. Erdos, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , pp. 97--109, Academic Press, London, 1971). Haj\'{o}s conjectured that every simple even graph on $n$ vertices can be decomposed into at most $n/2$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236 ). We present the problems, conjectures related to these problems and we summarize the know results.

Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. Erd\"{o}s raised the problem of determining $f(n)$. Erd\"{o}s conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\geq cn^{1+1/k}$. Haj\'{o}s conjecture that every simple even graph on $n$ vertices can be decomposed into at most $n/2$ cycles. We present the problems, conjectures related to these problems and we summarize the know results. We do not think Haj\'{o}s conjecture is true.

Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle. Fix 0<α<1. Let N_α(d) denote the maximum number of lines through the origin in R^d with pairwise common angle arccos α. Let k denote the minimum number (if it exists) of vertices in a graph whose adjacency matrix has spectral radius exactly (1−α)/(2α). If k<∞, then N_α(d)= ⌊ k(d−1)/(k−1) ⌋ for all sufficiently large d, and otherwise N_α(d)=d+o(d). In particular, N_{1/(2k−1)}(d)= ⌊ k(d−1)/(k−1) ⌋ for every integer k≥2 and all sufficiently large d. A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity.

No abstract uploaded!

By studying the heat semigroup, we prove Li-Yau type estimates for bounded and positive solutions of the heat equation on graphs, under the assumption of the curvature-dimension inequality $CDE'(n,0)$, which can be consider as a notion of curvature for graphs. Furthermore, we derive that if a graph has non-negative curvature then it has the volume doubling property, from this we can prove the Gaussian estimate for heat kernel, and then Poincar\'{e} inequality and Harnack inequality. As a consequence, we obtain that the dimension of space of harmonic functions on graphs with polynomial growth is finite, which original is a conjecture of Yau on Riemannian manifold proved by Colding and Minicozzi. Under the assumption of positive curvature on graphs, we derive the Bonnet-Myers type theorem that the diameter of graphs is finite and bounded above in terms of the positive curvature by proving some Log Sobolev inequalities.