Modal logics, both propositional and predicate, have been used in computer science since the late 1970s. One of the most important properties of modal logics of relevance to their applications in computer science is the complexity of their satisfiability problem. The complexity of satisfiability for modal logics is rather high: it ranges from NP-complete to undecidable for propositional logics and is undecidable for predicate logics. This has, for a long time, motivated research in drawing the borderline between tractable and intractable fragments of propositional modal logics as well as between decidable and undecidable fragments of predicate modal logics. In the present thesis, we investigate some very natural restrictions on the languages of propositional and predicate modal logics and show that placing those restrictions does not decrease complexity of satisfiability. For propositional languages, we consider restricting the number of propositional variables allowed in the construction of formulas, while for predicate languages, we consider restricting the number of individual variables as well as the number and arity of predicate letters allowed in the construction of formulas. We develop original techniques, which build on and develop the techniques known from the literature, for proving that satisfiability for a finite-variable fragment of a propositional modal logic is as computationally hard as satisfiability for the logic in the full language and adapt those techniques to predicate modal logics and prove undecidability of fragments of such logics in the language with a finite number of unary predicate letters as well as restrictions on the number of individual variables. The thesis is based on four articles published or accepted for publication. They concern propositional dynamic logics, propositional branchingand alternating-time temporal logics, propositional logics of symmetric rela tions, and first-order predicate modal and intuitionistic logics. In all cases, we identify the “minimal,” with regard to the criteria mentioned above, fragments whose satisfiability is as computationally hard as satisfiability for the entire logic.

This book deals with mathematical modeling, namely, it describes the mathematical model of heat transfer in a silicon cathode of small (nano) dimensions with the possibility of partial melting taken into account.  This mathematical model is based on the phase field system, i.e., on a contemporary generalization of Stefan-type free boundary problems. The approach used is not purely mathematical but is based on the understanding of the solution structure (construction and study of asymptotic solutions) and computer calculations. The book presents an algorithm for numerical solution of the equations of the mathematical model including its parallel implementation. The results of numerical simulation concludes the book. The book is intended for specialists in the field of heat transfer and field emission processes and can be useful for senior students and postgraduates.​

This paper provides a comprehensive overview of the gapping dataset for Russian that consists of 7.5k sentences with gapping (as well as 15k relevant negative sentences) and comprises data from various genres: news, fiction, social media and technical texts. The dataset was prepared for the Automatic Gapping Resolution Shared Task for Russian (AGRR-2019) - a competition aimed at stimulating the development of NLP tools and methods for processing of ellipsis. In this paper, we pay special attention to the gapping resolution methods that were introduced within the shared task as well as an alternative test set that illustrates that our corpus is a diverse and representative subset of Russian language gapping sufficient for effective utilization of machine learning techniques.

This book concentrates on in-depth explanation of a few methods to address core issues, rather than presentation of  a multitude of methods that are popular among the scientists. An added value of this edition is that I am trying to address two features of the brave new world that materialized after the first edition was written in 2010. These features are the emergence of “Data science” and changes in student cognitive skills in the process of global digitalization.  The birth of Data science gives me more opportunities in delineating the field of data analysis. An overwhelming majority of both theoreticians and practition-ers are inclined to consider the notions of ‘data analysis” (DA) and “machine learning” (ML) as synonymous. There are, however, at least two differences between the two. First comes the difference in perspectives. ML is to equip computers with methods and rules to see through regularities of the environment - and behave accordingly. DA is to enhance conceptual understanding. These goals are not inconsistent indeed, which explains a huge overlap between DA and ML. However, there are situations in which these perspectives are not consistent.  Regarding the current students’ cognitive habits, I came to the conclusion that they prefer to immediately get into the “thick of it”.  Therefore, I streamlined the presentation of multidimensional methods. These methods are now organized in four Chapters, one of which presents correlation learning (Chapter 3). Three other Chapters present summarization methods both quantitative (Chapter 2) and categorical (Chapters 4 and 5). Chapter 4 relates to finding and characterizing partitions by using K-means clustering and its extensions. Chapter 5 relates to hierarchical and separative cluster structures. Using encoder-decoder data recovery approach brings forth a number of mathematically proven interrelations between methods that are used for addressing such practical issues as the analysis of mixed scale data, data standardization, the number of clusters, cluster interpretation, etc. An obvious bias towards summarization against correlation can be explained, first, by the fact that most texts in the field are biased in the opposite direction, and, second, by my personal preferences. Categorical summarization, that is, clustering is considered not just a method of DA but rather a model of classification as a concept in knowledge engineering. Also, in this edition, I somewhat relaxed the “presentation/formulation/computation” narrative struc-ture, which was omnipresent in the first edition, to be able do things in one go. Chapter 1 presents the author’s view on the DA mainstream, or core, as well as on a few Data science issues in general. Specifically, I bring forward novel material on the role of DA, including its successes and pitfalls (Section 1.4), and classification as a special form of knowledge (Section 1.5). Overall, my goal is to show the reader that Data science is not a well-formed part of knowledge yet but rather a piece of science-in-the-making.  

