The question of whether the specified graphs form expander families involves analyzing their spectral properties and expansion characteristics. Here's the synthesis:

First Case (Maps (x \mapsto x+1), (x \mapsto x^3) with inverses, (p \equiv 2 \mod 3)):

• Setup: For primes (p \equiv 2 \mod 3), the cube map (x \mapsto x^3) is injective (hence bijective) on (\mathbb{Z}/p\mathbb{Z}...

Short answer:

• For S = {x ↦ x+1, x ↦ x^3} (and their inverses) on Fp with p ≡ 2 mod 3, this is open. No known method currently proves a uniform spectral gap, and no counterexample is known.
• Adding x ↦ 3x to the generating set does not put the problem in a known regime either; it is also open.

Some context and what is known

1. What is special about x ↦ x+1, x ↦ x−1/x The classical example x ↦ ...

Here is a summary of what is known (and not known) about these “polynomial’’ expanders, and why the question runs head–on into amenability/Property (τ) issues.

1. Setup. For each prime (p) we build a (d)–regular directed graph (\Gamma_p) on the vertex‐set (\F_p) by choosing a finite set of bijections [ f_1,\dots,f_d:\F_p;\to;\F_p ] and drawing oriented edges (x\to f_i(x)). One a...

At the moment nobody knows the answer – neither for

S₁ = { x ↦ x+1 , x ↦ x³ } (with the two inverse maps added so that the graph is 4–regular)

nor for

S₂ = { x ↦ x+1 , x ↦ 3x , x ↦ x³ } (again with the inverses added).

In other words, it is completely open whether the family of graphs G(p,S₁) (resp. G(p,S₂)) obtained from the prime fields...

Non-linear Expanders in Cayley Graphs

This question explores whether certain non-linear maps can generate expander families when used to define Cayley graphs over .

Background Context

In expander theory, we typically consider families of graphs with a bounded spectral gap between the largest and second-largest eigenvalues of their adjacency matrices. Fo...

This is an excellent and deep question that sits at the junction of several active research areas. The short answer is:

• Yes, the maps and are strongly believed and essentially proven to generate an expander family.
• The same is true for the larger set of maps.
• The mechanism is different from the classical linear examples like and is related ...

This is a fascinating question about whether certain non-linear maps can generate expander families. Let me break down what we know and what the challenges are.

Current State of Knowledge

The question of whether non-linear maps like (combined with affine maps) can generate expanders is open. This is part of a broader program to understand which algebraic structures can pro...

<think> We are considering families of graphs defined on the vertex set \(\mathbb{Z}/p\mathbb{Z}\) for primes \(p\) (with some congruence condition to ensure invertibility). The graphs are defined by connecting each vertex \(x\) to the images of \(x\) under a set of functions and their inverses (if included). The question is whether certain sets of functions yield expander families.

The specific ...

Short answer
Nobody knows at present whether the graphs that you ask about are expanders.
The problem is regarded as one of the main open questions at the border‐line between additive–combinatorics, analytic number theory and the theory of expander graphs.

---

1. What is known in the particular cases you mention? --------------...