"The latter happens to be a special case of the latter" is rather tautological.

I didn't say that $f$ had to be injective. The finite case is equivalent to the infinite case by using Tychonoff compactness: Wlog $G$ is connected, and your favourite vertex $v$ is at the origin; then a vertex $u$ of distance $n$ from $v$ must lie in the compact ball of radius $n$. So the space of possible functions is a product of compact sets, and constraints of the form $|f(x) - f(y)| = 1$ define closed sets. By the finite case, any finite intersection of these sets is non-empty, so we are done by compactness.

It's infuriating that (as far as I can tell) there isn't an order-3 projective plane embedded as a subset of the order-7 projective plane, as excising it would give a tight lower bound of $300$.

So, @GregKuperberg, are you implying Erdős is the sluttiest mathematician in history?

We already can solve this inequality. Each side is non-negative, so an equivalent inequality is obtained by raising each side to the fourth power, whence we get an inequality in rational functions. Then scale to get a polynomial inequality, which can be expressed as a sum of squares by Delzell's algorithm. Then that is trivially non-negative.

I don't think this is research-level, since it can (if true) be proved by converting to an equivalent polynomial inequality and appealing to Charles Delzell's explicit algorithm for expressing any positive-semidefinite polynomial as a sum of squares of rational functions (c.f. Hilbert's seventeenth problem).

Except that can never be the case, since $a = 2^n - rp$ for some integer $r$, so if $q|a$ and $q|p$ then $q|2^n$. It follows that $q = 2$, so $p$ is even. But $p$ is wlog odd by assumption.

You're correct that your method is suboptimal for a single roll. For $p = 7$, there's a probability of $\frac{1}{4}$ of terminating after three flips, so the expectation must be at least $3.75$. But the naive method gives $\frac{24}{7} \approxeq 3.429$.

So we treat the string of coinflips as a uniform random $\omega \in [0, 1)$, the value of which is unknown, and where after the nth flip we have narrowed it down to an interval of width $2^{-n}$? Then terminate once that interval is contained entirely within an interval $[\frac{k}{p}, \frac{k+1}{p})$? I like it!