44 problems

Uniform expansion conjecture. If $G$ is $\varepsilon$-quasirandom, then all connected Cayley graphs of $G$ are $\varepsilon$-uniform expanders.

Cheeger constant conjecture.

Let $(G_i)$ be the family of all non-abelian finite simple groups. A Cayley graph $\mathcal{C}(G_i,S_i)$ is the graph associated with the generating set $S_i$, and a family of grap…

Let $\Gamma_i$ be a family of finite groups, and let $\Sigma_i$ and $\Sigma_i'$ be generating sets of $\Gamma_i$ whose sizes are uniformly bounded. Lubotzky–Weiss generating-set co…

For $\varepsilon>0$, let an $(\varepsilon,d)$-expander be the sublinear-expansion notion used in the source. Hamiltonicity conjecture for regular sublinear expanders. There exists…

Let $f\in\mathbb R[x,y]$ be neither additive nor multiplicative. For a finite set $A\subset\mathbb R$, write $f(A,A)=\{f(a_1,a_2):a_1,a_2\in A\}$. Near-quadratic Elekes–Rónyai expa…

Mihail–Vazirani conjecture. Every $0/1$ polytope $P$ satisfies

Fix $t$, and let $n$ be large enough that the parameters $m_2,\ldots,m_t$ defined by … where $c\in(-1,1)$ is chosen so that $\sum_i m_i=n+1$. Let $H$ be the Tanner-code parity-chec…

Let $(\mathcal{G}_{n})_{n}$ be the family of $\operatorname{SL}(2,\mathbb{Z})$-orbit graphs of primitive $n$-squared origamis in the stratum $\mathcal{H}(2)$. McMullen's expander c…

Let $\mathbb{P}_m(n)$ be the undirected prefix-reversal graph, which is $2n$-regular for $m>1$. A sequence of regular graphs is an expander family if there exists $\varepsilon>0$ s…

Let $E \subseteq \mathbb{F}_q^d$ and let $R \subseteq \mathbb{F}_q \setminus \{0\}$. Let $C$ be the constant appearing in Theorem, whose conclusion guarantees the existence of the…

Let $D\in\mathbb{N}$. An $(n,d,\lambda)$-graph is a graph on $n$ vertices with degree $d$ and second eigenvalue bounded by $\lambda$. Let $T$ be a tree of maximum degree at most…

For a translation surface in the stratum $\mathcal{H}(2)$, the associated Veech group is arithmetic when its orbit gives rise to the graphs under consideration. McMullen's expansio…

Large-q exponential-regime conjecture. For all $q$ sufficiently large, there exists an infinite sequence of $d$-regular graphs with $\lambda_2=\Theta(1/\sqrt{d})$ for some…

Let $G$ be a finitely generated subgroup of $\mathrm{SL}_n(\mathbb{Z})$. Write $\mathbb{G}$ for the Zariski closure of $G$, and let $\mathbb{G}_0$ be its identity component. The gr…

For each prime $p$, let $\mathcal{G}_p$ be the corresponding Markoff modulo-$p$ graph. Super Strong Approximation. The collection of Markoff modulo-$p$ graphs $(\mathcal{G}_p)_p$ f…

Let $G$ be a definite Gross inner form and let $\mathfrak{p}$ be a finite place. Let $\{X_{\mathfrak{p}}(q)\}$ denote its family of congruence complexes. Density-Ramanujan conjectu…

Salehi-Golsefidy–Varjú conjecture. A finitely generated subgroup $G<\operatorname{SL}_n(\mathbb Z)$ has super approximation with respect to all positive integers exactly when the i…

Let $(G_n)_{n\ge 1}$ be a sequence of finite vertex-transitive expander graphs, and consider simple random walk on each $G_n$. Levin–Peres conjecture. The sequence $(G_n)_{n\ge 1}$…

For a graph with the parameters and family of cuts defined in Lemma, let $\mathcal{C}^{\mathrm{ind}}$ denote the corresponding family of induced cuts. Bounded enumeration conjectur…

Expander-graph conjecture. There is a choice of corrupted set such that the conclusion to Theorem holds.

Let $\mathcal{G}_n$ be the Cayley graph of $\mathrm{SL}_3(\mathbf{Z}/n\mathbf{Z})$ with respect to the images of the elementary matrices. A sequence of bounded-degree graphs is a s…

Let $G$ be a nonabelian finite simple group. A subset $S\subset G$ is symmetric when it is closed under taking inverses, and $\operatorname{Cay}(G,S)$ denotes the Cayley graph of…

Let $q$ be fixed and large, and let $X_n$ be the family of $(q+1)$-regular Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak. For a vertex set $Y\subset X_n$, write…

Let $g_n$ satisfy … and let $\mathbf{T_{n,g_n}}$ be a uniform triangulation of genus $g_n$ with $3n$ edges. An induced subgraph is a $\kappa$-expander if every set of vertices has…