PreprintarXiv licencearXiv
A short proof that R(3,k)=Θ(k2/log k)
Abstract
We give a nibble-free construction proving R(3,k)≥(1/200+o(1))k2/log k. We also include Shearer's proof bounding the independence number of a triangle-free graph, which implies R(3,k)≤ (1+o(1))(k2/log k).
Related
- A short proof of the Bernoulli decomposition theorem
- A short proof of the complete Crouzeix inequality in dimension three
- No braiding for quantum sl2 reps - A short proof
- A Short Proof of Zhang's Conjecture on Stack-Sortable Permutations
- A very short proof of the subgaussian convex-order comparison theorem
BibTeX
@misc{harris2026short,
title = {{A short proof that $R(3,k)=Θ(k^2/\log k)$}},
author = {Samuel Harris and Zion Hefty and Paul Horn and Dylan King and Florian Pfender},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01782},
eprint = {2609.01782},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01782},
}
RIS
TY - UNPB
TI - A short proof that R(3,k)=Θ(k^2/log k)
AU - Samuel Harris
AU - Zion Hefty
AU - Paul Horn
AU - Dylan King
AU - Florian Pfender
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01782
UR - https://arxiv.org/abs/2609.01782
AB - We give a nibble-free construction proving R(3,k)≥(1/200+o(1))k^2/log k. We also include Shearer's proof bounding the independence number of a triangle-free graph, which implies R(3,k)≤ (1+o(1))(k^2/log k).
ER -