Geodesic
On recursion relations in the problem of enumeration of posets
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 190-207.

Voir la notice de l'article provenant de la source Math-Net.Ru

In two previous works of the author, published in this journal, a series of formulas are obtained related to the themes of enumeration of partial orders (finite topologies). In the first work, a formula is proved that reduces the calculation of the number $T_0(n)$ of all partial orders defined on an $n$-set to the calculation of the numbers $W(p_1,\ldots,p_k)$ of partial orders of a special form. In the second paper, a partially convolute formula is obtained for the number $T_0(n)$. Relations of a recurrent nature are obtained that relate the individual values $W(p_1,\ldots,p_k).$ Explicit formulas are presented for calculating the individual values $W(p_1,\ldots,p_k). $ In this paper, we obtain new recurrence relations that relate the separate numbers $W(p_1,\ldots,p_k)$ between themselves. The obtained equations are enough to calculate without the computer the numbers $T_0(n)$ for all $n9.$ To calculate the number $T_0(9)$ of these relations not enough (the number of required numbers $W(p_1,\ldots,p_k)$ is $128$, and the rank of the system matrix is $123$; there are not enough five equations generating the desired rank). We admit the presence of some general regularity generating new formulas.
Keywords: graph enumeration, poset, finite topology. 
@article{SEMR_2020_17_a61,
     author = {V. I. Rodionov},
     title = {On recursion relations in the problem of enumeration of posets},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {190--207},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a61/}
}
TY  - JOUR
AU  - V. I. Rodionov
TI  - On recursion relations in the problem of enumeration of posets
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 190
EP  - 207
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a61/
LA  - ru
ID  - SEMR_2020_17_a61
ER  - 
%0 Journal Article
%A V. I. Rodionov
%T On recursion relations in the problem of enumeration of posets
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 190-207
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a61/
%G ru
%F SEMR_2020_17_a61
V. I. Rodionov. On recursion relations in the problem of enumeration of posets. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 190-207. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a61/

[1] V.I. Rodionov, “On enumeration of posets defined on finite set”, Siberian electr. Math. Reports, 13 (2016), 318–330 | MR | Zbl

[2] V.I. Rodionov, “On recurrence relation in the problem of enumeration of finite posets”, Siberian electr. Math. Reports, 14 (2017), 98–111 | MR | Zbl

[3] G. Brinkmann, B.D. McKay, “Posets on up to 16 points”, Order, 19:2 (2002), 147–179 | MR | Zbl

[4] Kh.Sh. Al' Dzhabri, V.I. Rodionov, “The graph of partial orders”, Vestn. Udmurt. Univ., Mat. Mekh. Komp'yut. Nauki, 4 (2013), 3–12 | Zbl

[5] Kh.Sh. Al' Dzhabri, “The graph of reflexive-transitive relations and the graph of finite topologies”, Vestn. Udmurt. Univ., Mat. Mekh. Komp'yut. Nauki, 25:1 (2015), 3–11 | Zbl

[6] Kh.Sh. Al' Dzhabri, V.I. Rodionov, “The graph of acyclic digraphs”, Vestn. Udmurt. Univ., Mat. Mekh. Komp'yut. Nauki, 25:4 (2015), 441–452 | Zbl

[7] Kh.Sh. Al' Dzhabri, V.I. Rodionov, “On support sets of acyclic and transitive digraphs”, Vestn. Udmurt. Univ., Mat. Mekh. Komp'yut. Nauki, 27:2 (2017), 153–161 | MR | Zbl

[8] V.I. Rodionov, “On the number of labeled acyclic digraphs”, Discrete Mathematics, 105:1–3 (1992), 319–321 | MR | Zbl

[9] L. Comtet, “Recouvrements, bases de filtre et topologies d'un ensemble fini”, C. R. Acad. Sci., 262 (1966), A1091–A1094 | MR | Zbl

[10] V. Krishnamurthy, “On the number of topologies on a finite set”, Amer. Math. Monthly, 73:2 (1966), 154–157 | MR | Zbl

[11] M. Erne, “Struktur- und anzahlformeln fur topologien auf endlichen mengen”, Manuscripta Math., 11 (1974), 221–259 | MR | Zbl

[12] Z.I. Borevich, “Enumeration of finite topologies”, J. Sov. Math., 20:6 (1982), 2532–2545 | MR | Zbl

[13] J.W. Evans, F. Harary, M.S. Lynn, “On the computer enumeration of finite topologies”, Comm. ACM, 10:5 (1967), 295–297 | Zbl

[14] S.K. Das, “A machine representation of finite $T_0$ topologies”, J. Assoc. Comput. Mach., 24:4 (1977), 676–692 | MR | Zbl

[15] Z.I. Borevich, W. Wieslaw, E. Dobrowolski, V.I. Rodionov, “The number of labeled topologies on nine points”, J. Sov. Math., 37:2 (1987), 937–942 | MR | Zbl

[16] Z.I. Borevich, V.V. Bumagin, V.I. Rodionov, “Number of labeled topologies on ten points”, J. Sov. Math., 17:4 (1981), 1941–1945 | MR | Zbl

[17] M. Erne, K. Stege, “Counting finite posets and topologies”, Order, 8:3 (1991), 247–265 | MR | Zbl

[18] M. Benoumhani, M. Kolli, “Finite topologies and partitions”, J. Integer Seq., 13:3 (2010), 10.3.5, 19 pp. | MR | Zbl

[19] D. Kim, Y.S. Kwon, J. Lee, “Enumerations of finite topologies associated with a finite graph”, Kyungpook Math J., 54:4 (2014), 655–665 | MR | Zbl

[20] M. Kolli, “Direct and elementary approach to enumerate topologies on a finite set”, J. Integer Seq., 10:3 (2007), 07.3.1, 11 pp. | MR | Zbl

[21] C. Marijuan, “Finite topologies and digraphs”, Proyecciones Journal of Mathematics, 29:3 (2010), 291–307 | MR | Zbl

[22] K. Ragnarsson, B.E. Tenner, “Obtainable sizes of topologies on finite sets”, J. Comb. Theory, Ser. A, 117:2 (2010), 138–151 | MR | Zbl

[23] N.P. Adamenko, I.G. Velichko, “Classification of Topologies on Finite Sets Using Graphs”, Ukrainian Mathematical Journal, 60:7 (2008), 1164–1167 | MR | Zbl

[24] I.G. Velichko, P.G. Stegantseva, N.P. Bashova, “The listing of topologies close to the discrete one on finite sets”, Russian Math., 59:11 (2015), 19–25 | MR | Zbl