Mathematics Problem Archive

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$-...

Start with a unit square and repeatedly choose a current square uniformly and subdivide it into four squares. Let $D_n$ be the minimum number of curre...

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...

Let $G$ be an infinite bounded-degree graph. Prove that $\operatorname{I-dim}(G)>1$ implies $p_c(G)<1$. As a weaker target, prove the conclusion when ...

Does the law of loop-erased random walk on $\mathbb{Z}^d$ have the exponential intersection-tail property: for two independent sampled paths $\gamma_1...

For some $d\ge3$, is there a probability measure on embeddings of $\mathbb{Z}^2$ into $\mathbb{Z}^d$ having an analogue of the exponential intersectio...

For a subset $S=\{(n,f(n),g(n)):n\in\mathbb{N}\}\subset\mathbb{Z}^3$, characterize the conditions on $f$ and $g$ under which $S$ supports a probabilit...

Let $G$ be vertex-transitive with positive Cheeger constant. If $\mu$ is the connective constant of self-avoiding walks and $\mu_{\mathrm{loops}}$ is ...

Prove that the connective constant $\mu(G)$ is continuous under local convergence of infinite vertex-transitive graphs....

Prove that every graph $G$ with isoperimetric dimension greater than $1$ has self-avoiding-walk connective constant $\mu(G)>1$....

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...

Let $T_n$ be a uniform triangulation of the sphere with $n$ faces, normalize its circle packing by its conformal barycenter, and let $\mu_{P T_n}$ be ...

Let $G$ be a planar graph circle-packed in $\mathbb{R}^2$ and let $f:V(G)\to\mathbb{Z}$ change by at most one across every edge. Add from each vertex ...

In the circle-packed planar-doubling setting of Section 7, prove that the expected distance of simple random walk from its root at time $t$ is at most...

Let $G$ be a planar triangulation with uniform volume growth faster than quadratic. Must $p_c(G)<1$? More strongly, is $p_c(G)=1/2$?...

For every infinite vertex-transitive graph $G$, prove that Bernoulli percolation has no infinite cluster at criticality, i.e. $\theta_G(p_c(G))=0$....

Let $X$ be a finite-energy, translation-invariant percolation process on $\mathbb{Z}^2$ satisfying the FKG inequality. If $X$ percolates almost surely...

Let $H_k$ be a $k$-regular planar triangulation. At the critical percolation parameter for the event that an open cluster contains a full infinite bin...

Does there exist an automorphism-invariant finite-energy percolation subgraph $X$ of $\mathbb{Z}^d$ that percolates almost surely but whose own Bernou...

For which $p$ does there exist $C<\infty$ such that, for any vertices $x,y$ and any $z$ on a geodesic from $x$ to $y$, $$\mathbb{P}_p(x\leftrightarrow...

Prove that a transient simple branching random walk on any vertex-transitive graph has infinitely many ends....

If $G$ is strongly amenable, can Bernoulli percolation on $G\times\mathbb{Z}$ have infinitely many infinite clusters throughout a nondegenerate interv...

Let $G$ be an infinite graph with $p_c(G)=1$. For Bernoulli percolation on $G\times\mathbb{Z}$, must every infinite cluster intersect each fiber $\{v\...

Let $G$ be a bounded-degree expander and suppose some vertex $v$ satisfies $$\mathbb{P}_{1/2}\!\left(\operatorname{diam}(K_v)>\tfrac12\operatorname{di...

Can two simple random walks on $\mathbb{Z}^3$ or $\mathbb{Z}^4$, started at vertices at graph distance $10$, be coupled so that their paths are disjoi...

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$ be the one-skeleton of a bounded-degree triangulation of an open disk. If $G$ is transient, prove that Bernoulli site percolation with paramet...

Tile the unit square by finitely or countably many squares of varying sizes, with at most three squares meeting at a corner, and color the squares ind...

Let $G$ be a bounded-degree triangulation of an open disk with polynomial volume growth. Prove that its Bernoulli site-percolation critical probabilit...

Let $G$ be the one-skeleton of a bounded-degree recurrent triangulation of an open disk. Prove that Bernoulli site percolation with parameter $1/2$ ha...

Let $G$ be the one-skeleton of a bounded-degree transient triangulation of an open disk. Prove that Bernoulli site percolation with parameter $1/2$ ha...

In the Poincaré disk, sample a Poisson process of intensity $\lambda$ with respect to hyperbolic area, form its Voronoi tessellation, and color cells ...

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...

Construct the Poisson–Voronoi tessellation of the plane equipped with an $\ell_p$ metric and give the cells their adjacency graph metric. What is the ...

Delete each edge of the square lattice independently with probability $q<1/2$, condition the origin to lie in the infinite component, and let $K_q$ be...

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...

Among all finite connected vertex-transitive graphs rescaled by their diameters, which one minimizes Gromov–Hausdorff distance to the round sphere $S^...

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...

Let the Euclidean plane or hyperbolic plane have a triangulation whose triangles have diameter at most $r$. Suppose that for every pair of radius-$r$ ...

Characterize the graphs that occur as tangency, or nerve, graphs of sphere packings with disjoint interiors in $\mathbb{R}^d$....