论文标题
$ \ mathbb {f} _2 $ rank和图的大小
The $\mathbb{F}_2$-Rank and Size of Graphs
论文作者
论文摘要
我们考虑了订单$ 2^n $的极端图，其中两个顶点都有相同的社区，但是邻接矩阵在两个元素的领域中仅排名$ n $。代数几何形状的先前结果表明，甚至所有$ n $都存在此类图，并且对于Odd $ n $而言都不存在。在本文中，我们为此结果提供了一个新的组合证明，为具有这些属性的图形结构提供了更大的见解。我们引入了与Kronecker产品密切相关的新图形产品，然后是任何什至$ n $的构造。此外，我们表明这是一个无限规范的准随机图家族，其签名的邻接矩阵是对称的Hadamard矩阵。相反，我们提供了一个组合证明，表明对于所有奇数$ n $，都没有最小值的$ \ mathbb {f} _2 $ -rank存在，并且下一个最佳级别等级$（n+1）$是可实现的，这很紧。
We consider the extremal family of graphs of order $2^n$ in which no two vertices have identical neighbourhoods, yet the adjacency matrix has rank only $n$ over the field of two elements. A previous result from algebraic geometry shows that such graphs exist for all even $n$ and do not exist for odd $n$. In this paper we provide a new combinatorial proof for this result, offering greater insight to the structure of graphs with these properties. We introduce a new graph product closely related to the Kronecker product, followed by a construction for such graphs for any even $n$. Moreover, we show that this is an infinite family of strongly-regular quasi-random graphs whose signed adjacency matrices are symmetric Hadamard matrices. Conversely, we provide a combinatorial proof that for all odd $n$, no twin-free graphs of minimal $\mathbb{F}_2$-rank exist, and that the next best-possible rank $(n+1)$ is attainable, which is tight.
