← All problems

Triangle-free Rank–Ramsey existence question of Beniamini, Linial, and Shraibman

Does there exist a sequence of triangle-free graphs GnG_n with ∣V(Gn)∣=n|V(G_n)|=n such that, for a coefficient field K\mathbb K, ρK(Gn)=rank⁡K(AGn+In)=o(n)\rho_{\mathbb K}(G_n)=\operatorname{rank}_{\mathbb K}(A_{G_n}+I_n)=o(n)?

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 4141.
  • Beniamini, Linial, and Shraibman (2024): constructions with logarithmic clique number and complement rank O(n2/3)\mathcal{O}(n^{2/3}).
  • Beniamini, Linial, and Shraibman (2024): Rank–Ramsey numbers determined when complement rank is at most 55.

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 4(2/3)3/4n3/44(2/3)^{3/4}n^{3/4} 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.

Sources

Solutions 0

No solutions have been posted yet.