Geodesic
Some unsolved problems in discrete mathematics and mathematical cybernetics
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 64 (2009) no. 5, pp. 787-803

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

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.
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 
@article{RM_2009_64_5_a0,
     author = {A. D. Korshunov},
     title = {Some unsolved problems in discrete mathematics and mathematical cybernetics},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {787--803},
     publisher = {mathdoc},
     volume = {64},
     number = {5},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2009_64_5_a0/}
}
TY  - JOUR
AU  - A. D. Korshunov
TI  - Some unsolved problems in discrete mathematics and mathematical cybernetics
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2009
SP  - 787
EP  - 803
VL  - 64
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/RM_2009_64_5_a0/
LA  - en
ID  - RM_2009_64_5_a0
ER  - 
%0 Journal Article
%A A. D. Korshunov
%T Some unsolved problems in discrete mathematics and mathematical cybernetics
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2009
%P 787-803
%V 64
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/RM_2009_64_5_a0/
%G en
%F RM_2009_64_5_a0
A. D. Korshunov. Some unsolved problems in discrete mathematics and mathematical cybernetics. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 64 (2009) no. 5, pp. 787-803. http://geodesic.mathdoc.fr/item/RM_2009_64_5_a0/