PreprintarXiv licencearXiv
Improved Explicit and Algorithmic Lower Bounds for r(5,t)
Abstract
We modify a construction of Bradač \cite{Bradac26} using a vertex ordering to give, for every prime power q, an explicit K5 free graph with more than q7 vertices and independence number below 600q4. This shows r(5,t)=Ω(t7/4). Additionally, pruning a graph defined by the Coulter and Matthews polynomial X14 \cite{CM}, we give a deterministic polynomial time construction proving r(5,t)=Ω(t20/11−ε) for every fixed ε>0. These results improve the constructive lower bound Ω(t5/3) of Kostochka, Pudlák and Rödl \cite{KPR}.
Related
- Improved explicit Burgess-strength bounds for composite moduli
- Explicit and logarithmically improved chromatic bounds for (P2∪ P3)-free graphs
- Explicit upper and lower bounds on certain functions related to ζ(s) for s>1
- Explicit lower bounds on the conductors of elliptic curves and abelian varieties over number fields
- Stability for the adjoint Finner inequality and improved lower bounds on the k-plane transform
BibTeX
@misc{kandasamy2026improved,
title = {{Improved Explicit and Algorithmic Lower Bounds for r(5,t)}},
author = {Amrit Kandasamy and Lawrence Zhou and Levi Segal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06969},
eprint = {2610.06969},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06969},
}
RIS
TY - UNPB
TI - Improved Explicit and Algorithmic Lower Bounds for r(5,t)
AU - Amrit Kandasamy
AU - Lawrence Zhou
AU - Levi Segal
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.06969
UR - https://arxiv.org/abs/2610.06969
AB - 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)=Ω(t^20/11−ε) for every fixed ε>0. These results improve the constructive lower bound Ω(t^5/3) of Kostochka, Pudlák and Rödl \cite{KPR}.
ER -