pipette
ESEspañol

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

Amrit Kandasamy, Lawrence Zhou, Levi Segal

Preprint

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