The tag has no wiki summary.

learn more… | top users | synonyms

8
votes
0answers
183 views

Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs

this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...
12
votes
3answers
327 views

Embedding expanders in CAT(0) spaces

It is well-known that expanders are hard to embed into Hilbert (or $\ell^p$) spaces - any embedding of an expander with $n$ vertices has distortion $\Omega(\log n)$. Can anyone provide a reference ...
2
votes
0answers
90 views

What are the best bounds to date on the maximum girth of a cubic graph?

The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem. In the 1988 paper "Ramanujan ...
11
votes
1answer
232 views

Variant of an Expander graph: Probability that S random points cast a shadow/projection of size at most S/2 on each face of a cube.

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, ...
7
votes
1answer
146 views

Do there exist “expanding” $1$-skeletons of simple $4$-polytopes?

Let $\{ G_n \}_{n \ge 1}$ be a sequence of graphs such that the number of vertices of $G_n$ tends to $\infty$ as $n \to \infty$. We say that $\{ G_n \}_{n \ge 1}$ is an expander family if $\lambda_2( ...
5
votes
1answer
361 views

More expanders?

Having received several exhausting answers to my recent question about the expansion properties of a certain graph, I now wonder whether anything is known on the following graphs of a similar nature: ...
10
votes
2answers
320 views

An expander (?) graph

For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless $z=0$). I was told that this graph is known to be ...
7
votes
1answer
287 views

Constructing expanders in Z/pZ

Fix a positive integer $k>0$. For $p>k$ a prime, let $A_p$ be a subset of the finite field $\mathbb{Z}/p\mathbb{Z}$ of size $k$ which contains a primitive element. Define $G_p$ to be the ...
17
votes
0answers
655 views

Could unramified Galois groups satisfy a version of property tau?

This is an experiment: there is a question I want to mention in an article I'm writing, and I am not sure it's a sensible question, so I will ask it here first, in the hopes that if it's insensible ...