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!

Szemerédi's regularity lemma and its variants are some of the most powerful tools in combinatorics. In this paper, we establish several results around the regularity lemma. First, we prove that whether or not we include the condition that the desired vertex partition in the regularity lemma is equitable has a minimal effect on the number of parts of the partition. Second, we use an algorithmic version of the (weak) Frieze–Kannan regularity lemma to give a substantially faster deterministic approximation algorithm for counting subgraphs in a graph. Previously, only an exponential dependence for the running time on the error parameter was known, and we improve it to a polynomial dependence. Third, we revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for several co-NP-complete problems. We show how to use the weak Frieze–Kannan regularity lemma to approximate the regularity of a pair of vertex subsets. We also show how to quickly find, for each ε′>ε, an ε′-regular partition with k parts if there exists an ε-regular partition with k parts. Finally, we give a simple proof of the permutation regularity lemma which improves the tower-type bound on the number of parts in the previous proofs to a single exponential bound.

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.

Persistent homology is constrained to purely topological persistence, while multiscale graphs account only for geometric information. This work introduces persistent spectral theory to create a unified low-dimensional multiscale paradigm for revealing topological persistence and extracting geometric shapes from high-dimensional datasets. For a point-cloud dataset, a filtration procedure is used to generate a sequence of chain complexes and associated families of simplicial complexes and chains, from which we construct persistent combinatorial Laplacian matrices. We show that a full set of topological persistence can be completely recovered from the harmonic persistent spectra, that is, the spectra that have zero eigenvalues, of the persistent combinatorial Laplacian matrices. However, non-harmonic spectra of the Laplacian matrices induced by the filtration offer another powerful tool for data analysis, modeling, and prediction. In this work, fullerene stability is predicted by using both harmonic spectra and non-harmonic persistent spectra, while the latter spectra are successfully devised to analyze the structure of fullerenes and model protein flexibility, which cannot be straightforwardly extracted from the current persistent homology. The proposed method is found to provide excellent predictions of the protein B-factors for which current popular biophysical models break down.

The spectral radius of a graph is the largest eigenvalue of the adjacency matrix of the graph. Let T(n,D
l) be the tree which minimizes the spectral radius of all trees of order n with exactly l vertices of maximum degree D
. In this paper, T(n,D
l) is determined for D=3, and for l<= 3 and n large enough. It is proven that for sufficiently large n, T(n, 3, l) is a caterpillar with (almost) uniformly distributed legs, T(n,D
2) is a dumbbell, and T(n,
D,3) is a tree consisting of three distinct stars of order D
connected by three disjoint paths of (almost) equal length from their centers to a common vertex. The unique tree with the largest spectral radius among all such trees is also determined. These extend earlier results of Lov´asz and Pelik´an, Simi´c and To˘si´c, Wu, Yuan and Xiao, and Xu, Lin and Shu.

In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F\"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

Motivated by the works of Liu, we provide a unified approach to find Appell-Lerch series and Hecke-type series representations for mock theta functions. We establish a number of parameterized identities with two parameters $a$ and $b$. Specializing the choices of $(a,b)$, we not only give various known and new representations for the mock theta functions of orders 2, 3, 5, 6 and 8, but also present many other interesting identities. We find that some mock theta functions of different orders are related to each other, in the sense that their representations can be deduced from the same $(a,b)$-parameterized identity. Furthermore, we introduce the concept of false Appell-Lerch series. We then express the Appell-Lerch series, false Appell-Lerch series and Hecke-type series in this paper using the building blocks $m(x,q,z)$ and $f_{a,b,c}(x,y,q)$ introduced by Hickerson and Mortenson, as well as $\overline{m}(x,q,z)$ and $\overline{f}_{a,b,c}(x,y,q)$ introduced in this paper. We also show the equivalences of our new representations for several mock theta functions and the known representations.