Number of cyclically irreducible words in the alphabet of a free group of finite rank. (English. Russian original) Zbl 1142.68056

Koganov, L. M.

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

Keywords:

cyclically irreducible word; proper word; chromatic polynomial of a graph; Whitney formula for the chromatic polynomial of a simple cycle

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).