Skip to content
Preprint

Triangle-free Rank--Ramsey graphs from ordered incidence lifts

Oct 2026 · 0 citations · 28 references
Mathematics

Abstract

For a graph $G$ with adjacency matrix $A_G$ and a coefficient field $\mathbb K$, put $\rho_{\mathbb K}(G)=\operatorname{rank}_{\mathbb K}(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, $$ \rho_{\mathbb K}(H_n)=\bigl(4(2/3)^{3/4}+o(1)\bigr)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\'asz 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.

View source

Similar papers

Preprint Sep 2026

Ordered matchings versus triangles via pseudorandom triangle-free graphs

For ordered graphs $H_1,\ldots,H_t$, let $\rt(H_1,\ldots,H_t)$ denote the least integer $N$ such that every $t$-coloring of the edges of the naturally ordered complete graph on $[N]$ contains an ordered copy of $H_i$ in color $i$ for some $i\in[t]$. We prove that a uniformly random ordered matching $M$ on $n$ vertices...

Wen Chen, Qizhong Lin, Chun-Lin You · 0 citations
Preprint Sep 2026

Real-rootedness of the $\tau$-polynomial under graph joins

For a simple graph $G$ with $n$ vertices, write its chromatic polynomial in the rising factorial basis as $$ \chi_G(x)=\sum_{i=0}^{n}(-1)^{n-i}c_i(G)\langle x\rangle_i,$$ where $ \langle x\rangle_i=x(x+1)\cdots(x+i-1).$ The associated $\tau$-polynomial $$ \tau_G(x)=\sum_{i=0}^{n}c_i(G)x^i $$ was defined and systematica...

Ming-Yang Kang, Zhi-Xin Liu, Sophie C. C. Sun et al. · 0 citations
Preprint Sep 2026

Exact Second-Order Zarankiewicz Numbers for Complete-Graph Incidence Families

For $n\ge6$, $m=\binom n2$, let the complete-graph incidence family on $K_n$ have the vertices of $K_n$ as columns, its edges as rows, and the incidence graph as one-edge graph. The universal cell bound of L\"ofberg and Qi gives $z_2(m,n)\le Z(n):=\lfloor n(n-1)(n+2)/4\rfloor$. We implement the nested one-factorization...

Yan-Nan Chen, J. Löfberg, Li-Qun Qi · 3 citations · ⚡1
Preprint Oct 2026

Edge complexity of complete bipartite and complete multipartite graphs

We study edge complexity, the minimum Fourier $\ell^1/\ell^2$ ratio of a graph's adjacency matrix over cyclic vertex labelings. For $K_{m,n}$, with $1\leq m\leq n$, we reduce the problem to minimizing the Fourier $\ell^1$-norm of indicators of $m$-element subsets of $\mathbb Z_{m+n}$. We prove the sharp bound $\operato...

S. Ferguson, V. Gupta, A. Iosevich et al. · 0 citations
Preprint Sep 2026

Ordered Ramsey numbers of 3-uniform hypergraphs with bounded weak degeneracy

The \emph{ordered Ramsey number} $r_<(G,H)$ of ordered $k$-graphs $G$ and $H$ is the least integer $N$ such that every red-blue edge-coloring of the naturally ordered complete $k$-graph on $[N]$ contains a blue ordered copy of $G$ or a red ordered copy of $H$. We prove that there is an absolute constant $c>0$ such that...

Wen Chen, Zi-Han He, Qi-Zhong Lin et al. · 0 citations
Preprint Nov 2026

Integral saturation of adjacency-degree lattices

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $\Lambda_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[\Lambda_G\ne\mathbb{Z}^n]\le n^{-3/20+o(1)}$. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultane...

Zhi-Peng Lu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.