The materials of The International Scientific – Practical Conference is presented below. The Conference reflects the modern state of innovation in education, science, industry and social-economic sphere, from the standpoint of introducing new information technologies. It is interesting for a wide range of researchers, teachers, graduate students and professionals in the field of innovation and information technologies.

This book brings together reviews by internationally renowed experts on quantum optics and photonics. It describes novel experiments at the limit of single photons, and presents advances in this emerging research area. It also includes reprints and historical descriptions of some of the first pioneering experiments at a single-photon level and nonlinear optics, performed before the inception of lasers and modern light detectors, often with the human eye serving as a single-photon detector. The book comprises 19 chapters, 10 of which describe modern quantum photonics results, including single-photon sources,  direct measurement of the photon's spatial wave function, nonlinear interactions and non-classical light, nanophotonics for room-temperature single-photon sources, time-multiplexed methods for optical quantum information processing, the role of photon statistics in visual perception, light-by-light coherent control using metamaterials, nonlinear nanoplasmonics, nonlinear polarization optics, and ultrafast nonlinear optics in the mid-infrared.

This volume collects the referred papers based on plenary, invited, and oral talks, as well on the posters presented at the Third International Conference on Computer Simulations in Physics and beyond (CSP2018), which took place September 24-27, 2018 in Moscow. The Conference continues the tradition started by an inaugural conference in 2015. It took place on the campus of A.N. Tikhonov Moscow Institute of Electronics and Mathematics in Strogino, was jointly organized by the National Research University Higher School of Economics, the Landau Institute for Theoretical Physics and Science Center in Chernogolovka.

The Conference is a multidisciplinary meeting, with a focus on computational physics and related subjects. Indeed, methods of computational physics prove useful in a broad spectrum of research in multiple branches of natural sciences, and this volume provides a sample.

We hope that this volume will interest readers, and we are already looking forward to the next conference in the series.

Moscow, Russia

November, 2018

CSP2018 Conference Chair and Volume Editor

Lev Shchur

2019 International Siberian Conference on Control and Communications (SIBCON). Proceedings

This book constitutes the refereed proceedings of the 9th International Conference on Optimization and Applications, OPTIMA 2018, held in Petrovac, Montenegro, in October 2018.The 35 revised full papers and the one short paper presented were carefully reviewed and selected from 103 submissions. The papers are organized in topical sections on mathematical programming; combinatorial and discrete optimization; optimal control; optimization in economy, finance and social sciences; applications.

This book covers the classical theory of Markov chains on general state-spaces as well as many recent developments. The theoretical results are illustrated by simple examples, many of which are taken from Markov Chain Monte Carlo methods. The book is self-contained, while all the results are carefully and concisely proven. Bibliographical notes are added at the end of each chapter to provide an overview of the literature.

Proceedings of Third Workshop "Computational linguistics and language science"

Sustaining a competitive edge in today’s business world requires innovative approaches to product, service, and management systems design and performance. Advances in computing technologies have presented managers with additional challenges as well as further opportunities to enhance their business models.

