{"id":"arxiv/2610.06969","url":"https://arxiv.org/abs/2610.06969","tags":["math.CO"],"score":0,"title":"Improved Explicit and Algorithmic Lower Bounds for r(5,t)","domain":"math.CO","source":"arxiv","authors":["Amrit Kandasamy","Lawrence Zhou","Levi Segal"],"reviews":0,"subject":"math.CO","summary":"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)=Ω(t^{7/4}).$$ 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)=Ω\\bigl(t^{20/11-\\varepsilon}\\bigr)$$ for every fixed $\\varepsilon>0$. These results improve the constructive lower bound $Ω(t^{5/3})$ of Kostochka, Pudlák and Rödl \\cite{KPR}.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-03","reactions":{}}