Laboratory of Theoretical Computer Science seminar resumed its work

In January, the laboratory of theoretical computer science planned to hold two seminars. Ivan Arzhantsev spoke at the first seminar. At the second seminar, our colleague from Nizhny Novgorod, Dmitry Sirotkin, spoke about his results.

At the seminar on January 16, Ivan Arzhantsev discussed with the participants of the seminar the construction of "ideal numbers", reducing ambiguous expansions to unambiguous, which allowed Kummer in 1850 to prove Fermat's great theorem for all regular primes. Kummer's idea leads to an elementary and essentially combinatorial definition of the theory of divisors for a semigroup.The participants discussed this definition and illustrated it with examples from different areas of mathematics, defined a group of semigroup divisor classes, considered a zero-sum sequence semigroup, and learned about an overview of the well-known results and open problems in this area.

On January 30, Dmitry Sirotkin examined some local graph transformations focused on data reduction in the problems of an independent set and a vertex 3-coloring. With the help of these transformations, as well as new techniques of algorithmic graph theory, the computational status of the actual subtasks of these tasks is established. Namely, the computational status of the independent set problem is established for some subclasses of the class of planar graphs, as well as the vertex 3-coloring problem in some subsets of the set of planar graphs and in some hereditary classes defined by forbidden generated small structures.