Improved Explicit and Algorithmic Lower Bounds for r(5,t)
In the authors' words
We modify a construction of Brada\v{c} \cite{Bradac26} using a vertex ordering to give, for every prime power , an explicit free graph with more than vertices and independence number below . This shows Additionally, pruning a graph defined by the Coulter and Matthews polynomial \cite{CM}, we give a deterministic polynomial time construction proving for every fixed . These results improve the constructive lower bound of Kostochka, Pudl\'ak and R\"odl \cite{KPR}.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 10 pages