Software Engineering for Enterprise System Agility: Emerging Research and Opportunities is a collection of innovative research that identifies the critical technological and management factors in ensuring the agility of business systems and investigates process improvement and optimization through software development. Featuring coverage on a broad range of topics such as business architecture, cloud computing, and agility patterns, this publication is ideally designed for business managers, business professionals, software developers, academicians, researchers, and upper-level students interested in current research on strategies for improving the flexibility and agility of businesses and their systems.

Computer simulations are nowadays a rmly established third pillar of modern natural sciences, complementing experimentation and paper-and-pencil theoret- ical studies. Simulations, experiments in silico, prove indispensable in diverse areas of research in physics and other natural sciences. This volume collects papers based on presentations delivered at the Sec- ond International Conference on Computer Simulations in Physics and beyond (CSP2017), which took place October 9-12, 2017 in Moscow. The Conference, which continues a biannual tradition started by an innaugural conference in 2015, took place on campus of A.N. Tikhonov Moscow Institute of Electronics and Mathematics, was jointly organized by the National Research University Higher School of Economics, the Landau Insitute for Theoretical Physics and Science Center in Chernogolovka. As the name implies, the Conference is a multidisciplinary meeting, with a focus on computational physics and related subjects. Indeed, methods of computational physics prove useful in a broad spectrum of research in multiple branches of natural sciences, and this volume provides a sample. We hope that this volume will interest a wide range of readers, and we are already looking forward for the next conference in this biannual series.

The 29th DAAAM International Symposium on Intelligent Manufacturing and Automation took place in Zadar, Croatia between the 24th and 27th October 2018, during the DAAAM International Week. The Symposium was organized by DAAAM International Vienna in cooperation with ÖIAV 1848, Vienna University of Technology, International Academy of Engineering and University of Applied Sciences – Technikum Wien and Under the Auspices of the Danube Rectors’ Conference & Rectors’ and Presidents’ Honor Committee of DAAAM International for 2018. The Symposium took place in Zadar, Croatia. This year’s symposium aimed at continuing the success of the previous years, focusing on the five-fold traditional objectives of the symposium: the presentation of the most recent high-quality results, support of development of young scientists and researchers, organization of international (summer) doctoral school, inauguration of new members of Central European Branch of International Academy of Engineering and the provision of the necessary setting for stimulating discussions, brainstorming and networking among European and international researchers coming both from the academia government agencies and industry.

This book offers a concise yet thorough introduction to the notion of moduli spaces of complex algebraic curves. Over the last few decades, this notion has become central not only in algebraic geometry, but in mathematical physics, including string theory, as well.

The book begins by studying individual smooth algebraic curves, including the most beautiful ones, before addressing families of curves. Studying families of algebraic curves often proves to be more efficient than studying individual curves: these families and their total spaces can still be smooth, even if there are singular curves among their members. A major discovery of the 20th century, attributed to P. Deligne and D. Mumford, was that curves with only mild singularities form smooth compact moduli spaces. An unexpected byproduct of this discovery was the realization that the analysis of more complex curve singularities is not a necessary step in understanding the geometry of the moduli spaces.

The book does not use the sophisticated machinery of modern algebraic geometry, and most classical objects related to curves – such as Jacobian, space of holomorphic differentials, the Riemann-Roch theorem, and Weierstrass points – are treated at a basic level that does not require a profound command of algebraic geometry, but which is sufficient for extending them to vector bundles and other geometric objects associated to moduli spaces. Nevertheless, it offers clear information on the construction of the moduli spaces, and provides readers with tools for practical operations with this notion.

Based on several lecture courses given by the authors at the Independent University of Moscow and Higher School of Economics, the book also includes a wealth of problems, making it suitable not only for individual research, but also as a textbook for undergraduate and graduate coursework.

