Skip to main content

All Questions

Filter by
Sorted by
Tagged with
23 votes
1 answer
1k views

Universal graph

A connected (and infinite) graph $U$ will be called $n$-universal if any connected graph with degree $\leqslant n$ admits an embedding in $U$. Is there a 3-universal graph with bounded degree?
Anton Petrunin's user avatar
7 votes
1 answer
283 views

Are two quasi-isometric, isomorphic on large enough balls, transitive graphs isomorphic?

Take two transitive graphs $X,Y$ (potentially directed and edge-labelled, e.g. Cayley graphs). Assume $X,Y$ are quasi-isometric with constant $K$, i.e. there exists a function $f:VX \to VY$ ($VX,\,VY$ ...
user148575's user avatar