Improved Explicit and Algorithmic Lower Bounds for r(5,t)

We modify a construction of Bradač \cite{Bradac26} using a vertex ordering to give, for every prime power $q$, an explicit $K_5$ free graph with more than $q^7$ vertices and independence number below $600q^4$. This shows $$r(5,t)=\mathrm{\Omega }(t^{7\mathrm{/}4})\mathrm{.}$$ Additionally, pruning a graph defined by the Coulter and Matthews polynomial $X^{14}$ \cite{CM}, we give a deterministic polynomial time construction proving $$r(5,t)=\mathrm{\Omega }\left(t^{20\mathrm{/}11-\epsilon }\right)$$ for every fixed $\epsilon >0$. These results improve the constructive lower bound $\mathrm{\Omega }(t^{5\mathrm{/}3})$ of Kostochka, Pudlák and Rödl \cite{KPR}.