Triangle-free Rank–Ramsey existence question of Beniamini, Linial, and Shraibman
Does there exist a sequence of triangle-free graphs with such that, for a coefficient field , ?
References
- Triangle-free Rank--Ramsey graphs from ordered incidence lifts — arXiv — Yong Lu, Qi Wu, Qiannan Zhou
Source: arXiv
Progress summary
An October 2026 unrefereed preprint claims to solve the existence question by giving explicit triangle-free graphs, but the claim has not been independently verified.
Beniamini, Linial, and Shraibman introduced the Rank–Ramsey problem in 2024, asking for triangle-free graphs whose complement adjacency matrices have unusually small rank. Their paper established substantial partial constructions but did not settle this triangle-free existence question.
Known results
- Beniamini, Linial, and Shraibman (2024): constructions with bounded clique number, as low as .
- Beniamini, Linial, and Shraibman (2024): constructions with logarithmic clique number and complement rank .
- Beniamini, Linial, and Shraibman (2024): Rank–Ramsey numbers determined when complement rank is at most .
October 16, 2026 claimed resolution
Yong Lu, Qi Wu, and Qiannan Zhou's preprint Triangle-free Rank--Ramsey graphs from ordered incidence lifts claims explicit triangle-free graphs with rank asymptotic to uniformly over fields, together with Hamiltonian examples for sufficiently large orders. This would resolve the stated existence problem, but the source is an unrefereed preprint and no independent verification was found.
Current status (as of October 2026): The existence question is claimed solved by an unrefereed preprint, but the claim is not independently verified.
Solutions 0
No solutions have been posted yet.