Triangle-free Rank--Ramsey graphs from ordered incidence lifts
Abstract
For a graph G with adjacency matrix AG and a coefficient field ๐, put ฯ๐(G)=rank๐(AG+I). We answer the triangle-free Rank--Ramsey existence question of Beniamini, Linial and Shraibman. For every order n, we construct a triangle-free graph Hn such that, simultaneously over all coefficient fields, ฯ๐(Hn)=(4(2/3)3/4+o(1))n3/4, with an error uniform in the field. The graphs can be chosen Hamiltonian for all sufficiently large n. Our method combines ordered layers of point--line incidence flags with a common low-dimensional endpoint space. We determine the exact real rank, independence number and chromatic number of the affine lifts. For all triangle-free complete incidence lifts, we obtain a sharp two-term lower bound for complete incidence lifts, with sharpness witnessed by projective-plane incidence graphs over suitable coefficient fields. We also establish a third-order estimate and stability near equality. On the same explicit graphs, both the Lovรกsz number and minimum semidefinite rank exceed the prescribed Boolean-matrix rank by polynomial factors. Thus neither parameter has a universal constant-factor upper bound in terms of complement rank. We determine Shannon capacity in the short-layer range.
Related
- Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
- Ordered matchings versus triangles via pseudorandom triangle-free graphs
- New results on cyclic and ordered Ramsey numbers
- Ordered Trees with Linear Off-Diagonal Ramsey Numbers
- A General Upper Bound on Multicolor Ordered Ramsey Numbers
BibTeX
@misc{lu2026trianglefree,
title = {{Triangle-free Rank--Ramsey graphs from ordered incidence lifts}},
author = {Yong Lu and Qi Wu and Qiannan Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22902},
eprint = {2610.22902},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22902},
note = {CC0},
}
RIS
TY - UNPB
TI - Triangle-free Rank--Ramsey graphs from ordered incidence lifts
AU - Yong Lu
AU - Qi Wu
AU - Qiannan Zhou
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.22902
UR - https://arxiv.org/abs/2610.22902
AB - For a graph G with adjacency matrix A_G and a coefficient field ๐, put ฯ_๐(G)=rank_๐(A_G+I). We answer the triangle-free Rank--Ramsey existence question of Beniamini, Linial and Shraibman. For every order n, we construct a triangle-free graph H_n such that, simultaneously over all coefficient fields, ฯ_๐(H_n)=(4(2/3)^3/4+o(1))n^3/4, with an error uniform in the field. The graphs can be chosen Hamiltonian for all sufficiently large n. Our method combines ordered layers of point--line incidence flags with a common low-dimensional endpoint space. We determine the exact real rank, independence number and chromatic number of the affine lifts. For all triangle-free complete incidence lifts, we obtain a sharp two-term lower bound for complete incidence lifts, with sharpness witnessed by projective-plane incidence graphs over suitable coefficient fields. We also establish a third-order estimate and stability near equality. On the same explicit graphs, both the Lovรกsz number and minimum semidefinite rank exceed the prescribed Boolean-matrix rank by polynomial factors. Thus neither parameter has a universal constant-factor upper bound in terms of complement rank. We determine Shannon capacity in the short-layer range.
ER -