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 (h2)/2$ holds. We define a class of homogeneous algebraic graphs with even cycle indicator $h$ and codimension $(h2)/2$. It contains geometries $A_2(F)$, $B_2(F)$ and $G_2(F)$ and infinitely many other homogeneous algebraic graphs.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 commutative integrity ringshomogeneous algebraic graphscodimensiongirth indicatorgirth
 Contact author(s)
 vasylustimenko @ yahoo pl
 History
 20230114: revised
 20221029: received
 See all versions
 Short URL
 https://ia.cr/2022/1489
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1489, author = {Vasyl Ustimenko}, title = {On new results on Extremal Algebraic Graph Theory and their connections with Algebraic Cryptography}, howpublished = {Cryptology ePrint Archive, Paper 2022/1489}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1489}}, url = {https://eprint.iacr.org/2022/1489} }