Some unsolved problems in discrete mathematics and mathematical cybernetics

A. D. Korshunov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 64 (2009) no. 5, pp. 787-803

Résumé

There are many unsolved problems in discrete mathematics and mathematical cybernetics. Writing a comprehensive survey of such problems involves great difficulties. First, such problems are rather numerous and varied. Second, they greatly differ from each other in degree of completeness of their solution. Therefore, even a comprehensive survey should not attempt to cover the whole variety of such problems; only the most important and significant problems should be reviewed. An impersonal choice of problems to include is quite hard. This paper includes 13 unsolved problems related to combinatorial mathematics and computational complexity theory. The problems selected give an indication of the author's studies for 50 years; for this reason, the choice of the problems reviewed here is, to some extent, subjective. At the same time, these problems are very difficult and quite important for discrete mathematics and mathematical cybernetics. Bibliography: 74 items.

Détail

Keywords: graph reconstruction by subgraphs, Hamiltonian cycles, disjunctive normal forms, the snake-in-the-box problem, lower bounds, $\mathrm{NP}$-completeness, polynomial problems, Boolean functions hard to compute, cube piercing, perfect binary codes, Steiner triple systems.
Mots-clés : graph isomorphism

Bibliographie

[1] S. A. Cook, “The complexity of theorem-proving procedures”, Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing (Shaker Heights, 1971), ACM Press, New York, 1971, 151–158 ; S. A. Kuk, “Slozhnost protsedur vyvoda teorem”, Kibernet. sb. Nov. ser., 1975, no. 12, 5–15 | Zbl | Zbl

[2] L. A. Levin, “Universal problems of full search”, Probl. Inf. Transm., 9:3 (1973), 265–266 | MR | Zbl

