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

A simplicial complex Δ is called$flag$if all minimal nonfaces of Δ have at most two elements. The following are proved: First, if Δ is a flag simplicial pseudomanifold of dimension$d$−1, then the graph of Δ (i) is (2$d$−2)-vertex-connected and (ii) has a subgraph which is a subdivision of the graph of the$d$-dimensional cross-polytope. Second, the$h$-vector of a flag simplicial homology sphere Δ of dimension$d$−1 is minimized when Δ is the boundary complex of the$d$-dimensional cross-polytope.

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

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.

The set of all non-increasing nonnegative integers sequence $\pi=$ ($d(v_1 ),$ $d(v_2 ),$ $...,$ $d(v_n )$) is denoted by $NS_n$. A sequence $\pi\in NS_n$ is said to be graphic if it is the degree sequence of a simple graph $G$ on $n$ vertices, and such a graph $G$ is called a realization of $\pi$. The set of all graphic sequences in $NS_n$ is denoted by $GS_n$. A graphical sequence $\pi$ is potentially $H$-graphical if there is a realization of $\pi$ containing $H$ as a subgraph, while $\pi$ is forcibly $H$-graphical if every realization of $\pi$ contains $H$ as a subgraph. Let $K_k$ denote a complete graph on $k$ vertices. 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}$). This paper summarizes briefly some recent results on potentially $K_{m}-G$-graphic sequences and give a useful classification for determining $\sigma(H,n)$.

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

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, Erdős raised the question of determining $f(n)$ [see J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New York, 1976; MR0411988 (54 #117)]. We prove that for $n\geq 36\cdot 5t^2-4\cdot 5t+1$ one has $f(n)\geq n+9t-1$ . We conjecture that $\liminf (f(n)-n)/\sqrt n\leq\sqrt 3$ .

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.

No abstract uploaded!