On linguistic dynamical systems, families of graphs of large girth, and

V. A. Ustimenko

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XIII, Tome 326 (2005), pp. 214-234

Résumé

The paper is devoted to the study of a linguistic dynamical system of dimension $n\ge 2$ over arbitrary commutative ring $K$, i.e. a family $F$ of nonlinear polynomial maps $f_\alpha\colon K^n\to K^n$ depending on “time” $\alpha\in\{K-0\}$ such that $f_\alpha^{-1}=f_{-\alpha}$, $f_{\alpha_1}(x)=f_{\alpha_2}(x)$ for some $x\in K^n$ implies $\alpha_1=\alpha_2$, and each map $f_\alpha$ has no invariant points. The neighbourhood $\{f_\alpha(v)|\alpha\in K-\{0\}\}$ of an element $v$ defines the graph $\Gamma(F)$ of a dynamical system on the vertex set $K^n$. We shall refer to $F$ as a linguistic dynamical system of rank $d\ge 1$ if for each string $\mathrm{a}=(\alpha_1,\dots,\alpha_s)$, $s\le d$, where $\alpha_i+\alpha_{i+1}$ is a nonzero divisor for $i=1,\dots,d-1$, the vertices $v$ and $v_{\mathrm{a}}=f_{\alpha_1}\times\dots\times f_{\alpha_s}(v)$ in the graph are connected by a unique pass. For each commutative ring $K$ and even integer number $n\ne 0$ mod 3 there is a family of linguistic dynamical systems $L_n(K)$ of rank $d\ge 1/3n$. Let $L(n, K)$ be the graph of a dynamical system $L_n(q)$. If $K=F_q$, the graphs $L(n, F_q)$ form a new family of graphs of large girth. The projective limit $L(K)$ of $L(n,K)$, $n\to\infty$, is well defined for each commutative ring $K$, in the case of integral domain $K$ the graph $L(K)$ is a forest. If $K$ has zero divisors, then the girth of $K$ is dropping to 4. We introduce some other families of graphs of large girth related to the dynamical systems $L_n(q)$ in the case of even $q$. The dynamical systems and related graphs can be used for the development of symmetric or asymmetric cryptographical algorithms. These graphs allow us establish the best known upper bounds on the minimal order of regular graphs without cycles of length $4n$, with $n$ odd $\ge 3$.

Bibliographie

[1] F. Bien, “Constructions of telephone networks by group representations”, Notices Amer. Mah. Soc., 36 (1989), 5–22 | MR | Zbl

[2] N. Biggs, Algebraic Graph Theory, 2nd ed, University Press, Cambridge, 1993 | MR

[3] N. L. Biggs, “Graphs with large girth”, Ars Combinatoria, 25C (1988), 73–80 | MR | Zbl

[4] N. L. Biggs, A. G. Boshier, “Note on the girth of Ramanujan graphs”, Journal of Combinatorial Theory, Series B, 49 (1990), 190–194 | DOI | MR | Zbl

[5] N. L. Biggs, M. J. Hoare, “The sextet construction for cubic graphs”, Combinatorica, 3 (1983), 153–165 | DOI | MR | Zbl

[6] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978 | MR | Zbl

[7] B. Bollobás, Random Graphs, Academic Press, London, 1985 | MR | Zbl

[8] J. A. Bondy, M. Simonovits, “Cycles of even length in graphs”, J. Combinatorial Theory (B), 16 (1974), 97–105 | DOI | MR | Zbl

[9] A. Brouwer, A. Cohen, A. Neumaier, Distance-regular Graphs, Springer, Berlin, 1989 | MR

[10] P. Erdös, H. Sachs, “Regulare Graphen gegebener Taillenweite mit minimaler Krotenzahl”, Wiss. Z. Univ. Halle Martin Luther, Univ. Halle-Wittenberg, Math. Natur. Reine, 12 (1963), 251–257 | MR

[11] N. Koblitz, A Course in Number Theory and Cryptography, Second Edition, Springer, 1994 | MR

[12] N. Koblitz, Algebraic aspects of cryptography, Algorithms and Computations in Mathematics, 3, Springer, 1998 | MR

[13] W. Imrich, “Explicit construction of graphs without small cycles”, Combinatorica, 2 (1984), 53–59 | DOI | MR

[14] F. Lazebnik, V. A. Ustimenko, “New examples of graphs without small cycles and of large size”, Europ. J. of Combinatorics, 14 (1993), 445–460 | DOI | MR | Zbl

[15] F. Lazebnik, V. Ustimenko, “Explicit construction of graphs with an arbitrary large girth and of large size”, Discrete Appl. Math., 60 (1995), 275–284 | DOI | MR | Zbl

[16] F. Lazebnik, V. A. Ustimenko, A. J. Woldar, “A new series of dense graphs of high girth”, Bull (New Series) of AMS, 32:1 (1995), 73–79 | DOI | MR | Zbl

