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

No abstract uploaded!

An analogue of the well-known $$ \frac{3}{{16}} $$ lower bound for the first eigenvalue of the Laplacian for a congruence hyperbolic surface is proven for a congruence tower associated with any non-elementary subgroup$L$of SL(2,$Z$). The proof in the case that the Hausdorff of the limit set of$L$is bigger than $$ \frac{1}{2} $$ is based on a general result which allows one to transfer such bounds from a combinatorial version to this archimedian setting. In the case that delta is less than $$ \frac{1}{2} $$ we formulate and prove a somewhat weaker version of this phenomenon in terms of poles of the corresponding dynamical zeta function. These “spectral gaps” are then applied to sieving problems on orbits of such groups.

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

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.