Narrow Results

We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is.

As an application, we show that if G is a high-girth regular expander on n vertices, then a typical non-backtracking random walk of length n on G does not visit a vertex more than times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing n balls to n bins uniformly, in contrast to the simple random walk on G, which almost surely visits some vertex Ω(log n) times.

In this paper we establish new estimates on sum-product sets and certain exponential sums in finite fields of prime order. Our first result is an extension of the sum-product theorem from [8] when sets of different sizes are involed. It is shown that if and p^ε < |B|, |C| < |A| < p^1-ε, then |A + B| + |A · C| > p^{δ (ε)}|A|. Next we exploit the Szemerédi–Trotter theorem in finite fields (also obtained in [8]) to derive several new facts on expanders and extractors. It is shown for instance that the function f(x,y) = x(x+y) from to satisfies |F(A,B)| > p^β for some β = β (α) > α whenever and |A| ~ |B|~ p^α, 0 < α < 1. The exponential sum ∑_{x∈ A,y∈B}ε_p(axy+bx²y²), ab ≠ 0 (mod p), may be estimated nontrivially for arbitrary sets satisfying |A|, |B| > p^ρ where ρ < 1/2 is some constant. From this, one obtains an explicit 2-source extractor (with exponential uniform distribution) if both sources have entropy ratio at last ρ. No such examples when ρ < 1/2 seemed known. These questions were largely motivated by recent works on pseudo-randomness such as [2] and [3].

Finally it is shown that if p^ε < |A| < p^1-ε, then always |A + A|+|A^-1 + A^-1| > p^δ(ε)|A|. This is the finite fields version of a problem considered in [11]. If A is an interval, there is a relation to estimates on incomplete Kloosterman sums. In the Appendix, we obtain an apparently new bound on bilinear Kloosterman sums over relatively short intervals (without the restrictions of Karatsuba's result [14]) which is of relevance to problems involving the divisor function (see [1]) and the distribution (mod p) of certain rational functions on the primes (cf. [12]).

Let 𝔽_q be the finite field with q elements and P(x, y) be a polynomial in 𝔽_q[x, y]. Using additive character sum estimates, we study expander property of the function x₁ + P(x₂, x₃). We give an alternative proof using spectra of sum–product graphs in the case of P(x, y) = xy, and also extend the problem in the setting of finite cyclic rings.

Let F be a non archimedean local field and let G be an algebraic connected almost F-simple group over F, whose Lie algebra contains sl₃(F). We prove that G(F) has strong Banach property (T) in a stronger sense than in the article "Un renforcement de la propriété (T)", published in Duke Math. J. As a consequence, families of expanders built from a lattice in G(F) do not embed uniformly in Banach spaces of type > 1. Also any affine isometric action of G(F) on a Banach space of type > 1 has a fixed point.

We extend Vincent Lafforgue's results to Sp₄. As applications, the family of expanders constructed by finite quotients of a lattice in such a group does not admit a uniform embedding in any Banach space of type > 1, and any affine isometric action of such a group, or of any cocompact lattice in it, in a Banach space of type > 1 has a fixed point.

In this paper we study a coarse version of the $K$-theoretic Farrell–Jones conjecture we call coarse or bounded isomorphism conjecture. Using controlled category theory we are able to translate this conjecture for asymptotically faithful covers into a more familiar form. This allows us to prove the conjecture for box spaces of residually finite groups whose Farrell–Jones assembly map with coefficients is an isomorphism.

O. Reingold et al. introduced the notion zig-zag product on two different graphs, and presented a fully explicit construction of d-regular expanders with the second largest eigenvalue O(d^-1/3). In the same paper, they ask whether or not the similar technique can be used to construct expanders with the second largest eigenvalue O(d^-1/2). Such graphs are called Ramanujan graphs. Recently, zig-zag product has been generalized by A. Ben-Aroya and A. Ta-Shma. Using this technique, they present a family of expanders with the second largest eigenvalue d^{-1/2 + o(1)}, what they call almost-Ramanujan graphs. However, their construction relies on local invertible functions and the dependence between the big graph and several small graphs, which makes the construction more complicated.

In this paper, we shall give a generalized theorem of zig-zag product. Specifically, the zig-zag product of one "big" graph and several "small" graphs with the same size will be formalized. By choosing the big graph and several small graphs individually, we shall present a family of fully explicitly almost-Ramanujan graphs with locally invertible function waived.