Paper 2022/1489

On new results on Extremal Algebraic Graph Theory and their connections with Algebraic Cryptography

Abstract

Homogeneous algebraic graphs defined over arbitrary field are classical objects of Algebraic Geometry. This class includes geometries of Chevalley groups $A_2(F)$, $B_2(F)$ and $G_2(F)$ defined over arbitrary field $F$. Assume that codimension of homogeneous graph is the ratio of dimension of variety of its vertices and the dimension of neighbourhood of some vertex. We evaluate minimal codimension $v(g)$ and $u(h)$ of algebraic graph of prescribed girth $g$ and cycle indicator. Recall that girth is the size of minimal cycle in the graph and girth indicator stands for the maximal value of the shortest path through some vertex. We prove that for even $h$ the inequality $u(h) \le (h-2)/2$ holds. We define a class of homogeneous algebraic graphs with even cycle indicator $h$ and codimension $(h-2)/2$. It contains geometries $A_2(F)$, $B_2(F)$ and $G_2(F)$ and infinitely many other homogeneous algebraic graphs.