Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Having received several exhausting answers to my recent questionmy 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:

  1. The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$, where $g$ is a fixed primitive root mod $p$.

  2. The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$, where $e$ is a fixed non-zero element, and $g$ is a generating element of ${\rm GF}(2^n)$.

  3. The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.

Are these (families of) graphs known to be good expanders? Can one investigate them using Selberg's 3/16-theorem or other "standard" tools used to study the graph my original questionmy original question concerned with?

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:

  1. The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$, where $g$ is a fixed primitive root mod $p$.

  2. The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$, where $e$ is a fixed non-zero element, and $g$ is a generating element of ${\rm GF}(2^n)$.

  3. The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.

Are these (families of) graphs known to be good expanders? Can one investigate them using Selberg's 3/16-theorem or other "standard" tools used to study the graph my original question concerned with?

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:

  1. The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$, where $g$ is a fixed primitive root mod $p$.

  2. The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$, where $e$ is a fixed non-zero element, and $g$ is a generating element of ${\rm GF}(2^n)$.

  3. The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.

Are these (families of) graphs known to be good expanders? Can one investigate them using Selberg's 3/16-theorem or other "standard" tools used to study the graph my original question concerned with?

corrected spelling of tag
Link
Nick Gill
  • 11.2k
  • 40
  • 70
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

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:

  1. The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$, where $g$ is a fixed primitive root mod $p$.

  2. The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$, where $e$ is a fixed non-zero element, and $g$ is a generating element of ${\rm GF}(2^n)$.

  3. The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.

Are these (families of) graphs known to be good expanders? Can one investigate them using Selberg's 3/16-theorem or other "standard" tools used to study the graph my original question concerned with?