Mathematics Problem Archive

Can the sequence of metric balls in an infinite Cayley graph form a family of expanders?...

Suppose $G$ and $H$ are Cayley, or vertex-transitive, expanders on the same number of vertices and can be matched with asymptotically vanishing edge d...

If $G$ is a finite vertex-transitive expander, must every almost automorphism of $G$ be close to an automorphism?...

For an infinite $d$-regular Ramanujan graph, does random-walk neighborhood sampling converge to the $d$-regular tree?...

For a locally convergent sequence $(G_n)$ of bounded-degree integer-labeled graphs, does the normalized rank modulo $p$ of the adjacency matrix conver...

For a graph sequence $(G_n)$ define $e((G_n))=\liminf |E(G_n)|/|V(G_n)|$, and define its combinatorial cost as the infimum of $e((H_n))$ over graph se...

Compactness implies that for every $\varepsilon>0$ there is $K>0$ such that every finite graph can be approximated within error $\varepsilon$ by a fin...

Let $(G_n)$ be a locally convergent graph sequence and let $\mu_n$ be the probability distribution of the roots of the chromatic polynomial of $G_n$. ...

Which probability measures can occur as eigenvalue distributions of finite $d$-regular graphs? Find natural restrictions....

Let $G$ be a $d$-regular Cayley graph with spectral measure $\mu$. Is $\mu$ a weak limit of spectral measures of finite $d$-regular graphs?...

For each $d\geq3$, does the independence ratio of a uniformly random $d$-regular graph converge in probability as the number of vertices tends to infi...

Do uniformly random $d$-regular graphs converge, in local-global convergence, to the weak closure of independent identically distributed processes?...

Is the i.i.d. action of the free group $F_2$ a local-global limit of finite actions of $F_2$?...

Let $\Gamma$ have property (T), and let $(G_n)$ be a sofic approximation of a Cayley graph of $\Gamma$. Can $(G_n)$ be changed by an asymptotically va...

Can every ergodic unimodular random network that is almost surely an infinite tree be obtained as the limit of an expander family?...

Let $G$ be an infinite vertex-transitive graph, let $A$ be a finite vertex set, let $b$ be a vertex, and let $\partial A$ be the set of vertices at di...

Define the first $L^2$ Betti number of a vertex-transitive graph $G$ from the expected degree of a free spanning forest. Do $G$ and its square $G^2$ h...

Can free spanning forests be used to prove basic properties of the first $L^2$ Betti number, such as multiplicativity upon passage to a finite-index s...

Let $G$ be an infinite Cayley graph of a group that is not virtually cyclic. Prove that there exists $p<1$ for which Bernoulli $p$-edge percolation on...

Does every infinite connected Cayley graph admit an invariant random perfect matching?...

Does every infinite Cayley graph, or every infinite vertex-transitive graph, have a spanning tree without leaves?...

In every infinite Cayley graph, does the density of dead ends tend to zero?...

Are factors of i.i.d. on the $3$-regular tree closed in the weak topology? In particular, is the weak limit of majority functions on $n$-balls a facto...

Does every infinite Cayley graph $G$ admit a $G$-invariant proper coloring with $\chi(G)$ colors?...

Let $X$ be the space of $k$-regular Cayley graphs with the local-convergence topology and let $T\subset X$ be the closed subset of transient graphs. I...

For every $k>1$, does there exist $C(k)<1$ such that the return probability of every transient $k$-regular Cayley graph is at most $C(k)$?...

For a nonamenable group $\Gamma$, does the Bernoulli shift $\{0,1\}^{\Gamma}$ factor onto $\{0,1,2\}^{\Gamma}$?...

Can every $d$-regular graphing without multiple edges be properly edge-colored by $d+1$ colors?...

Let $(G_n)$ and $(H_n)$ converge to the same graph limit, and let $(T_n)$ be a convergent sequence with each $T_n$ a spanning tree of $G_n$. Do there ...

Let $G$ be a bounded-degree expander, or strongly ergodic, graphing that can be properly colored by $C$ colors with arbitrarily small error. Can it be...

Let $G$ be a bounded-degree expander, or strongly ergodic, graphing that weakly contains a finite graph $H$. Does $G$ factor onto $H$?...

Does every higher-rank semisimple real lattice have rank gradient zero?...

Does every residually finite property-(T) group have rank gradient zero?...

Is there a polynomial time algorithm that is able to find the largest clique of $G$ (with high probability) for $\omega \ll \sqrt{n}$ ? For example, f...

Can the Euclidean minimum spanning tree (MST) of $n$ points in $\mathbb{R}^d$ be computed in time close to the lower bound of $\Omega(n \log n)$?...

Does every simple graph with maximum vertex degree $\Delta \leq 6$ have a 3D orthogonal point-drawing with no more than two bends per edge? A 3D ortho...

Does every $n$-vertex planar graph have a 3D grid drawing with $O(n)$ volume? A 3D grid drawing of a graph is a placement of the vertices at distinct ...

Does every planar graph have $O(1)$ queue-number? A queue layout of a graph consists of a linear order of the vertices and a partition of the edges in...

Is the Yao-Yao Graph a $t$-spanner for constant $t$? A geometric graph is a $t$-spanner (or just a spanner) if, for every pair of nodes, the shortest ...

Babai's problem: which groups are Babai invariant groups?...

Given $n\in\mathbb{N}$, can a prime $p>n$ be found in deterministic polynomial time?...

Given coprime $a,n\in\mathbb{N}$, can a prime $p\equiv a\pmod n$ be found in deterministic polynomial time?...

Is complete integer factorization $C_5$ in deterministic polynomial time $P$?...

Is complete integer factorization $C_5$ in randomized polynomial time $R$?...

Does there exist a set $S\subset\mathbb{N}$ of positive lower asymptotic density for which complete factorization of every input $n\in S$ is in determ...

Given $n$, can one find $r,s\in\mathbb{N}$ with $n=r^2s$ and $s$ squarefree in deterministic polynomial time?...

Is complete integer factorization randomized polynomial-time reducible to computation of the squarefree part?...

Can one decide in deterministic polynomial time whether an integer $n$ is squarefree?...

Can $\omega(n)$, the number of distinct prime factors of $n$, be computed in deterministic polynomial time?...

Let $C_{10}$ find $x$ satisfying $x^e\equiv a\pmod n$ under $\gcd(e,\varphi(n))=\gcd(a,n)=1$. Is complete integer factorization randomized polynomial-...