Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper proves that the set of finite graphs admitting a continuous homomorphism from the standard Schreier graph $F(2^{\mathbb Z^d})$ is $\Sigma^0_1$-complete for $d \geq 2$, extending prior work for $d=2$. The positive part of the reduction demonstrates that graphs satisfying a specific property, including $K_4$, admit such a homomorphism, generalizing a result by Gao and Jackson. Additionally, the paper establishes that a sequence of graph classes $(\mathcal H_d)$ is strictly decreasing.
The complexity of continuous graph homomorphisms from higher-dimensional Schreier graphs is fully characterized, revealing a $\Sigma^0_1$-complete set of receiving graphs.
For every fixed integer $d\geq2$, we prove that the finite graphs receiving a continuous homomorphism from the standard Schreier graph $F(2^{\mathbb Z^d})$ form a $Σ^0_1$-complete set. This extends a theorem of Gao, Jackson, Krohne and Seward when $d=2$. For the positive part of the reduction, we show that if a graph $H$ satisfies a certain property then there is a continuous graph homomorphism from $F(2^{\mathbb Z^d})$ to $H$, in particular, the complete graph $K_4$ satisfies this property. This extends a theorem of Gao and Jackson. We also prove that $\big (\mathcal H_d\big )$ is a strictly decreasing sequence.