The IEEE Russia North West Section, Saint Petersburg Electrotechnical University “LETI”, and the European Centre for Quality (Moscow) are pleased to present the Proceedings of the 2018 IEEE International Conference "Quality Management, Transport and Information Security, Information Technologies" (IT&QM&IS). The Conference was held in St. Petersburg, Russia on September 24–29, 2018, and it was proudly hosted by Saint Petersburg Electrotechnical University “LETI”. The Organizing Committee believes and trusts that we have been true to the spirit of collegiality that members of IEEE value whilst also maintaining a high standard as we reviewed papers, provided feedback and now present a strong body of published work in this collection of proceedings. The themes for this year's conference were chosen as a means of bringing together academics and industrialists, engineering and management research, manufacturing and teaching, and providing a basis for discussion of issues arising across the engineering and business community in relation to Quality Management, Information Technologies, Transport and Information Security aimed at developing engineers and managers for the future. The goal of these proceedings has been to present high quality work in an accessible medium, for use in a wide community of academics, engineers, managers, and industrialists, the community united by the key words Science, Education, Quality, Innovations in engineering. To achieve this aim, all abstracts were blind reviewed, and full papers submitted for publication in this journal of proceedings were subjected to a rigorous reviewing process.

This volume, dedicated to the memory of the great American mathematician Bertram Kostant (May 24, 1928 – February 2, 2017), is a collection of 19 invited papers by leading mathematicians working in Lie theory, representation theory, algebra, geometry, and mathematical physics. Kostant’s fundamental work in all of these areas has provided deep new insights and connections, and has created new fields of research. This volume features the only published articles of important recent results of the contributors with full details of their proofs. Key topics include: Poisson structures and potentials (A. Alekseev, A. Berenstein, B. Hoffman) Vertex algebras (T. Arakawa, K. Kawasetsu) Modular irreducible representations of semisimple Lie algebras (R. Bezrukavnikov, I. Losev) Asymptotic Hecke algebras (A. Braverman, D. Kazhdan) Tensor categories and quantum groups (A. Davydov, P. Etingof, D. Nikshych) Nil- Hecke algebras and Whittaker D-modules (V. Ginzburg) Toeplitz operators (V. Guillemin, A. Uribe, Z. Wang) Kashiwara crystals (A. Joseph) Characters of highest weight modules (V. Kac, M. Wakimoto) Alcove polytopes (T. Lam, A. Postnikov) Representation theory of quantized Gieseker varieties (I. Losev) Generalized Bruhat cells and integrable systems (J.-H. Liu, Y. Mi) Almost characters (G. Lusztig) Verlinde formulas (E. Meinrenken) Dirac operator and equivariant index (P.-É. Paradan, M. Vergne) Modality of representations and geometry of-groups (V. L. Popov) Distributions on homogeneous spaces (N. Ressayre) Reduction of orthogonal representations (J.- P. Serre).

The nonlinear stage of the modulational (Benjamin–Feir) instability of unidirectional deep-water surface gravity waves is simulated numerically by the fifth-order nonlinear envelope equations. The conditions of steep and breaking waves are concerned. The results are compared with the solution of the full potential Euler equations and with the lower-order envelope models (the 3-order nonlinear Schrödinger equation and the standard 4-order Dysthe equations). The generalized Dysthe model is shown to exhibit the tendency to re-stabilization of steep waves with respect to long perturbations.

The issue of accounting of the wave breaking phenomenon in direct numerical simulations of oceanic waves is discussed. It is emphasized that this problem is crucial for the deterministic description of waves, and also for the dynamical calculation of extreme wave statistical characteristics, such as rogue wave height probability, asymmetry, etc. The conditions for accurate simulations of irregular steep waves within the High Order Spectral Method for the potential Euler equations are identified. Such non-dissipative simulations are considered as the reference when comparing with the simulations of occasionally breaking waves which use two kinds of wave breaking regularization. It is shown that the perturbations caused by the wave breaking attenuation may be noticeable within 20 min of the performed simulation of the wave evolution

We consider two nested billiards in ℝd, d≥3, with C2-smooth strictly convex boundaries. We prove that if the corresponding actions by reflections on the space of oriented lines commute, then the billiards are confocal ellipsoids. This together with the previous analogous result of the author in two dimensions solves completely the Commuting Billiard Conjecture due to Sergei Tabachnikov. The main result is deduced from the classical theorem due to Marcel Berger saying that in higher dimensions only quadrics may have caustics. We also prove versions of Berger's theorem and the main result for billiards in spaces of constant curvature: space forms.

