Mathematics Problem Archive

Call an infinite connected graph $G$ of uniformly bounded degree an infinite expander if there is a constant $c>0$ such that, for every vertex set $S$...

Does there exist a graph $G$ and a map $f:V(G)\to\mathbb{R}^2$ such that $|\|f(x)-f(y)\|_2-d_G(x,y)|<C$ for every $x,y\in V(G)$ and some constant $C<\...

Must every vertex-transitive graph of exponential growth contain an infinite subgraph $H$ with positive Cheeger constant $h(H)>0$? Can $H$ always be c...

Must every graph with uniform exponential volume growth contain an infinite subgraph, possibly a tree, having positive Cheeger constant?...

Does there exist a vertex-transitive graph whose multiplicative rough-isometry constants to its $k$-net graphs tend to $1$ as $k\to\infty$?...

Does there exist a graph for which repeatedly passing to $k$-net graphs, at appropriately chosen scales, produces strictly smaller large-scale graph m...

Let $G$ be vertex-transitive and let $G_k$ be a $k$-net graph of $G$. Must $h(G_k)\ge h(G)$ whenever $G_k$ is not a single vertex?...

There is a positive function $f(h,d,k)$ such that every graph $G$ with $h(G)>h>0$ and maximum degree less than $d$ has $h(G_k)>f(h,d,k)$ for each $k$-...

Must every Cayley graph of superlinear growth contain, up to rough isometric embedding, either the square grid $\mathbb{Z}^2$ or an infinite binary tr...

If an infinite graph is $C$-roughly transitive for some finite $C$, must it be roughly isometric to a homogeneous metric space? Equivalently, does the...

For every Cayley graph $G$, does there exist $r=r(G)$ such that $G$ covers every graph whose radius-$r$ balls are all isomorphic to the radius-$r$ bal...

Fix a rooted radius-$r$ ball $B(o,r)$ that occurs as every radius-$r$ ball of some finite graph. What is the minimum diameter of a finite graph all of...

Let $G$ be an $n$-vertex graph whose rooted balls of size $k$ are all isomorphic. If $k>n/2$, or if $k$ is within a fixed constant of $\operatorname{d...

If an infinite vertex-transitive graph is $f(r)$-sofic for some function $f$, must it be $cr$-sofic for a constant $c$? More uniformly, for fixed degr...

Prove that no infinite connected Ramanujan graph is Liouville; equivalently, every such graph admits a nonconstant bounded harmonic function....

Suppose $\mathbb{Z}$ acts on a graph $G$ by isometries, the quotient $H=G/\mathbb{Z}$ is Liouville, and simple random walk on $G$ visits every transla...

Let $(G_k)$ be a locally convergent sequence of bounded-degree graphs, each having separation profile of order at most the square root of the subgraph...

Prove that there is a universal constant $C$ such that every finite connected vertex-transitive graph $G$ of degree $d$ satisfies $$R_{\mathrm{eff}}(u...

Does there exist a family $(G_n)$ of finite $d$-regular graphs with $|G_n|\to\infty$ and a constant $h>0$ such that every induced metric ball in every...