### Article

## The Diameter of Chess Grows Exponentially

We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves.

We prove existence and uniqueness of a solution to the problem of minimizing the logarithmic energy of vector potentials associated to a d-tuple of positive measures supported on closed subsets of the complex plane. The assumptions we make on the interaction matrix are weaker than the usual ones, and we also let the masses of the measures vary in a compact subset of ℝ+ d. The solution is characterized in terms of variational inequalities. Finally, we review a few examples taken from the recent literature that are related to our results.

Currently, the tasks of ensuring the quality and stability of the provided IT services are extremely topical. In the operation of the composite applications, the problem of increasing the effectiveness of incident management is a complex technical problem, the solution of which requires the use of the simulation methods. In the work, the integration platform Ensemble of InterSystems Company was considered as a basis for designing integration solutions. Given the architectural features of the integration platforms, a mathematical model of the incident management process in the Ensemble integration platform is proposed. This mathematical model was used to develop algorithms for identifying and classifying incidents. The results of the work can be used in the design and development of incident management information systems, as well as in organizing the work of technical support services for IT companies

This paper aims to tackle the problem of brain network classification with machine learning algorithms using spectra of networks’ matrices. Two approaches are discussed: first, linear and tree-based models are trained on the vectors of sorted eigenvalues of the adjacency matrix, the Laplacian matrix and the normalized Laplacian; next, SVM classifier is trained with kernels based on information divergence between the eigenvalue distributions. The latter approach gives promising results in the classification of autism spectrum disorder versus typical development and of the carriers versus noncarriers of an allele associated with the high risk of Alzheimer disease.

We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.

Proceedings include extended abstracts of reports presented at the III International Conference on Optimization Methods and Applications “Optimization and application” (OPTIMA-2012) held in Costa da Caparica, Portugal, September 23—30, 2012.

A “Network Analysis” section was arranged at the XVIIIth Interna- tional Academic Conference on Economic and Social Development at the Higher School of Economics on 11–12 April 2017. For the third year, this section invited scholars from sociology, political science, management, mathematics, and linguistics who use network analysis in their research projects. During the sessions, speakers discussed the development of mathematical models used in network analysis, studies of collaboration and communication networks, networks’ in- uence on individual attributes, identifcation of latent relationships and regularities, and application of network analysis for the study of concept networks.

The speakers in this section were E. V. Artyukhova (HSE), G. V. Gra- doselskaya (HSE), M. Е. Erofeeva (HSE), D. G. Zaitsev (HSE), S. A. Isaev (Adidas), V. A. Kalyagin (HSE), I. A. Karpov (HSE), A. P. Koldanov (HSE), I. I. Kuznetsov (HSE), S. V. Makrushin (Fi- nancial University), V. D. Matveenko (HSE), A. A. Milekhina (HSE), S. P. Moiseev (HSE), Y. V. Priestley (HSE), A. V. Semenov (HSE), I. B. Smirnov (HSE), D. A. Kharkina (HSE, St. Petersburg), C. F. Fey (Aalto University School of Business), and F. López-Iturriaga (Uni- versity of Valladolid).

The collection represents proceedings of the nineth international conference "Discrete Models in Control Systems Theory" that is held by Lomonosov Moscow State Uneversity and is dedicated in 90th anniversary of Sergey Vsevolodovich Yablonsky's birth. The conference subject are includes: discrete functional systems; discrete functions properties; control systems synthesis, complexity, reliability, and diagnostics; automata; graph theory; combinatorics; coding theory; mathematical methods of information security; theory of pattern recognition; mathematical theory of intellegence systems; applied mathematical logic. The conference is sponsored by Russian Foundation for Basic Research (project N 15-01-20193-г).

Let *G* be a simple graph whose vertices are partitioned into two subsets, called ‘filled’ vertices and ‘empty’ vertices. A vertex *v* is said to be forced by a filled vertex *u* if *v* is a unique empty neighbor of *u*. If we can fill all the vertices of *G* by repeatedly filling the forced ones, then we call an initial set of filled vertices a forcing set. We discuss the so-called failed forcing number of a graph, which is the largest cardinality of a set which is not forcing. Answering the recent question of Ansill, Jacob, Penzellna, Saavedra, we prove that this quantity is NP-hard to compute. Our proof also works for a related graph invariant which is called the skew failed forcing number.

We study dierences in structural connectomes between typically developing and autism spectrum disorders individuals with machine learning techniques using connection weights and network metrics as features. We build linear SVM classier with accuracy score 0:64 and report 16 features (seven connection weights and nine network node centralities) best distinguishing these two groups.

A model for organizing cargo transportation between two node stations connected by a railway line which contains a certain number of intermediate stations is considered. The movement of cargo is in one direction. Such a situation may occur, for example, if one of the node stations is located in a region which produce raw material for manufacturing industry located in another region, and there is another node station. The organization of freight traﬃc is performed by means of a number of technologies. These technologies determine the rules for taking on cargo at the initial node station, the rules of interaction between neighboring stations, as well as the rule of distribution of cargo to the ﬁnal node stations. The process of cargo transportation is followed by the set rule of control. For such a model, one must determine possible modes of cargo transportation and describe their properties. This model is described by a ﬁnite-dimensional system of diﬀerential equations with nonlocal linear restrictions. The class of the solution satisfying nonlocal linear restrictions is extremely narrow. It results in the need for the “correct” extension of solutions of a system of diﬀerential equations to a class of quasi-solutions having the distinctive feature of gaps in a countable number of points. It was possible numerically using the Runge–Kutta method of the fourth order to build these quasi-solutions and determine their rate of growth. Let us note that in the technical plan the main complexity consisted in obtaining quasi-solutions satisfying the nonlocal linear restrictions. Furthermore, we investigated the dependence of quasi-solutions and, in particular, sizes of gaps (jumps) of solutions on a number of parameters of the model characterizing a rule of control, technologies for transportation of cargo and intensity of giving of cargo on a node station.

Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.