Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. P. 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). We present the problems, conjectures related to this problems and we summarize the know results. We make the following conjecture: \par \noindent{\bf Conjecture } $$\lim\sb {n \to \infty} {f(n)-n \over \sqrt n} = \sqrt {2 + \frac{4}{9}}.$$

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}-Z, n)$ for $n\geq 5r+19, r+1 \geq k \geq 5,$ $j \geq 5$ where $Z$ is a graph on $k$ vertices and $j$ edges which contains a graph $Z_4$ but not contains a cycle on $4$ vertices. We also determine the values of $\sigma (K_{r+1}-Z_4, n)$, $\sigma (K_{r+1}-(K_4-e), n)$, $\sigma (K_{r+1}-K_4, n)$ for $n\geq 5r+16, r\geq 4$.

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$.

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$.

"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$ .''

"In this paper we consider a variation of the classical Turán-type extremal problems. Let $S$ be an $n$ -term graphical sequence, and $\sigma(S)$ be the sum of the terms in $S$ . Let $H$ be a graph. The problem is to determine the smallest even $l$ such that any $n$ -term graphical sequence $S$ having $\sigma(S)\geq l$ has a realization containing $H$ as a subgraph. Denote this value $l$ by $\sigma(H,n)$ . We show $\sigma(C_{2m+1},n)=m(2n-m-1)+2$ , for $m\geq 3$ , $n\geq 3m$ ; $\sigma(C_{2m+2},n)=m(2n-m-1)+4$ , for $m\geq 3$ , $n\geq 5m-2$ .''

In this paper, we prove that discrete Morse functions on digraphs are flat Witten-Morse functions and Witten complexes of transitive digraphs approach to Morse complexes. We construct a chain complex consisting of the formal linear combinations of paths which are not only critical paths of the transitive closure but also allowed elementary paths of the digraph, and prove that the homology of the new chain complex is isomorphic to the path homology. On the basis of the above results, we give the Morse inequalities on digraphs.

We study a certain discrete differentiation of piecewise-constant functions on the adjoint of the braid hyperplane arrangement, defined by taking finite-differences across hyperplanes. In terms of Aguiar-Mahajan's Lie theory of hyperplane arrangements, we show that this structure is equivalent to the action of Lie elements on faces. We use layered binary trees to encode flags of adjoint arrangement faces, allowing for the representation of certain Lie elements by antisymmetrized layered binary forests. This is dual to the well-known use of (delayered) binary trees to represent Lie elements of the braid arrangement. The discrete derivative then induces an action of layered binary forests on piecewise-constant functions, which we call the forest derivative. Our main result states that forest derivatives of functions factorize as external products of functions precisely if one restricts to functions which satisfy the Steinmann relations, which are certain four-term linear relations appearing in the foundations of axiomatic quantum field theory. We also show that the forest derivative satisfies the Lie properties of antisymmetry the Jacobi identity. It follows from these Lie properties, and also crucially factorization, that functions which satisfy the Steinmann relations form a left comodule of the Lie cooperad, with the coaction given by the forest derivative. Dually, this endows the adjoint braid arrangement modulo the Steinmann relations with the structure of a Lie algebra internal to the category of vector species. This work is a first step towards describing new connections between Hopf theory in species and quantum field theory.

In this paper, we give a necessary and sufficient condition that discrete Morse functions on a digraph can be extended to be Morse functions on its transitive closure, from this we can extend the Morse theory to digraphs by using quasi-isomorphism between path complex and discrete Morse complex, we also prove a general sufficient condition for digraphs that the Morse functions satisfying this necessary and sufficient condition.

Let G=(V,E) be a locally finite graph. Firstly, using calculus of variations, including a direct method of variation and the mountain-pass theory, we get sequences of solutions to several local equations on G (the Schrödinger equation, the mean field equation, and the Yamabe equation). Secondly, we derive uniform estimates for those local solution sequences. Finally, we obtain global solutions by extracting convergent sequence of solutions. Our method can be described as a variational method from local to global.

Inspired by works of Castéras (Pac J Math 276:321–345, 2015), Li and Zhu (Calc Var Partial Differ Equ 58:1–18, 2019), Sun and Zhu (Calc Var Partial Differ Equ 60:1–26, 2021), we propose a heat flow for the mean field equation on a connected finite graph G=(V,E). Namely ∂_tϕ(u)=Δu−Q+ρ\frac{e^u}{∫_V e^u dμ} u(⋅,0)=u_0, where Δ is the standard graph Laplacian, ρ is a real number, Q:V→R is a function satisfying ∫_V Qdμ=ρ, and ϕ:R→R is one of certain smooth functions including ϕ(s)=es. We prove that for any initial data u_0 and any ρ∈R, there exists a unique solution u:V×[0,+∞)→R of the above heat flow; moreover, u(x, t) converges to some function u_∞:V→R uniformly in x∈V as t→+∞, and u_∞ is a solution of the mean field equation Δu_∞−Q+ρ\frac{e^{u_∞}}{∫_V e^{u_∞}dμ}=0. Though G is a finite graph, this result is still unexpected, even in the special case Q≡0. Our approach reads as follows: the short time existence of the heat flow follows from the ODE theory; various integral estimates give its long time existence; moreover we establish a Lojasiewicz–Simon type inequality and use it to conclude the convergence of the heat flow.

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).

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 explore the tunneling behavior of a quantum particle on a finite graph in the presence of an asymptotically large potential with two or three potential wells. The behavior of the particle is primarily governed by the local spectral symmetry of the graph around the wells. In the case of two wells the behavior is stable in the sense that it can be predicted from a sufficiently large neighborhood of the wells. However in the case of three wells we are able to exhibit examples where the tunneling behavior can be changed significantly by perturbing the graph arbitrarily far from the wells.

