In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $f(n)\geq n+32t-1$ for $t=27720r+169\ (r\geq 1)$ and $n\geq\frac{6911}{16}t^2+\frac{514441}{8}t-\frac{3309665}{16}$ . Consequently, $\liminf_{n\to\infty}\frac{f(n)-n}{\sqrt n}\geq\sqrt{2+\frac{2562}{6911}}$ .

No abstract uploaded!

We establish a new on-diagonal lower estimate of continuous-time heat kernels for large time on graphs. To achieve the goal, we first introduce an upper estimate of heat kernels in natural graph metric, then use the upper estimate and the volume growth condition to show the validity of the on-diagonal lower estimate.

We prove a homology vanishing theorem for graphs with positive Bakry-\'Emery curvature, analogous to a classic result of Bochner on manifolds\cite {Bochner}. Specifically, we prove that if a graph has positive curvature at every vertex, then its first homology group is trivial, where the notion of homology that we use for graphs is the path homology developed by Grigor'yan, Lin, Muranov, and Yau\cite {Grigoryan2}.%\Hm {added the fundamental group curvature relation} We moreover prove that the fundamental group is finite for graphs with positive Bakry-\'Emery curvature, analogous to a classic result of Myers on manifolds\cite {Myers1941}. The proofs draw on several separate areas of graph theory. We study graph coverings, gain graphs, and cycle spaces of graphs, in addition to the Bakry-\'Emery curvature and the path homology. The main results follow as a consequence of several different relationships developed among these different areas. Specifically, we show that a graph with positive curvature can have no non-trivial infinite cover preserving 3-cycles and 4-cycles, and give a combinatorial interpretation of the first path homology in terms of the cycle space of a graph. We relate cycle spaces of graphs to gain graphs with abelian gain group, and relate these to coverings of graphs. Along the way, we prove other new facts about gain graphs, coverings, and cycles spaces that are of related interest. Furthermore, we relate gain graphs to graph homotopy and the fundamental group developed by Grigor'yan, Lin, Muranov, and Yau\cite {Grigoryan_homotopy}, and obtain an alternative proof to their result that the abelianization of the fundamental

No abstract uploaded!

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If$P$is a simplicial$d$-polytope then its$h$-vector ($h$_{0},$h$_{1}, …,$h$_{$d$}) satisfies $$ {h_0}\leq {h_1}\leq \ldots \leq {h_{{\left\lfloor {{d \left/ {2} \right.}} \right\rfloor }}} $$ . Moreover, if$h$_{$r$−1}=$h$_{$r$}for some $$ r\leq \frac{1}{2}d $$ then$P$can be triangulated without introducing simplices of dimension ≤$d$−$r$.

The CD inequalities are introduced to imply the gradient estimate of Laplace operator on graphs. This article is based on the unbounded Laplacians, and finally concludes some equivalent properties of the CD(K,1) and CD(K,n).

Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). We use the symbol $Z_4$ to denote $K_4-P_2.$ A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $\sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}-U, n)$ for $n\geq 5r+18, r+1 \geq k \geq 7,$ $j \geq 6$ where $U$ is a graph on $k$ vertices and $j$ edges which contains a graph $K_3 \bigcup P_3$ but not contains a cycle on $4$ vertices and not contains $Z_4$.

No abstract uploaded!

In this note, we prove the sharp DaviesGaffneyGrigoryan Lemma for minimal heat kernels on graphs.

No abstract uploaded!

We show that the product in the quantum K-ring of a generalized flag manifold G/P involves only finitely many powers of the Novikov variables. In contrast to previous approaches to this finiteness question, we exploit the finite difference module structure of quantum K-theory. At the core of the proof is a bound on the asymptotic growth of the J-function, which in turn comes from an analysis of the singularities of the zastava spaces studied in geometric representation theory. An appendix by H. Iritani establishes the equivalence between finiteness and a quadratic growth condition on certain shift operators.

We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by$δ$are called$δ$-$uniform$. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics.

The rank of tensors is not additive with respect to the direct sum.

No abstract uploaded!

Geometric genus is an important invariant in the classification theory for isolated singularities. In this paper we give a complete classification of three-dimensional isolated weighted homogeneous singularities with geometric genus one. This is one of important classes of minimally elliptic singularities.

Let $K_k$, $C_k$, $T_k$, and $P_{k}$ denote a complete graph on $k$ vertices, a cycle on $k$ vertices, a tree on $k+1$ vertices, and a path on $k+1$ vertices, respectively. Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $\sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}-H, n)$ for $n\geq 4r+10, r\geq 3, r+1 \geq k \geq 4$ where $H$ is a graph on $k$ vertices which contains a tree on $4$ vertices but not contains a cycle on $3$ vertices. We also determine the values of $\sigma (K_{r+1}-P_2, n)$ for $n\geq 4r+8, r\geq 3$.

