On the homogeneous algebraic graphs of large girth and their applications. (English) Zbl 1156.05028
Summary: Families of finite graphs of large girth were introduced in classical extremal graph theory. One important theoretical result here is the upper bound on the maximal size of the graph with girth \(\geqslant 2d\) established in Even Circuit Theorem by P. Erdös. We consider some results on such algebraic graphs over any field. The upper bound on the dimension of variety of edges for algebraic graphs of girth \(\geqslant 2d\) is established. Getting the lower bound, we use the family of bipartite graphs \(D(n,K)\) with \(n\geqslant 2\) over a field \(K\), whose partition sets are two copies of the vector space \(K^n\). We consider the problem of constructing homogeneous algebraic graphs with a prescribed girth and formulate some problems motivated by classical extremal graph theory. Finally, we present a very short survey on applications of finite homogeneous algebraic graphs to coding theory and cryptography.
MSC:
| 05C35 | Extremal problems in graph theory |
| 14Q15 | Computational aspects of higher-dimensional varieties |
| 05D99 | Extremal combinatorics |
| 05C90 | Applications of graph theory |
| 15A63 | Quadratic and bilinear forms, inner products |
| 81P68 | Quantum computation |
| 94A60 | Cryptography |
| 68Q99 | Theory of computing |
Software:
CRYPTIMReferences:
| [1] | Ambainis, Andris; Nayak, Ashwin; Ta-Shma, Amnon; Vazirani, Umesh, Dense quantum coding and quantum finite automata, J. ACM (JACM), 49, 4, 496-511 (2002) · Zbl 1326.68133 |
| [2] | C. Berrou, A. Glavieux, P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: turbo-codes, ICC 1993, Geneva, Switzerland, 1993, pp. 1064-1070.; C. Berrou, A. Glavieux, P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: turbo-codes, ICC 1993, Geneva, Switzerland, 1993, pp. 1064-1070. |
| [3] | Biggs, N. L., Graphs with large girth, Ars Combin., 25C, 73-80 (1988) · Zbl 0649.05042 |
| [4] | Biggs, N., Algebraic Graph Theory (1993), Cambridge, University Press |
| [5] | Biggs, N. L.; Boshier, A. G., Note on the girth of Ramanujan graphs, J. Combin. Theory, Ser. B, 49, 190-194 (1990) · Zbl 0708.05032 |
| [6] | Biggs, N. L.; Hoare, M. J., The sextet construction for cubic graphs, Combinatorica, 3, 153-165 (1983) · Zbl 0522.05030 |
| [7] | Bollobás, B., Extremal Graph Theory (1978), London Math. Soc. Monograph, Academic Press · Zbl 0419.05031 |
| [8] | Bondy, J. A.; Simonovits, M., Cycles of even length in graphs, J. Combin. Theory, Ser. B, 16, 87-105 (1974) · Zbl 0283.05108 |
| [9] | Brower, A.; Cohen, A.; Nuemaier, A., Distance Regular Graphs (1989), Springer: Springer Berlin · Zbl 0747.05073 |
| [10] | Erdös, P.; Renyi, A.; Soc, V. T., On a problem of graph theory, Studia Math. Hungar., 1, 215-235 (1966) · Zbl 0144.23302 |
| [11] | Erdös, P.; Sachs, H., Regulare Graphen gegebener Taillenweite mit minimaler Krotenzahl, Wiss. Z. Univ. Halle Martin Luther, Univ. Halle-Wittenberg, Math. Natur. Reine, 12, 251-257 (1963) · Zbl 0116.15002 |
| [12] | Erdös, P.; Simonovits, M., Compactness results in extremal graph theory, Combinatorica, 2, 3, 275-288 (1982) · Zbl 0508.05043 |
| [13] | Faudree, W.; Simonovits, M., On a class of degenerate extremal graph problems, Combinatorica, 3, 1, 83-93 (1983) · Zbl 0521.05037 |
| [14] | Feit, W.; Higman, D., The nonexistence of certain generalised polygons, J. Algebra, 1, 114-131 (1964) · Zbl 0126.05303 |
| [15] | Füredi, Z.; Lazebnik, F.; Seress, A.; Ustimenko, V. A.; Woldar, A. J., Graphs of prescribed Girth and Bi-Degree, J. Combin. Theory, Ser. B, 64, 2, 228-239 (1995) · Zbl 0828.05034 |
| [16] | Gallager, R. G., Low-density parity-check codes, IRE Trans. Inform. Theory IT-8, 21-28 (1962) · Zbl 0107.11802 |
| [17] | P. Guinand, J. Lodge, Tanner type codes arising from large girth graphs, in: Proceedings of the 1997 Canadian Workshop on Information Theory (CWIT ’97), Toronto, Ontario, Canada, 1997, pp. 5-7.; P. Guinand, J. Lodge, Tanner type codes arising from large girth graphs, in: Proceedings of the 1997 Canadian Workshop on Information Theory (CWIT ’97), Toronto, Ontario, Canada, 1997, pp. 5-7. |
| [18] | P. Guinand, J. Lodge, Graph theoretic construction of generalized product codes, in: Proceedings of the 1997 IEEE International Symposium on Information Theory (ISIT ’97), Ulm, Germany, 1997, pp. 111-112.; P. Guinand, J. Lodge, Graph theoretic construction of generalized product codes, in: Proceedings of the 1997 IEEE International Symposium on Information Theory (ISIT ’97), Ulm, Germany, 1997, pp. 111-112. |
| [19] | J. Kotorowicz, V.A. Ustimenko, On the implementation of cryptoalgorithms based on agebraic graphs over some commutative rings, in: Condenced Matters Physics, Special Issue: Proceedings of the International Conferences “Infinite particle systems, Complex systems theory and its application, Kazimerz Dolny, Poland, 2006, 11 (2(54)), 2008, pp. 347-360.; J. Kotorowicz, V.A. Ustimenko, On the implementation of cryptoalgorithms based on agebraic graphs over some commutative rings, in: Condenced Matters Physics, Special Issue: Proceedings of the International Conferences “Infinite particle systems, Complex systems theory and its application, Kazimerz Dolny, Poland, 2006, 11 (2(54)), 2008, pp. 347-360. |
| [20] | Imrich, W., Explicit construction of graphs without small cycles, Combinatorica, 2, 53-59 (1984) · Zbl 0535.05033 |
| [21] | Lazebnik, F.; Ustimenko, V., Some algebraic constructions of dense graphs of large girth and of large size, DIMACS Series Discrete Math. Theoret. Comput. Sci., 10, 75-93 (1993) · Zbl 0798.05034 |
| [22] | Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J., New upper bounds on the order of cages, Electron. J. Combin., 14, R13, 1-11 (1997) · Zbl 0885.05078 |
| [23] | Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J., A new series of dense graphs of high girth, Bull. (New Series) AMS, 32, 1, 73-79 (1995) · Zbl 0822.05039 |
| [24] | Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J., A characterization of the components of the graphs \(D(k, q)\), Discrete Math., 157, 271-283 (1996) · Zbl 0861.05051 |
| [25] | Lubotsky, A.; Philips, R.; Sarnak, P., Ramanujan graphs, J. Combin. Theory, 115, 2, 62-89 (1989) |
| [26] | D.J.C. MacKay, R.N. Neal, Good Codes based on very sparse matrices, in: “Cryptography and Coding, 5th IMA Conference, Lecture Notes in Computer Science 1025, 1995, pp. 110-111.; D.J.C. MacKay, R.N. Neal, Good Codes based on very sparse matrices, in: “Cryptography and Coding, 5th IMA Conference, Lecture Notes in Computer Science 1025, 1995, pp. 110-111. |
| [27] | 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. English translation: J. Prob. Inform. Trans., 1988, pp. 39-46.; 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. English translation: J. Prob. Inform. Trans., 1988, pp. 39-46. · Zbl 0708.05030 |
| [28] | M. Margulis, Arithmetic groups and graphs without short cycles, in: 6th Int. Symp. on Information Theory, Tashkent, Abstracts 1, 1984, pp. 123-125 (in Russian).; M. Margulis, Arithmetic groups and graphs without short cycles, in: 6th Int. Symp. on Information Theory, Tashkent, Abstracts 1, 1984, pp. 123-125 (in Russian). |
| [29] | Moura, Jose M. F.; Lu, Jin; Zhang, Haotian, Structured LDPC Codes with Large Girth, IEEE Signal Process. Mag., 21, 1, 42-55 (2004) |
| [30] | Sachs, H., Regular graphs with given girth and restricted circuits, J. London. Math. Soc, 38, 423-429 (1963) · Zbl 0117.17302 |
| [31] | N. Sauer, Extermaleigenschaften regularer Graphen gegebener Taillenweite 1, 2, Osterreich. Acad. Wiss. Math. Natur. Kl. S.-B 2, 176 (1967) 9-25, 27-43.; N. Sauer, Extermaleigenschaften regularer Graphen gegebener Taillenweite 1, 2, Osterreich. Acad. Wiss. Math. Natur. Kl. S.-B 2, 176 (1967) 9-25, 27-43. |
| [32] | (Shaska, T.; Huffman, W. C.; Joyner, D.; Ustimenko, V., Advances in Coding Theory and Cryptography. Advances in Coding Theory and Cryptography, Series on Coding Theory and Cryptology, vol. 3 (2007), World Scientific) · Zbl 1120.94004 |
| [33] | Simonovits, M., Extremal graph theory, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory 2 (1983), Academic Press: Academic Press London), 161-200 · Zbl 0531.05037 |
| [34] | Tanner, R. M., A transform theory for a class of group-invariant codes, IEEE Trans. Inform. Theory, 34, 4, 725-775 (1988) · Zbl 0656.94019 |
| [35] | Michiel Tanner, R., A recursive approach to low density codes, IEEE Trans. Info Th. IT, 27, 5, 533-547 (1984) · Zbl 0474.94029 |
| [36] | Thas, J. A., Generalised polygons, (Buekenhout, F., Handbook in Incidence Geometry (1995), North-Holland: North-Holland Amsterdam), (Chapter 9) · Zbl 0835.51002 |
| [37] | Tits, J., Sur la trialite et certains groupes qui s’en deduisent, Publ. Math. I.H.E.S, 2, 15-20 (1959) · Zbl 0088.37204 |
| [38] | Tits, J.; Weiss, R., Moufang Polygons (2002), Springer-Verlag · Zbl 1010.20017 |
| [39] | Touzene, A.; Ustimenko, V., Graph based private key crypto-system, Int. J. Comput. Res., 13, 3, 275-282 (2005) · Zbl 1122.68053 |
| [40] | V.A. Ustimenko, Random walks on special graphs and Cryptography, Amer. Math. Soc. Meeting, Loisville, March, 1998.; V.A. Ustimenko, Random walks on special graphs and Cryptography, Amer. Math. Soc. Meeting, Loisville, March, 1998. |
| [41] | V.A. Ustimenko, Coordinatization of regular tree and its quotients, in “Voronoi’s Impact in Modern Science”, Proceedings of Memorial Voronoi Conference, Kiev, 1998, Kiev, Institute of Mathematics, 1998, pp. 125-152.; V.A. Ustimenko, Coordinatization of regular tree and its quotients, in “Voronoi’s Impact in Modern Science”, Proceedings of Memorial Voronoi Conference, Kiev, 1998, Kiev, Institute of Mathematics, 1998, pp. 125-152. · Zbl 0946.05026 |
| [42] | V. Ustimenko, D. Sharma, Special Graphs in Cryptography, in: Proceedings of 2000 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2000), Melbourne, 2000.; V. Ustimenko, D. Sharma, Special Graphs in Cryptography, in: Proceedings of 2000 International Workshop on Practice and Theory in Public Key Cryptography (PKC 2000), Melbourne, 2000. |
| [43] | V. Ustimenko, D. Sharma, CRYPTIM: the system to encrypt text and image data, in: Proceedings of International ICSC congress on Intelligent Systems and Applications, 2000, University of Wollongong, 2001, 14pp.; V. Ustimenko, D. Sharma, CRYPTIM: the system to encrypt text and image data, in: Proceedings of International ICSC congress on Intelligent Systems and Applications, 2000, University of Wollongong, 2001, 14pp. |
| [44] | V. Ustimenko, CRYPTIM: Graphs as tools for symmetric encryption, in: Lecture Notes in Computer Science, Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes, November 2001, vol. 2237, Springer, 2001, pp. 278-287.; V. Ustimenko, CRYPTIM: Graphs as tools for symmetric encryption, in: Lecture Notes in Computer Science, Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes, November 2001, vol. 2237, Springer, 2001, pp. 278-287. |
| [45] | Ustimenko, V., Graphs with special arcs and cryptography, Acta Appl. Math., 74, 2, 117-153 (2003) · Zbl 1065.68050 |
| [46] | Ustimenko, V.; Woldar, A., Extremal properties of regular and affine generalised polygons of tactical configurations, Eur. J. Combin., 24, 99-111 (2003) · Zbl 1014.05038 |
| [47] | Ustimenko, V.; Khmelevsky, Yu., Walks on graphs as symmetric and assymetric tools for encryption, South Pacific J. Nat. Stud., 20, 23-41 (2002) |
| [48] | Ustimenko, V., On the extremal graph theory for directed graphs and its cryptographical applications, Advances in Coding Theory and Cryptography. Advances in Coding Theory and Cryptography, Series on Coding Theory and Cryptology, vol. 3 (2007), World Scientific, pp. 181-200 · Zbl 1140.05039 |
| [49] | V. Ustimenko, On the graph based cryptography and symbolic computations, Serdica J. Comput., Proceedings of International Conference on Application of Computer Algebra 2006, Varna 1, 2007, pp. 131-186.; V. Ustimenko, On the graph based cryptography and symbolic computations, Serdica J. Comput., Proceedings of International Conference on Application of Computer Algebra 2006, Varna 1, 2007, pp. 131-186. · Zbl 1256.94067 |
| [50] | V. Ustimenko, On the extremal regular directed graphs without commutative diagrams and their applications in coding theory and cryptography, Albanian. J. Math. (5) (2007) (Special Issue “Algebra and Computational Algebraic Geometry” 1).; V. Ustimenko, On the extremal regular directed graphs without commutative diagrams and their applications in coding theory and cryptography, Albanian. J. Math. (5) (2007) (Special Issue “Algebra and Computational Algebraic Geometry” 1). · Zbl 1135.05030 |
| [51] | Ustimenko, V., On linguistic dynamical systems, graphs of large girth and cryptography, J. Math. Sci., 140, 3, 412-434 (2007) |
| [52] | V. Ustimenko, Algebraic small world graphs of large girth and related groups, Condenced Matters Physics, in: Proceedings of the International Conferences “Infinite particle systems”, Complex systems theory and its application, Kazimerz Dolny, Poland, 2008, in press.; V. Ustimenko, Algebraic small world graphs of large girth and related groups, Condenced Matters Physics, in: Proceedings of the International Conferences “Infinite particle systems”, Complex systems theory and its application, Kazimerz Dolny, Poland, 2008, in press. |
| [53] | Van Assche, Gilles, Quantum Cryptography and Secret-Key Distillation (2006), Cambridge University Press · Zbl 1109.81005 |
| [54] | Walther, H., Eigenschaften von regularen Graphen gegebener Taillenweite und Minimaler Knotzenzahl, Wiss. Z. Illmenau, 11, 167-168 (1965) · Zbl 0137.43203 |
| [55] | Walther, H., Uber regulare Graphen gegebener Taillenweite und inimaler Knotenzahl, Wiss. Z. Techn Hochsch. Ilmenau, 11, 93-96 (1965) · Zbl 0132.21301 |
| [56] | Weiss, A. L., Girth of bipartite sextet graphs, Combinatorika, 4, 2-3, 241-245 (1984) · Zbl 0565.05051 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