We modify the definition of Ricci curvature of Ollivier of Markov chains on graphs to study the properties of the Ricci curvature of general graphs, Cartesian product of graphs, random graphs, and some special class of graphs.

Let Q be an acyclic quiver and s be a sequence with elements in the vertex set Q_0. We describe an induced sequence of simple (backward) tilting in the bounded derived category D(Q), starting from the standard heart H_Q = modkQ and ending at another heart H_s in D(Q). Then we show that s is a green mutation sequence if and only if every heart in this simple tilting sequence is greater than or equal to HQ[−1]; it is maximal if and only if H_s = H_Q[−1]. This provides a categorical way to understand green mutations. Further, fix a Coxeter element c in the Coxeter group W_Q of Q, which is admissible with respect to the orientation of Q. We prove that the sequence \tilde{w} induced by a c-sortable word w is a green mutation sequence. As a consequence, we obtain a bijection between c-sortable words and finite torsion classes in H_Q. As byproducts, the interpretations of inversions, descents and cover reflections of a c-sortable word w are given in terms of the combinatorics of green mutations.

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 study the cluster algebras arising from cluster tubes with rank bigger than 1. Cluster tubes are 2−Calabi-Yau triangulated categories which contain no cluster tilting objects, but maximal rigid objects. Fix a certain maximal rigid object T in the cluster tube C_n of rank n. For any indecomposable rigid object M in C_n, we define an analogous X_M of Caldero-Chapton's formula (or Palu's cluster character formula) by using the geometric information of M. We show that X_M,X_{M′} satisfy the mutation formula when M,M′ form an exchange pair, and that X_? : M↦X_M gives a bijection from the set of indecomposable rigid objects in C_n to the set of cluster variables of cluster algebra of type C_{n−1}, which induces a bijection between the set of basic maximal rigid objects in C_n and the set of clusters. This strengths a surprising result proved recently by Buan-Marsh-Vatne that the combinatorics of maximal rigid objects in the cluster tube Cn encode the combinatorics of the cluster algebra of type B_{n−1} since the combinatorics of cluster algebras of type B_{n−1} or of type C_{n−1} are the same by a result of Fomin and Zelevinsky. As a consequence, we give a categorification of cluster algebras of type C.

We introduce and study mutation of torsion pairs, as a generalization of mutation of cluster tilting objects, rigid objects and maximal rigid objects. It is proved that any mutation of a torsion pair is again a torsion pair. A geometric realization of mutation of torsion pairs in the cluster category of type A_n or A_\infty is given via rotation of Ptolemy diagrams.

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.

For any r-order {0,1}-tensor A with e ones, we prove that the spectral radius of A is at most exp((r-1)/r) with the equality holds if and only if e=k^r for some integer k and all ones forms a principal sub-tensor 1_{k x k x ... x k}. We also prove a stability result for general tensor A with e ones where e = k^r+l with relatively small l. Using the stability result, we completely characterized the tensors achieving the maximum spectral radius among all r-order {0,1}-tensor A with k^r+l ones, for -r-1 ≤ l ≤ r, and k sufficiently large.

We introduce the notion of Bonnet-Myers and Lichnerowicz sharpness in the Ollivier Ricci curvature sense. Our main result is a classification of all self-centered Bonnet-Myers sharp graphs (hypercubes, cocktail party graphs, even-dimensional demi-cubes, Johnson graphs , the Gosset graph J(2n, n) and suitable Cartesian products). We also present a purely combinatorial reformulation of this result. We show that Bonnet-Myers sharpness implies Lichnerowicz sharpness and classify all distance-regular Lichnerowicz sharp graphs under the additional condition θ_1=b_1-1. We also relate Bonnet-Myers sharpness to an upper bound of Bakry-Émery ∞-curvature, which motivates a general conjecture about Bakry-Émery ∞-curvature.

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.

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.

We construct small cancellation labellings for some infinite sequences of finite graphs of bounded degree. We use them to define infinite graphical small cancellation presentations of groups. This technique allows us to provide examples of groups with exotic properties: • We construct the first examples of finitely generated coarsely non-amenable groups (that is, groups without Guoliang Yu’s Property A) that are coarsely embeddable into a Hilbert space. Moreover, our groups act properly on CAT(0) cubical complexes. • We construct the first examples of finitely generated groups, with expanders embedded isometrically into their Cayley graphs—in contrast, in the case of the Gromov monster expanders are not even coarsely embedded. We present further applications.