[3] R. M. Karp, “Reducibility among combinatorial problems”, Complexity of computer computations, Proc. Sympos. (IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, 85–103 ; P. M. Karp, “Svodimost kombinatornykh zadach”, Kibernet. sb. Nov. ser., 1975, no. 12, 16–38 | MR | Zbl

[4] M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of $\mathrm{NP}$-completeness, A Series of Books in the Mathematical Sciences, Freeman, San Francisco, 1979 ; M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR | Zbl | MR

[5] R. E. Ladner, “On the structure of polynomial time reducibility”, J. Assoc. Comput. Mach., 22:1 (1975), 155–171 | MR | Zbl

[6] M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of $\mathrm{NP}$-completeness, A Series of Books in the Mathematical Sciences, Freeman, San Francisco, 1979 ; M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR | Zbl | MR

[7] M. Agrawal, N. Kayal, N. Saxena, “PRIMES is in $\mathrm{P}$”, Ann. of Math., 160:2 (2004), 781–793 | DOI | MR | Zbl

[8] J. E. Hopcroft, R. E. Tarjan, “Isomorphism of planar graphs”, Complexity of computer computations, Proc. Sympos. (IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, 131–152, 187–212 ; Dzh. E. Khokroft, R. E. Taryan, “Izomorfizm planarnykh grafov”, Kibernet. sb. Nov. ser., 1975, no. 12, 39–61 \medskip \centerline{\selectlanguage{russian}\bf K razdelu 3} \setcounter{enumi}{0} \smal | MR

[9] B. A. Subbotovskaya, “Realization of linear functions by formulas using $\{\,\vee,^-\}$”, Sov. Math., Dokl., 2 (1961), 110–112 | MR | Zbl

[10] B. A. Subbotovskaya, “Comparison of bases in the realization by formulas of functions of the algebra of logic”, Sov. Math., Dokl., 149:4 (1963), 478–481 | MR | Zbl

[11] Eh. I. Nechiporuk, “A Boolean function”, Sov. Math., Dokl., 7 (1966), 999–1000 | MR | Zbl

[12] A. E. Andreev, “A method for obtaining efficient lower estimates of complexity of $\pi$-schemes”, Mosc. Univ. Math. Bull., 42:1 (1987), 63–66 | MR | Zbl | Zbl

[13] A. A. Razborov, “Lower bounds for the monotone complexity of some Boolean functions”, Sov. Math., Dokl., 31 (1985), 354–357 | MR | Zbl

[14] A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493 | DOI | MR | Zbl

[15] A. E. Andreev, “On a method for obtaining lower bounds for the complexity of individual monotone functions”, Sov. Math., Dokl., 31 (1985), 530–534 | MR | Zbl

[16] A. E. Andreev, “A method for obtaining efficient lower bounds for monotone complexity”, Algebra Logic, 26:1 (1987), 1–18 | DOI | MR | Zbl

[17] O. B. Lupanov, “On the realization of functions of logical algebra by formulae of finite classes (formulae of limited depth) in the basis $\{\,\vee,^-\}$”, Probl. Cybernetics, 1965, no. 6, 1–14 | Zbl

[18] V. V. Glagolev, “Estimate of the complexity of a reduced disjunctive normal form for almost all functions of the algebra of logic”, Sov. Math., Dokl., 5 (1965), 1302–1305 | MR | MR | Zbl

[19] S. E. Kuznetsov, “O nizhnei otsenke dliny kratchaishei d.n.f. pochti vsekh bulevykh funktsii”, Veroyatnostnye metody i kibernetika, no. 19, Izd-vo Kazanskogo un-ta, Kazan, 1983, 44–47 | MR | Zbl

[20] V. V. Glagolev, “Verkhnyaya otsenka slozhnosti minimalnoi d.n.f. dlya pochti vsekh funktsii algebry logiki”, Diskretnyi analiz: Cb. nauch. tr., no. 5, In-t matematiki SO AN SSSR, Novosibirsk, 1965, 3–8 | MR | Zbl

[21] A. D. Korshunov, “An upper bound of the complexity of the shortest disjunctive normal forms for almost all Boolean functions”, Cybernetics, 5 (1969), 705–715 | DOI | MR | Zbl

[22] A. A. Sapozhenko, “O slozhnosti diz'yunktivnykh normalnykh form, poluchennykh s pomoschyu gradientnogo algoritma”, Diskretnyi analiz: Cb. nauch. tr., no. 21, In-t matematiki SO AN SSSR, Novosibirsk, 1972, 62–71 | MR | Zbl

[23] A. D. Korshunov, “On the complexity of the shortest disjunctive normal forms of Boolean functions”, Amer. Math. Soc. Transl., 135 (1987), 55–79 | MR | Zbl | Zbl

[24] A. D. Korshunov, “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form sluchainykh bulevykh funktsii”, Metody diskretnogo analiza v optimizatsii upravlyayuschikh sistem: Cb. nauch. tr., no. 40, In-t matematiki SO AN SSSR, Novosibirsk, 1983, 25–53 | MR | Zbl

[25] A. E. Andreev, “On the synthesis of disjunctive normal forms which are close to minimal”, Sov. Math., Dokl., 27:2 (1983), 265–269 | MR | Zbl

[26] R. G. Nigmatullin, “Variatsionnyi printsip v algebre logiki”, Diskretnyi analiz: Cb. nauch. tr., no. 10, In-t matematiki SO AN SSSR, Novosibirsk, 1967, 69–89 | MR | Zbl

[27] S. S. Kislitsyn, A. A. Sapozhenko, “O predstavlenii mnozhestva chisel teoretiko-mnozhestvennoi summoi arifmeticheskikh progressii”, Voprosy kibernetiki, no. 16, Nauchnyi sovet AN SSSR po kompleksnoi probleme “Kibernetika”, M., 1975, 53–62

[28] S. V. Novikov, S. V. Oleksin, “O pokrytii mnozhestva arifmeticheskimi progressiyami”, Izv. AN BSSR. Ser. fiz.-matem. nauk, 1979, no. 6, 25–27 | MR | Zbl

[29] V. V. Glagolev, “O pokrytii arifmeticheskimi progressiyami”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem: Cb. nauch. tr., no. 32, In-t matematiki SO AN SSSR, Novosibirsk, 1978, 34–39 | MR | Zbl

[30] A. D. Korshunov, “Complexity of coverings of number sets by arithmetical progressions”, Discrete analysis and operations research, Math. Appl., 355, Kluwer, Dordrecht, 1996, 81–100 | MR | MR | Zbl

[31] E. A. Kostochka, “O prokalyvanii granei edinichnogo $n$-mernogo kuba”, Diskretnyi analiz: Cb. nauch. tr., no. 28, In-t matematiki SO AN SSSR, Novosibirsk, 1976, 55–64 | Zbl

[32] E. I. Nechiporuk, “Complexity of gating circuits which are realized by Boolean matrices with undetermined elements”, Sov. Phys., Dokl., 10 (1966), 591–593 | Zbl

[33] E. I. Nechiporuk, “O topologicheskikh printsipakh samokorrektirovaniya”, Problemy kibernetiki, no. 21, Nauka, M., 1969, 5–102 | MR | Zbl

[34] V. K. Leont'ev, “An upper bound for the $\alpha$-height of (0,1)-matrices”, Math. Notes, 15:3 (1974), 245–250 | DOI | MR | Zbl | Zbl

[35] W. H. Kautz, “Unit distance error checking codes”, IRE Trans. Electron. Comput., 7 (1958), 177–180 | DOI

[36] Yu. I. Zhuravlev, “Mengentheoretische Methoden in der Aussagenlogik”, Probl. Kybernetik, 8 (1965), 3–51 | Zbl

[37] Yu. L. Vasil'ev, “On the length of a cycle in an $n$-dimensional unit cube”, Sov. Math., Dokl., 4 (1963), 160–163 | MR | Zbl

[38] A. A. Evdokimov, “Maximal length of circuit in a unitary $n$-dimensional cube”, Math. Notes, 6:3 (1970), 642–648 | DOI | MR | Zbl

[39] A. A. Evdokimov, O maksimalnoi dline tsepi v $n$-mernom edinichnom kube i nekotorykh rodstvennykh zadachakh, Dis. $\dots$ kand. fiz.-matem. nauk, In-t matematiki SO AN SSSR, Novosibirsk, 1971

[40] H. L. Abbott, M. Katchalski, “On the construction of snake in the box codes”, Utilitas Math., 40 (1991), 97–116 | MR | Zbl

[41] V. V. Glagolev, “Verkhnyaya otsenka dliny tsikla v $n$-mernom edinichnom kube”, Diskretnyi analiz: Cb. nauch. tr., no. 6, In-t matematiki SO AN SSSR, Novosibirsk, 1966, 3–7 | MR | Zbl

[42] G. Zémor, “An upper bound on the size of the snake-in-the-box”, Combinatorica, 17:2 (1997), 287–298 | DOI | MR | Zbl

[43] E. N. Gilbert, “Gray codes and paths on the $n$-cube”, Bell System Tech. J., 37:3 (1958), 815–826 | MR

[44] H. L. Abbott, “Hamiltonian circuits and paths on the $n$-cube”, Canad. Math. Bull., 9:5 (1966), 557–562 | MR | Zbl

[45] E. Dixon, S. Goodman, “On the number of Hamiltonian circuits in the $n$-cube”, Proc. Amer. Math. Soc., 50 (1975), 500–504 | DOI | MR | Zbl

[46] R. J. Douglas, “A note on a theorem of H. L. Abbott”, Canad. Math. Bull., 13:1 (1970), 79–81 | MR | Zbl

[47] A. L. Perezhogin, V. N. Potapov, “O chisle gamiltonovykh tsiklov v bulevom kube”, Diskret. analiz i issled. oper. Ser. 1, 8:2 (2001), 52–62 | MR | Zbl

[48] T. Feder, C. Subi, “Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations”, Inform. Process. Lett., 109:5 (2009), 267–272 | DOI | MR

[49] A. A. Evdokimov, A. L. Perezhogin, “Minimal enumerations of subsets of a finite set and the middle level problem”, Discrete Appl. Math., 114:1–3 (2001), 109–114 | DOI | MR | MR | Zbl

[50] C. D. Savage, P. Winkler, “Monotone Gray codes and the middle levels problem”, J. Combin. Theory Ser. A, 70:2 (1995), 230–248 | DOI | MR | Zbl

[51] I. Shields, C. D. Savage, “A Hamilton path heuristic with applications to the middle two levels problem”, Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), Congr. Numer., 140, 1999, 161–178 | MR | Zbl

[52] R. W. Hamming, “Error detecting and error correcting codes”, Bell System Tech. J., 29:2 (1950), 147–160 ; R. Khemming, “Kody s obnaruzheniem i ispravleniem oshibok”, Kody s obnaruzheniem i ispravleniem oshibok, IL, M., 1956, 7–22 | MR

[53] Yu. L. Vasilev, “O negruppovykh plotno upakovannykh kodakh”, Problemy kibernetiki, no. 8, Fizmatlit, M., 1962, 337–339 | MR | Zbl

[54] D. S. Krotov, “Nizhnie otsenki chisla $m$-kvazigrupp poryadka 4 i chisla sovershennykh dvoichnykh kodov”, Diskret. analiz i issled. oper. Ser. 1, 7:2 (2000), 47–53 | MR | Zbl

[55] D. S. Krotov, S. V. Avgustinovich, “On the number of $1$-perfect binary codes: a lower bound”, IEEE Trans. Inform. Theory, 54:4 (2008), 1760–1765 | DOI | MR

[56] S. A. Malyugin, “O nizhnei otsenke chisla sovershennykh dvoichnykh kodov”, Diskret. analiz i issled. oper. Ser. 1, 6:4 (1999), 44–48 | MR | Zbl

[57] S. V. Avgustinovich, “On a property of perfect binary codes”, Operations research and discrete analysis, Math. Appl., 391, Kluwer, Dordrecht, 1997, 13–15 | MR | Zbl | Zbl

[58] Yu. A. Zuev, “Porogovye funktsii i porogovye predstavleniya bulevykh funktsii”, Matematicheskie voprosy kibernetiki, no. 5, Fizmatlit, M., 1994, 5–61 | MR | Zbl

[59] E. Goto, H. Takahasi, “Some theorems useful in threshold logic for enumerating Boolean functions”, Information Processing, Proceedings of IFIP Congress (Munich, 1962), North-Holland, Amsterdam, 1963, 747–752 | Zbl

[60] E. I. Nechiporuk, “O sinteze skhem iz porogovykh elementov”, Problemy kibernetiki, no. 11, Fizmatgiz, M., 1964, 49–62 | MR | Zbl

[61] S. Yajima, T. Ibaraki, “A lower bound of the number of threshold functions”, IEEE Trans. Electron. Comput., EC-14:6 (1965), 926–929 ; S. Yadzhima, E. Ibaraki, “Nizhnyaya otsenka chisla porogovykh funktsii”, Kibernet. sb. Nov. ser., 1969, no. 6, 72–81 | DOI | Zbl

[62] Yu. A. Zuev, “Asymptotics of the logarithm of the number of threshold functions of the algebra of logic”, Sov. Math., Dokl., 39:3 (1989), 512–513 | MR | Zbl

[63] Yu. A. Zuev, “Methods of geometry and probabilistic combinatorics in threshold logic”, Discrete Math. Appl., 2:4 (1992), 427–438 | DOI | MR | Zbl | Zbl

[64] A. A. Irmatov, “On the number of threshold functions”, Discrete Math. Appl., 3:4 (1993), 429–432 | MR | Zbl

[65] M. Hall, Jr., Combinatorial theory, Blaisdell, Waltham–Toronto–London, 1967 | MR | MR | Zbl | Zbl

[66] J. Doyen, G. Valette, “On the number of non isomorphic Steiner triple systems”, Math. Z., 120:2 (1971), 178–192 | DOI | MR | Zbl

[67] G. P. Egorychev, “The solution of van der Waerden's problem for permanents”, Adv. Math., 42:3 (1981), 299–305 | DOI | MR | MR | Zbl | Zbl

[68] J. A. Bondy, “A graph reconstructor's manual”, Surveys in combinatorics, Proceedings of the 13th British Combinatorics Conference (Guildford, 1991), London Math. Soc. Lecture Note Ser., 166, Cambridge Univ. Press, Cambridge, 1991, 221–252 | MR | Zbl

[69] M. Bilinski, Y. S. Kwon, X. Yu, “On reconstruction of planar graphs”, J. Combin. Theory. Ser. B, 97:5 (2007), 745–756 | DOI | MR | Zbl

[70] S. Fiorini, J. Lauri, “The reconstruction of maximal planar graphs. I: Recognition”, J. Combin. Theory Ser. B, 30:2 (1981), 188–195 | DOI | MR | Zbl

[71] W. B. Giles, “The reconstruction of outerplanar graphs”, J. Combin. Theory Ser. B, 16:3 (1974), 215–226 | DOI | MR | Zbl

[72] P. J. Kelly, “A congruence theorem for trees”, Pacific J. Math., 7:1 (1957), 961–968 | MR | Zbl

[73] J. Lauri, “The reconstruction of maximal planar graphs, II: Reconstruction”, J. Combin. Theory Ser. B, 30:2 (1981), 196–214 | DOI | MR | Zbl

[74] S. M. Ulam, A collection of mathematical problems, Interscience Tracts Pure Appl. Math., 8, Wiley, New York, 1960 ; 2nd ed.: Problems in modern mathematics, Wiley, New York, 1964 ; S. Ulam, Nereshennye matematicheskie zadachi, Sovremennye problemy matematiki, Nauka, M., 1964 | MR | Zbl | MR | Zbl | Zbl