Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results
One result of this kind was proved by Lipton "On proving that a graph has no large clique: A connection with Ramsey theory". He connects lower bound conjectures with purely graph theoretic results, showing that if $NP$ is not contained in $coNTIME(n^{O(\log n)})/(\log \log n)$, then the inapproximability of $MAX-CLIQUE$ implies that there are graphs with neat Ramsey-theoretic properties. (See the paper for definitions.) I have no idea if any progress has been made on proving whether or not such graphs actually exist.