We present a solution of the algebraic version of Birkhoff Conjecture on integrable billiards. Namely we show that every polynomially integrable real bounded convex planar billiard with smooth boundary is an ellipse. We extend this result to billiards with piecewise-smooth and not necessarily convex boundary on arbitrary two-dimensional surface of constant curvature: plane, sphere, Lobachevsky (hyperbolic) plane; each of them being modeled as a plane or a (pseudo-) sphere in ℝ3 equipped with appropriate quadratic form. Namely, we show that a billiard is polynomially integrable, if and only if its boundary is a union of confocal conical arcs and appropriate geodesic segments. We also present a complexification of these results. These are joint results of Mikhail Bialy, Andrey Mironov and the author. The proof is split into two parts. The first part is given by Bialy and Mironov in their two joint papers. They considered the tautological projection of the boundary to ℝℙ2 and studied its orthogonal-polar dual curve, which is piecewise algebraic, by S.V.Bolotin's theorem. By their arguments and another Bolotin's theorem, it suffices to show that each non-linear complex irreducible component of the dual curve is a conic. They have proved that all its singularities and inflection points (if any) lie in the projectivized zero locus of the corresponding quadratic form on ℂ3. The present paper provides the second part of the proof: we show that each above irreducible component is a conic and finish the solution of the Algebraic Birkhoff Conjecture in constant curvature.

The reaction of di(methoxycarbonyl)tetrazine with substituted cycloprop-2-ene-1-carboxylates gives a series of 3,4-diazanorcaradienes and 1,2-diazepines. The influence of the nature of cyclopropenes and the reaction conditions on its selectivity was investigated. The addition of nucleophiles to norcaradienes was studied and a rare example of the “walk” rearrangement in this class of compounds was revealed.

7-Lithio-3-tert-butylpyrazolo[5,1-c][1,2,4]triazines have been generated for the first time using one-pot nucleophilic addition and metal-halogen exchange reactions in 7-bromopyrazolo[5,1-c][1,2,4]triazines. It was found that the stability of 7-lithio species depends highly on the substitution pattern at the C(4) ring position. The rate of the pyrazole ring opening reaction roughly followed the order of the electronegativity of substituents: rapid cycle cleavage took place already at −97 °C for C(4) = O, CH–Ar, CH–C≡CPh, while CH–Alk and CH2 substituted derivatives were stable in these conditions (Ar = Ph, 4-tolyl; Alk = t-Bu, n-Bu, n-Pr). Quantum chemical modeling showed that the ring opening is accompanied with simultaneous shift of the Li atom towards N(6). Calculated free activation energies are in range from 12.7 to 15.0 kcal*mol−1. Electrophile trapping of fairly stable 4-alkyl-1,7-metalated derivatives at −97 °C using H2O, DMF or PhCHO allowed the selective side-chain functionalization. Tautomeric exo- and endocyclic double bond equilibrium in the isolated 4-oxo and 4-aryl substituted ring opening products is also discussed on the basis of IR, 1H, 13C NMR, high resolution mass spectra and X-ray powder diffraction analysis.

Triallylborane-mediated thermal trans/cis-isomerization of α-allylated azaheterocycles is a unique stereoselective transformation providing straightforward access to important heterocycles. The main experimental features of this process, namely, thermodynamically controlled isomer ratio, 1,3-allylic strain as a driving force and regioselectivity are quantitatively described by quantum chemical calculations at B3LYP/6-31+G(d,p)/PCM(DMSO) level of theory.