In this paper, we give the sharp upper bound for the number of vertices with positive curvature in a planar graph with nonnegative combinatorial curvature. Based on this, we show that the automorphism group of a planar—possibly infinite—graph with nonnegative combinatorial curvature and positive total curvature is a finite group, and give an upper bound estimate for the order of the group.

In this paper, we give a complete classification of cotorsion pairs in a cluster category C of type A^\infty_\infty via certain configurations of arcs, called τ-compact Ptolemy diagrams, in an infinite strip with marked points. As applications, we classify t-structures and functorially finite rigid subcategories in C, respectively. We also deduce Liu-Paquette's classification of cluster tilting subcategories of C and Ng's classification of torsion pairs in the cluster category of type A^\infty_\infty.

We study pretty good quantum state transfer (ie, state transfer that becomes arbitrarily close to perfect) between vertices of graphs with an involution in the presence of an energy potential. In particular, we show that if a graph has an involution that fixes at least one vertex or at least one edge, then there exists a choice of potential on the vertex set of the graph for which we get pretty good state transfer between symmetric vertices of the graph. We show further that in many cases, the potential can be chosen so that it is only non-zero at the vertices between which we want pretty good state transfer. As a special case of this, we show that such a potential can be chosen on the endpoints of a path to induce pretty good state transfer in paths of any length. This is in contrast to the result of [6], in which the authors show that there cannot be perfect state transfer in paths of length 4 or more, no matter what potential is chosen.

We study the cluster combinatorics of d-cluster tilting objects in d-cluster categories. Using mutations of maximal rigid objects in d-cluster categories, which are defined in a similar way to mutations for d-cluster tilting objects, we prove the equivalences between d-cluster tilting objects, maximal rigid objects and complete rigid objects. Using the chain of d+1 triangles of d-cluster tilting objects in [O. Iyama, Y. Yoshino, Mutations in triangulated categories and rigid Cohen–Macaulay modules, Invent. Math. 172 (1) (2008) 117–168], we prove that any almost complete d-cluster tilting object has exactly d+1 complements, compute the extension groups between these complements, and study the middle terms of these d+1 triangles. All results are the extensions of corresponding results on cluster tilting objects in cluster categories established for d-cluster categories in [A. Buan, R. Marsh, M. Reineke, I. Reiten, G. Todorov, Tilting theory and cluster combinatorics, Adv. Math. 204 (2006) 572–618]. They are applied to the Fomin–Reading generalized cluster complexes of finite root systems defined and studied in [S. Fomin, N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Not. 44 (2005) 2709–2757; H. Thomas, Defining an m-cluster category, J. Algebra 318 (2007) 37–46; K. Baur, R. Marsh, A geometric description of m-cluster categories, Trans. Amer. Math. Soc. 360 (2008) 5789–5803; K. Baur, R. Marsh, A geometric description of the m-cluster categories of type D_n, preprint, arXiv:math.RT/0610512; see also Int. Math. Res. Not. 2007 (2007), doi:10.1093/imrn/rnm011], and to that of infinite root systems [B. Zhu, Generalized cluster complexes via quiver representations, J. Algebraic Combin. 27 (2008) 25–54].

We classify all connected, simple, 3-regular graphs with girth at least 5 that are Ricci-flat. We use the definition of Ricci curvature on graphs given in Lin-Lu-Yau, Tohoku Math., 2011, which is a variation of Ollivier, J. Funct. Anal., 2009. A graph is Ricci-flat, if it has vanishing Ricci curvature on all edges. We show, that the only Ricci-flat cubic graphs with girth at least 5 are the Petersen graph, the Triplex and the dodecahedral graph. This will correct the classification in Lin-Lu-Yau, Comm. Anal. Geom., 2014, that misses the Triplex.

We associate to a finite digraph D a lattice polytope PD whose vertices are the rows of the Laplacian matrix of D. This generalizes a construction introduced by Braun and the third author. As a consequence of the Matrix-Tree Theorem, we show that the normalized volume of PD equals the complexity of D, and PD contains the origin in its relative interior if and only if D is strongly connected. Interesting connections with other families of simplices are established and then used to describe reflexivity, the h∗-polynomial, and the integer decomposition property of PD in these cases. We extend Braun and Meyer’s study of cycles by considering cycle digraphs. In this setting, we characterize reflexivity and show there are only four non-trivial reflexive Laplacian simplices having the integer decomposition property.

"A sequence $S$ is potentially $K_4-e$ graphical if it has a realization containing a $K_4-e$ as a subgraph. Let $\sigma(K_4-e,n)$ denote the smallest degree sum such that every $n$ -term graphical sequence $S$ with $\sigma(S)\geq\sigma(K_4-e,n)$ is potentially $K_4-e$ graphical. Gould, Jacobson, Lehel raised the problem of determining the value of $\sigma(K_4-e,n)$ . In this paper, we prove that $\sigma(K_4-e,n)=2[(3n-1)/2]$ for $n\geq7$ and $n=4,5$ , and $\sigma(K_4-e,6)=20$ .''

No abstract uploaded!