[17] F. Lazebnik, V. A. Ustimenko, A. J. Woldar, “New upper bounds on the order of cages”, Electronic J. Combin., 14 (1997), R13 | MR

[18] F. Lazebnik, V. A. Ustimenko, A. Woldar, “Polarities and $2k$-cycle-free graphs”, Discrete Mathematics, 197–198, 503–513 | MR | Zbl

[19] A. Lubotsky, R. Philips, P. Sarnak, “Ramanujan graphs”, J. Comb. Theory, 115:2 (1989), 62–89

[20] W. Magnus, A. Karrass, D. Solitar, Combinatorial Group Theory, Interscience, 1966

[21] G. A. Margulis, “Explicit construction of graphs without short cycles and low density codes”, Combinatorica, 2 (1982), 71–78 | DOI | MR | Zbl

[22] G. Margulis, “Explicit group-theoretical constructions of combinatorial schemes and their application to desighn of expanders and concentrators”, Probl. Peredachi Informatsii, 24:1, 51–60 | MR | Zbl

[23] M. Margulis, “Arithmetic groups and graphs without short cycles”, 6th Intern. Symp. on Information Theory, vol. 1, Tashkent, 1984, 123–125

[24] H. L. Montgomery, Topics in Multiplicative Number Theory, Lecture Notes in Mathematics, 227, Springer Verlag, New York, 1971 | MR | Zbl

[25] H. Sachs, “Regular graphs with given girth and restricted circuits”, J. London. Math. Soc., 38 (1963), 423–429 | DOI | MR | Zbl

[26] N. Sauer, “Extermaleigenschaften regularer Graphen gegebener Taillenweite, 1, 2”, Osterreich. Acad. Wiss. Math. Natur. Kl. S.-B 2, 176 (1967), 9–25, 27–43 | MR

[27] J. Seberry, J. Pieprzyk, Cryptography: An Introducion to Computer Security, Prentice Hall, 1989 | Zbl

[28] M. Simonovitz, “Extermal graph theory”, Selected Topics in Graph Theory, 2, eds. L. W. Beineke, R. J. Wilson, Academic Press, London, 1983, 161–200 | MR

[29] J. Spencer, The strange logic of random graphs, Springer Verlag, 2001 | MR

[30] W. Tutte, A family of cubical graphs, 43, Proc. Cambridge Philos. Soc., 1945 | MR

[31] V. A. Ustimenko, “Linear interpretation of Chevalley group flag geometries”, Ukrainian Math. J., 43:7,8 (1991), 1055–1060 | MR | Zbl

[32] V. A. Ustimenko, “Coordinatisation of regular tree and its quotients”, Voronoi's Impact on Modern Science, book 2, eds. P. Engel, H. Syta, 1998, 125–152 | Zbl

[33] V. A. Ustimenko, “On the varieties of parabolic subgroups, their generalizations and combinatorial applications”, Acta Applicandae Mathematicae, 52 (1998), 223–238 | DOI | MR | Zbl

[34] V. Ustimenko, “Graphs with special arcs and cryptography”, Acta Applicandae Mathematicae, 74:2 (2002), 117–153 | DOI | MR | Zbl

[35] V. Ustimenko, “CRYPTIM: Graphs as tools for symmetric encryption”, Applied algebra, algebraic algorithms and error-correcting codes. 14th international symposium, AAECC-14, Proceedings (Melbourne, Australia, November 26–30, 2001), Lecture Notes in Comput. Sci., 2227, Springer, New York, 2001, 278–286 | MR | Zbl

[36] V. Ustimenko, “Maximality of affine group and hidden graph cryptsystems”, Algebra and Discrete Mathematics, 2005, no. 1, 133–150 | MR | Zbl

[37] V. A. Ustimenko, D. Sharma, “CRYPTIM: system to encrypt text and image data”, Proceedings of International ICSC Congress on Intelligent Systems (2000, Wollongong), 2001 | Zbl

[38] V. Ustimenko, A. Touzene, “CRYPTALL:system to encrypt all types of data”, Notices of Kiev-Mohyla Academy, 23 (2004), 12–15 | Zbl

[39] Yu. Khmelevsky, V. A. Ustimenko, “Practical aspects of the Informational Systems reengineering”, The South Pacific Journal of Natural Science, 21 (2003); http://www.usp.ac.fj | Zbl

[40] H. Walther, “Eigenschaften von regularen Graphen gegebener Taillenweite und Minimaler Knotzenzahl”, Wiss. Z. Illmenau, 11 (1965), 167–168 | MR | Zbl

[41] H. Walther, “Uber regulare Graphen gegebener Taillenweite und minimaler Knotenzahl”, Wiss. Z. Techn Hochsch. Ilmenau, 11 (1965), 93–96 | MR | Zbl

[42] A. L. Weiss, “Girth of bipartite sextet graphs”, Combinatorika, 4:2–3 (1984), 241–245 | DOI | MR | Zbl