In this paper, we formulate a field-theoretical model of dilute salt solutions of electrically neutral spherical colloid particles. Each colloid particle consists of a 'central' charge that is situated at the center and compensating peripheral charges (grafted to it) that are fixed or fluctuating relative to the central charge. In the framework of the random phase approximation, we obtain a general expression for electrostatic free energy of solution and analyze it for different limiting cases. In the limit of infinite number of peripheral charges, when they can be modelled as a continual charged cloud, we obtain an asymptotic behavior of the electrostatic potential of a point-like test charge in a salt colloid solution at long distances, demonstrating the crossover from its monotonic decrease to damped oscillations with a certain wavelength. We show that the obtained crossover is determined by certain Fisher-Widom line. For the same limiting case, we obtain an analytical expression for the electrostatic free energy of a salt-free solution. In the case of nonzero salt concentration, we obtain analytical relations for the electrostatic free energy in two limiting regimes. Namely, when the ionic concentration is much higher than the colloid concentration and the effective size of charge cloud is much bigger than the screening lengths that are attributed to the salt ions and the central charges of colloid particles. The proposed theory could be useful for theoretical description of the phase behavior of salt solutions of metal-organic complexes and polymeric stars.

The subject of this paper is the big quantum cohomology rings of symplectic isotropic Grassmannians IG(2,2n). We show that these rings are regular. In particular, by “generic smoothness”, we obtain a conceptual proof of generic semisimplicity of the big quantum cohomology for IG(2,2n). Further, by a general result of Hertling, the regularity of these rings implies that they have a description in terms of isolated hypersurface singularities, which we show in this case to be of type A_{n−1}. By the homological mirror symmetry conjecture, these results suggest the existence of a very special full exceptional collection in the derived category of coherent sheaves on IG(2,2n). Such a collection is constructed in the appendix by Alexander Kuznetsov.

Consider a family of Fano varieties π:X⟶B∋o over a curve germ with a smooth total space X. Assume that the generic fiber is smooth and the special fiber F=π^{−1}(o) has simple normal crossings. Then F is called a semistable degeneration of Fano varieties. We show that the dual complex of F is a simplex of dimension ≤dim F. Simplices of any admissible dimension can be realized for any dimension of the fiber. Using this result and the Minimal Model Program in dimension 3 we reproduce the classification of the semistable degenerations of del Pezzo surfaces obtained by Fujita. We also show that the maximal degeneration is unique and has trivial monodromy in dimension ≤3.

We show that over an algebraically closed field of characteristic not equal to 2, homological projective duality for smooth quadric hypersurfaces and for double covers of projective spaces branched over smooth quadric hypersurfaces is a combination of two operations: one interchanges a quadric hypersurface with its classical projective dual and the other interchanges a quadric hypersurface with the double cover branched along it.

In this paper we introduce a class of noncommutative (finitely generated) monomial algebras whose Hilbert series are algebraic functions. We use the concept of graded homology and the theory of unambiguous context-free grammars for this purpose. We also provide examples of finitely presented graded algebras whose corresponding leading monomial algebras belong to the proposed class and hence possess algebraic Hilbert series.

For a polarized variety (X,L) and a closed connected subgroup G⊂Aut(X,L) we define a G-invariant version of the δ-threshold. We prove that for a Fano variety (X,−KX) and a connected subgroup G⊂Aut(X) this invariant characterizes G-equivariant uniform K-stability. We also use this invariant to investigate G-equivariant K-stability of some Fano varieties with large groups of symmetries, including spherical Fano varieties. We also consider the case of G being a finite group.

We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.

A set of objects, some goods and some bads, is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then fair division may not exist. What is the smallest number of objects that must be shared between two or more agents in order to attain a fair division? We focus on Pareto-optimal, envy-free and/or proportional allocations. We show that, for a generic instance of the problem --- all instances except of a zero-measure set of degenerate problems --- a fair and Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time, assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where the agents' valuations are aligned for many objects.

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash Social Welfare on the Pareto frontier of the set of feasible utilities. The rule becomes multivalued and none of the standard methods can be applied to compute its outcome. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in Devanur et al (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).

We give a simple recursion labeled by binary sequences which computes rational q,t-Catalan power series, both in relatively prime and non relatively prime cases. It is inspired by, but not identical to recursions due to B. Elias, M. Hogancamp, and A. Mellit, obtained in their study of link homology. We also compare our recursion with the Hogancamp-Mellit's recursion and verify a connection between the Khovanov-Rozansky homology of N,M-torus links and the rational q,t-Catalan power series for general positive N,M.

