×

zbMATH — the first resource for mathematics

Number of cyclically irreducible words in the alphabet of a free group of finite rank. (English. Russian original) Zbl 1142.68056
Cybern. Syst. Anal. 43, No. 4, 499-506 (2007); translation from Kibern. Sist. Anal. 2007, No. 4, 39-48 (2007).
Summary: It is shown that a formula that was independently obtained earlier for the number of cyclically irreducible words of length \(n\) in a symmetric alphabet of a finitely generated free group of rank \(k\) and the Whitney formula for a chromatic polynomial of a simple nonself-intersecting cycle of length \(n\) with a variable \(\lambda \) are mutually deducible from one another when \(\lambda = 2k\). The necessary bijections differ for even and odd values of \(n\).

MSC:
68R15 Combinatorics on words
05C15 Coloring of graphs and hypergraphs
20E05 Free nonabelian groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. M. Koganov, ”Number of cyclically irreducible words in the alphabet of a free group,” in: O. B. Lupanov (ed.), Abstracts of the XIIIth Intern. Conf. on Problems of Theor. Cybernetics, Izd-vo Tsentra Prikl. Issled., Mekh.-Mat. Fak. MGU, Moscow (2002), p. 85. · Zbl 1142.68056
[2] L. M. Koganov, ”Two deductions of an explicit closed expression for the number of cyclically irreducible words of fixed length in a free group,” in: O. B. Lupanov (ed.), Proc. VIIIth Intern. Seminar ” Discrete Mathematics and Its Applications,” Izd-vo Mekh.-Mat. Fak. MGU, Moscow (2004), pp. 203–204.
[3] L. M. Koganov, ”A question of R. I. Grigorchuk and problems connected with it,” in: Proc. VIIth Intern. Seminar ”Discrete Mathematics and Its Applications,” Vol. 3, Izd-vo Mekh.-Mat. Fak. MGU, Moscow (2001), pp. 363–364.
[4] I. Rivin, ”Growth in free groups (and other stories),” in: arXiv: math. CO/9911076_v 2; (1999), pp. 1–31.
[5] I. Rivin, ”Some properties of the conjugacy class growth function,” Contemporary Mathematics, 360, 113–117 (2004). · Zbl 1071.20504
[6] H. Whitney, ”The colorings of graphs,” Ann. Math. (2), 33, 688–718 (1932). · JFM 58.0606.01 · doi:10.2307/1968214
[7] H. Whitney, ”A logical expansion in mathematics,” Bull. Amer. Math. Soc., 38, 572–579 (1932). · JFM 58.0605.08 · doi:10.1090/S0002-9904-1932-05460-X
[8] R. C. Read, ”An introduction to chromatic polynomials,” J. Combinat. Theory, 4, No. 1, 52–71 (1968). · Zbl 0173.26203 · doi:10.1016/S0021-9800(68)80087-0
[9] M. O. Asanov, V. A. Baranskii, and V. V. Rasin, Discrete Mathematics: Graphs, Matroids, and Algorithms [in Russian], Regular and Chaotic Dynamics (R&C Dynamics), Moscow-Izhevsk (2001).
[10] M. Bocher, Introduction to Higher Algebra [Russian translation], GTTI (1933).
[11] A. D. Mednykh, ”Determination of the number of nonequivalent coverings over a compact Riemann surface,” in: Dokl. Akad. Nauk SSSR, 239, No. 2, 269–271 (1978). · Zbl 0395.30034
[12] A. D. Mednykh, ”Branched coverings of Riemann surfaces whose branch orders coincide with the multiplicity,” Comm. in Algebra, 18, No. 5, 1517–1533 (1990). · Zbl 0701.30042 · doi:10.1080/00927879008823980
[13] I. M. Vinogradov, Foundations of Number Theory [in Russian], ONTI, Moscow-Leningrad (1936). · Zbl 0014.20304
[14] Yu. V. Matiyasevich, ”One representation of a chromatic polynomial,” in: Proc. Sobolev Institute of Mathematics SB RAS, Methods of Discrete Analysis in Control Systems Theory, No. 31, 61–70, Novosibirsk (1977). · Zbl 0435.05025
[15] R. P. Stanley, Enumerative Combinatorics [Russian translation], Vol. 1, Mir, Moscow (1990).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.