PreprintarXiv licencearXiv
Optimally pseudorandom K4-free graphs
Abstract
We show that optimally pseudorandom K4-free graphs of order n and degree d = Θ(n4/5) exist by constructing a graph in the split Cayley hexagon, matching the known upper bound. This resolves the first open case for Kk-free graphs after k=3 for which Alon gave a tight construction in 1994. This has a variety of implications for K4-free pseudorandom graphs. Furthermore, it implies an explicit lower bound on the Ramsey number of r(4, t) ≥ t1.6̅ − o(1), improving the previous record by Kostochka, Pudlák, and Rödl of r(4, t) ≥ t1.6−o(1).
Related
BibTeX
@misc{han2026optimally,
title = {{Optimally pseudorandom $K_4$-free graphs}},
author = {Jie Han and Ferdinand Ihringer and Hendrik Van Maldeghem},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32461},
eprint = {2609.32461},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32461},
}
RIS
TY - UNPB
TI - Optimally pseudorandom K_4-free graphs
AU - Jie Han
AU - Ferdinand Ihringer
AU - Hendrik Van Maldeghem
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32461
UR - https://arxiv.org/abs/2609.32461
AB - We show that optimally pseudorandom K_4-free graphs of order n and degree d = Θ(n^4/5) exist by constructing a graph in the split Cayley hexagon, matching the known upper bound. This resolves the first open case for K_k-free graphs after k=3 for which Alon gave a tight construction in 1994. This has a variety of implications for K_4-free pseudorandom graphs. Furthermore, it implies an explicit lower bound on the Ramsey number of r(4, t) ≥ t^1.6̅ − o(1), improving the previous record by Kostochka, Pudlák, and Rödl of r(4, t) ≥ t^1.6−o(1).
ER -