In 1975, P. Erd\"{o}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+36t$$ for $t=1260r+169 \,\ (r\geq 1)$ and $n \geq 540t^{2}+\frac{175811}{2}t+\frac{7989}{2}$. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2 \over 5}},$ which is better than the previous bounds $\sqrt 2$ (see [2]), $\sqrt {2+{2562\over 6911}}$ (see [7]).

We compute a momentum space version of the entanglement spectrum and entanglement entropy of general Young tableau states, and one-point functions on Young tableau states. These physical quantities are used to measure the topology of the dual spacetime geometries in the context of gauge/gravity correspondence. The idea that Young tableau states can be obtained by superposing coherent states is explicitly verified. In this quantum superposition, a topologically distinct geometry is produced by superposing states dual to geometries with a trivial topology. Furthermore we have a refined bound for the overlap between coherent states and the rectangular Young tableau state, by using the techniques of symmetric groups and representations. This bound is exponentially suppressed by the total edge length of the Young tableau. It is also found that the norm squared of the overlaps is bounded above by inverse powers of the exponential of the entanglement entropies. We also compute the overlaps between Young tableau states and other states including squeezed states and multi-mode entangled states which have similarities with those appeared in quantum information theory.

We introduce a homotopy theory of digraphs (directed graphs) and prove its basic properties, including the relations to the homology theory of digraphs constructed by the authors in previous papers. In particular, we prove the homotopy invariance of homologies of digraphs and the relation between the fundamental group of the digraph and its first homology group. The category of (undirected) graphs can be identified by a natural way with a full subcategory of digraphs. Thus we obtain also consistent homology and homotopy theories for graphs.

In the first part of this paper, we study Koszul property of directed graded categories. In the second part of this paper, we prove a general criterion for an infinite directed category to be Koszul. We show that infinite directed categories in the theory of representation stability are Koszul over a field of characteristic zero

No abstract uploaded!