Recent work of the first author, Negut and Rasmussen, and of Oblomkov and Rozansky in the context of Khovanov-Rozansky knot homology produces a family of polynomials in q and t labeled by integer sequences. These polynomials can be expressed as equivariant Euler characteristics of certain line bundles on flag Hilbert schemes. The q,t-Catalan numbers and their rational analogues are special cases of this construction. In this paper, we give a purely combinatorial treatment of these polynomials and show that in many cases they have nonnegative integer coefficients.  For sequences of length at most 4, we prove that these coefficients enumerate subdiagrams in a certain fixed Young diagram and give an explicit symmetric chain decomposition of the set of such diagrams. This strengthens results of Lee, Li and Loehr for (4,n) rational q,t-Catalan numbers.

We describe the universal target of annular Khovanov-Rozansky link homology functors as the homotopy category of a free symmetric monoidal category generated by one object and one endomorphism. This categorifies the ring of symmetric functions and admits categorical analogues of plethystic transformations, which we use to characterize the annular invariants of Coxeter braids. Further, we prove the existence of symmetric group actions on the Khovanov-Rozansky invariants of cabled tangles and we introduce spectral sequences that aid in computing the homologies of generalized Hopf links. Finally, we conjecture a characterization of the horizontal traces of Rouquier complexes of Coxeter braids in other types.

We prove that the full twist is a Serre functor in the homotopy category of type A Soergel bimodules. As a consequence, we relate the top and bottom Hochschild degrees in Khovanov-Rozansky homology, categorifying a theorem of Kálmán.

Admixture is increasingly being recognized as an important factor in evolutionary genetics. The distribution of genomic admixture tracts, and the resulting effects on admixture linkage disequilibrium, can be used to date the timing of admixture between species or populations. However, the theory used for such prediction assumes selective neutrality despite the fact that many famous examples of admixture involve natural selection acting for or against admixture. In this paper, we investigate the effects of positive selection on the distribution of tract lengths. We develop a theoretical framework that relies on approximating the trajectory of the selected allele using a logistic function. By numerically calculating the expected allele trajectory, we also show that the approach can be extended to cases where the logistic approximation is poor due to the effects of genetic drift. Using simulations, we show that the model is highly accurate under most scenarios. We use the model to show that positive selection on average will tend to increase the admixture tract length. However, perhaps counter-intuitively, conditional on the allele frequency at the time of sampling, positive selection will actually produce shorter expected tract lengths. We discuss the consequences of our results in interpreting the timing of the introgression of EPAS1 from Denisovans into the ancestors of Tibetans.

We characterize open embeddings of Stein spaces and of $C^\infty$-manifolds in terms of certain flatness-type conditions on the respective homomorphisms of function algebras.  

Let S={s1<s2<s3<…} be the sequence of all natural numbers which can be represented as a sum of two squares of integers. For X≥2 we denote by g(X) the largest gap between consecutive elements of S that do not exceed X. We prove that for X→+∞ the lower bound g(X)≥(390/449−o(1))lnX holds.  This estimate is twice the recent estimate by R. Dietmann and C. Elsholtz.

We study properties of Markov chain Monte Carlo simulations of classical spin models with local updates. We derive analytic expressions for the mean value of the acceptance rate of the single-spin-flip algorithms for the one-dimensional Ising model. We find that for the Metropolis algorithm the average acceptance rate is a linear function of energy. We further provide numerical results for the energy dependence of the average acceptance rate for the 3- and 4-state Potts model, and the XY model in one and two spatial dimensions. In all cases, the acceptance rate is an almost linear function of the energy in the critical region. The variance of the acceptance rate is studied as a function of the specific heat.

The convolution ring K^{GL_n(\OOO)⋊ℂ×}(Gr_{GL_n}) was identified with a quantum unipotent cell of the loop group LSL_2 in [Cautis-Williams, arXiv:1801.08111]. We identify the basis formed by the classes of irreducible equivariant perverse coherent sheaves with the dual canonical basis of the quantum unipotent cell.