Labo J.-V.Poncelet: seminars

Fall 2012

12.09.2012 (Wednesday) at 15.30 (Independent University of Moscow) Thomas Fernique(Laboratoire d'Informatique de Paris-Nord, UMR nº7030 du CNRS, Institut Galilée - Université Paris-Nord, France)
The Ammann-Beenker Tilings Revisited

     We introduce two tiles whose tilings form a one-parameter family of tilings which can all be seen as digitization of two-dimensional planes in the four-dimensional Euclidean space. This family contains the Ammann-Beenker tilings as the solution of a simple optimization problem.

Winter-Spring 2012

15.03.2012 (Thursday) at 14.30 (Independent University of Moscow) A.B.Sossinsky (Independent University of Moscow Laboratoire Poncelet, CNRS-UIM):
KNOT ENERGY AND FLAT NORMAL FORMS OF KNOTS

    A new approach to knot energy, motivated by a series of physical experiments with a resilient wire contour, will be presented. Amazingly, all the experiments produced the same normal form (corresponding to the energy minimum) for any knot from a given isotopy class with seven crossings or less. Thus our little wire contour outperforms the classical knot energies (e.g. Moebius energy) studied by Fukuhara, O'Hara, Freedman and others. Some experiments will be demonstrated and many of their results (often unexpected) will be described.

    Then the first steps of the mathematical modeling of the behavior of the wire contour will be sketched (this is joint work with Oleg Karpenkov). They involve some variational calculus, elliptic functions, combinatorics of knot diagrams, and the phase space of the pendulum. We will also discuss so-called flat knots (mathematical counterparts of a resilient wire contour squeezed between two parallel planes), their normal forms and their relationship with classical (3D) knots.

    The talk will be accessible to mathematicians and mathematical physicists without any knowledge of knot theory: the very few basic facts from that theory needed in the exposition will be explained. A number of new problems (not involving special knowledge of knot theory, but possibly necessitating the calculus of variations, geometric combinatorics, differential geometry, and numerical simulations) will be formulated.

Winter-Spring 2011

26.05.2011 (Thursday) at 15.00 (Independent University of Moscow) Giovanni Cerulli Irelli (Haussdorff Research Institute for Mathematics):
Quiver Grassmannians of Kronecker type and applications to cluster algebras

    Cluster algebras are commutative rings introduced by Fomin and Zelevinsky with the aim studying total positivity in semisimple algebraic groups. There is a natural notion of positivity in every cluster algebra and describing the semiring of positive elements is still an open problem. We will explain in details the connection with quivers and quiver representations. In particular it is natural to ask what is the counterpart of positivity under this connection. The answer to this question is part of my current research. The first step was done in a joint paper with F.Esposito and it will be the main subject of the talk.

17.03.2011 (Thursday) at 15.00 (Independent University of Moscow) Nicolas Bedaride (Universite Aix-Marseille III, France and Poncelet Laboratory, Moscow):
Symbolic dynamics for some dynamical systems

    The aim of the talk is to describe the symbolic dynamics of different dynamical systems. We will consider following dynamical systems: billiard, outer billiard, piecewise isometries, interval exchange and we will explain the different methods to understand the languages and the symbolic dynamics associated to these maps.

03.03.2011 (Thursday) at 15.00 (Independent University of Moscow) Denis Grebenkov (Ecole Polytechnique, France and Poncelet Laboratory, Moscow):
Localization of the Laplace operator eigenfunctions

    The notion of localization was introduced in solid state physics by P. W. Anderson who suggested that randomness of a potential in the Schrodinger equation may lead to localized eigenstates in disordered media. This so-called Anderson localization, which is responsible for the metal/isolator transition in solids, has found numerous experimental confirmations. This phenomenon is called "strong" localization characterized by exponential space decay of the modulus of the wave amplitude. The localization has also been shown to occur for non-random potentials on self-similar deterministic fractals like Sierpinski gasket. In such disconnected domains, the localized eigenfunctions are supported by a small subset of the domain and are zero elsewhere. A series of experimental and numerical studies have recently shown the emergence and importance of weakly localized eigenfunctions in irregularly-shaped domains. These eigenfunctions are localized in a small subset of the domain and are very small (but not zero) outside this subset. This type of localization, due to destructive interference is generally called "weak" localization and is characterized by a power law decay in space. It is worth stressing that the localized eigenfunctions constitute only a fraction among all eigenfunctions. The mathematical analysis of weakly localized eigenfunctions is therefore a challenging problem because it addresses only a subset of eigenfunctions. Even a rigorous mathematical definition of weak localization is not yet available, in spite of a growing interest to this topic in recent years.

24.02.2011 (Thursday) at 15.00 (Independent University of Moscow) Alexander Kuznetsov (Steklov Mathematical Institute, Moscow):
Exceptional bundles on homogeneous varieties

    An exceptional collection in the derived category of coherent sheaves on a variety gives an effective description of arbitrary objects in the category, it can be considered as an analogue of a basis of a vector space. I will talk about a new approach to an old conjecture saying that any compact homogeneous variety of a semisimple algebraic group has a full exceptional collection, and about some surprising combinatorics of weights and roots related to this problem.

10.02.2011 (Thursday) at 15.00 (Independent University of Moscow) Raoul Santachiara (LPTMS, Universite de Paris-Sud, France and Poncelet Laboratory, Moscow):
Calogero-Sutherland Hamiltonian eigenfunctions and conformal field theory correlators

     We have recently shown that the differential equations satisfied by the correlators of a large family of conformal field theories (based on Virasoro and, more in general, on W algebras) is directly related to Calogero-Sutherland Hamiltonians. This study was initially motivated by the computation of many-body wavefunctions of (non-Abelian) Fractional Quantum Hall systems. In particular we showed a duality between the particle and quasi-hole wavefunctions. These results hint to new structures of the Calogero-Sutherland model which concern duality transformations and non-polynomial eigenfunctions.

Fall 2010

27.01.2011 (Thursday) at 15.00 (Independent University of Moscow) Oleg Ogievetsky (CPT, Luminy, Marseille and Poncelet Laboratory, Moscow):
Diagonal reduction algebras

    Let g be a Lie algebra and f its reductive Lie subalgebra. The branching rules of decompositions of g-modules into sums of f-modules are conveniently described with the help of a certain algebra, associated to the pair (g,f), called "reduction" algebra. I will illustrate on (possibly) simple examples the general structure of reduction algebras and tools to work with them. If time allows, I will say some words about diagonal reduction algebras which are related to decompositions of tensor products of irreps of reductive Lie algebras into the direct sums of irreps.

09.12.2010 (Thursday) at 14.00, Thomas Fernique (Laboratoire d'Informatique Fondamentale, Marseille, and Poncelet Laboratory, Moscow):
Combinatorial substitutions and sofic tilings

    A combinatorial substitution is a map over tilings which allows to define sets of tilings with a strong hierarchical structure. We give an explicit construction which shows that such sets of tilings are sofic, that is, can be enforced by finitely many local constraints. This extends some similar previous results (Mozes?90, Goodman- Strauss?98) in a much shorter presentation.

01.12.2010 (Wednesday) at 14.00, Gerard H. E. Duchamp (Laboratoire d´Informatique de l´Université Paris-Nord, France):
Schützenberger factorization and noncommutative differential equations. Abstract and details

01.12.2010 (Wednesday) at 15.00, Karol Penson (LPTMC, Université Pierre et Marie Curie, France):
Fuss-Catalan Numbers as Moments. Abstract and details

07.10.2010 (Thursday) at 15.30, Igor Artamkin (High School of Economics, Moscow State Institute of Radiotechnics, Electronics and Automation, and Poncelet Laboratory): A polytope of simple cycles in a graph

    Given a graph, we propose an elementary construction of a pair of reflexive centrally-symmetric polytopes, and some generalizations of this construction. This leads to a construction of duality on the set of reflexive centrally-symmetric polytopes. Initially the problem had arized in toric geometry: the initial graph was the graph of a maximally degenerated nodal curve, and the toric manifold corresponding to the reflexive polytope was a Fano manifold, a natural compactification of its generalized Jacobian.
     In the talk we will emphasize combinatorial and geometrical aspects.

16.09.2010 (THURSDAY) at 13.00, Mikhail Belkin (Ohio State University):
Geometric Aspects of Machine Learning

     In recent years techniques for automated analysis of data have become increasingly important in large part due to the development of Internet, computer imaging and numerous other computer-generated sources of information. Much of these data is quite complex and high-dimensional, which is different from the classical statistical setting, where the data typically reside in low dimensions. To address high-dimensionality and non-linearity of the data, a new class of techniques based on the notion of a Riemannian manifold has recently become popular in machine learning and high-dimensional statistics. In this talk I will discuss the role of geometry and, in particular, the Laplace-Beltrami operator, in machine learning and statistical inference. I will present some practical algorithms based on these ideas as well as certain theoretical results.

Winter-Spring 2010

13.05.2010 (THURSDAY) at 15.00, Evgeny Smirnov (Independent University of Moscow):
Schubert polynomials, pipe dreams and related combinatorial objects

     Schubert polynomials were introduced by A.Lascoux and M.P.Schuetzenberger as a tool for certain questions of geometry of flag varieties. They naturally generalize well-known Schur polynomials. In 1996 S.Fomin and An.Kirillov provided a realization for Schubert polynomials using combinatorial objects usually referred to as pipe dreams, or rc-graphs.
     It turns out that these pipe dreams have many interesting combinatorial properties which relate them, among others, to plane partitions (=three-dimensional Young diagrams) and Stasheff associahedra. Some of them were already observed in 1990s by Fomin and Kirillov, Billey et al.; some other properties are new. In my talk I will give an overview of these properties. Time permitting, I will also explain how pipe dreams are related to our work in progress with V.Kiritchenko and V.Timorin on the realization of Schubert calculus on full flag varieties via Gelfand-Zetlin polytopes.

14.04.2010 (WEDNESDAY) at 15.00, Alexander Tiskin (University of Warwick):
The tropical Monge matrices: Algebraic structure and algorithms

     Monge matrices are a fundamental object in optimisation theory, as well as in graph and string computation. In this respect, tropical multiplication of Monge matrices is of great interest, since it corresponds to finding shortest paths in a planar digraph. We consider a subclass of Monge matrices, obtained by taking submatrix sums in permutation matrices. Under tropical multiplication, this subclass forms a monoid, which can be described by a simple modification of the classical braid group. It turns out that multiplication in this monoid can be performed very fast. This leads to a large number of applications: fast decision of the Bruhat order on permutations; fast maximum clique computation in a circle graph; fast approximate pattern matching in a compressed file. We will give the main theoretical results, and then survey some of the applications.

25.03.2010 at 15.00. Sergei Nechaev:
Kardar-Parisi-Zhang (KPZ) scaling in topological mixing

     In the spirit of recent works on topological chaos generated by sequential rotation of infinitely thin stirrers placed in a viscous liquid, we consider the statistical properties of braiding exponent which quantitatively characterizes the chaotic behavior of advected particles in two-dimensional flows. We pay a special attention to the random stirring protocol and study the time-dependent behavior of the variance of the braiding exponent. We show that this behavior belongs to the Kardar-Parisi-Zhang universality class typical for models of nonstationary growth. Using the matrix (Magnus) representation of the braid group generators, we relate the random stirring protocol with the growth of random heap generated by a ballistic deposition.

11.03.2010 at 15.00. м.й. бЕПЕЫЮЦХМ:
гЮЛНЫЕМХЪ юЛЛЮММЮ

     мЕБШОСЙКШИ ЬЕЯРХСЦНКЭМХЙ Я ОПЪЛШЛХ СЦКЮЛХ Х ЯРНПНМЮЛХ ОНДУНДЪЫЕИ ДКХМШ ЛНФМН ПЮГПЕГЮРЭ МЮ ДБЮ ЬЕЯРХСЦНКЭМХЙЮ, ОНДНАМШУ ХЯУНДМНЛС Я ЙНЩТТХЖХЕМРЮЛХ k Х k^2. яПЕДХ БЯЕУ ГЮЛНЫЕМХИ ОКНЯЙНЯРХ ОНКСВХБЬХЛХЯЪ ЬЕЯРХСЦНКЭМХЙЮЛХ ЛНФМН БШДЕКХРЭ ГЮЛНЫЕМХЪ, МЮГШБЮЕЛШЕ ГЮЛНЫЕМХЪЛХ юЛЛЮМЮ. гЮЛНЫЕМХЪ юЛЛЮММЮ НАКЮДЮЧР ХМРЕПЕЯМШЛХ ЯБНИЯРБЮЛХ. мЮОПХЛЕП, КЧАНЕ ГЮЛНЫЕМХЕ юЛЛЮММЮ МЕОЕПХНДХВМН.

25.02.2010 at 15.00. Andrei Sobolevski (Institute for Information Transmission Problems and Poncelet Laboratory):
Fast transport optimization for Monge costs on the circle

     Consider the problem of optimally matching two measures on the circle, or equivalently two periodic measures on the real line, and suppose the cost $c(x, y)$ of matching two points of matching two points $x, y$ satisfies the Monge condition: $c(x_1, y_1) + c(x_2, y_2) < c(x_1, y_2) + c(x_2, y_1)$ whenever $x_1 < x_2$ and $y_1 < y_2$. We introduce a notion of locally optimal transport plan, motivated by the weak KAM (Aubry-Mather) theory, and show that all locally optimal transport plans are conjugate to shifts and that the cost of a locally optimal transport plan is a convex function of a shift parameter.
     This theory is applied to a transportation problem arising in image processing: for two sets of point masses on the circle, both of which have the same total mass, find an optimal transport plan with respect to a given cost function satisfying the Monge condition. In the circular case the sorting strategy fails to provide a unique candidate solution and a naive approach requires a quadratic number of operations. For the case of $N$ real-valued point masses we present an $O(N log \varepsilon )$ algorithm that approximates the optimal cost within $\varepsilon$; when all masses are integer multiples of $1/M$, the algorithm gives an exact solution in $O(N log M)$ operations.

11.02.2010 at 15.00. Raoul Santachiara (LPTMS, Orsay):
On W symmetries and Jack polynomials in fractional quantum Hall systems

    Non-abelian phases are gapped phase of matter in which the adiabatic transport of one excitation around another implies a unitary transformation within a subspace of degenerate wavefunctions which differ from each other only globally.
    Much of the comprehension of non-Abelian fractional quantum Hall (FQH) states relies on the conformal field theory(CFT). In this approach, the analytic part of trial wave functions is given by the conformal blocks of a given CFT. We consider the Read-Rezayi states, which play a paradigmatic role in the physics of non-Abelian states, and a their recently proposed generalization, the Jacks wavefunctions.
    We will see that all these family of FQH states are related to the representation theory of the $WA_{k-1}$ chiral algebra and we will use this representation theory to derive differential equations which characterize the most general Read Rezayi and Jack excited wavefunctions.

28.01.2010 at 15.00. Xavier Caruso:
Dimensions of generalized affine Deligne-Lusztig varieties

    Let k be an algebraically closed field of characteristic p>0. Endow k with sigma defined as a non-zero power of the absolute Frobenius on k and extend sigma to a continuous ring endomorphism of k((u)) by sending u to u^b for some integer b>1. In this talk, I will explain how one can associate to these data some generalized affine Deligne-Lusztig varieties and then how one can estimate their dimensions.

14.01.2010 at 15.00. Victor GAYRAL (Reims):
Singular traces in von Neumann algebras

    Dixmier traces in von Neumann algebras play an important role in noncommutative geometry, for instance to compute local co-cycles in index theory for type II spectral triples. In this introductory talk, I will explain our (with A. Cary, A. Rennie and F. Sukochev) contribution to the theory of locally compact type II spectral triples.

Fall 2009

17.12.2009 Alexander Dikovsky (LINA, Nantes) at 14.00 and Daniil Ryabko (INRIA, Lille) at 15.30

A. Dikovsky: Bootstrapping of wide coverage dependency grammars
    In computer science, the term “bootstrapping” applies to procedures which incrementally construct complex structures (data / automata / compilers / theories, etc.) from initial rudimentary knowledge. In psycholinguistics, it applies to models of first language acquisition from rudimentary prosodical and syntactic / semantic structures in a pragmatic context. The existing formal theories arrive to model grammar inference in the limit from series of examples of correct sentences (or structures) under very restrictive conditions and without a guarantee of incrementality.
    In this talk will be presented a strategy of practical incremental development of wide coverage dependency grammars from examples of correct dependency structures. The keystone of this strategy is the use of Categorial Dependency Grammars (CDG) as a formal model of dependency syntax. CDG are not rule grammars. They are completely lexicalized and assign to words their dependency types in the style “to be governed through dependency "d", the word should have subordinates through such-and-such dependencies in a certain order.” Importantly, the CDG define dependency structures, projective or not, completely locally, i.e. within the words' local domains: the governor and all its immediate subordinates. It is due to this locality that the strategy is incremental. The grammar is gradually constructed by generalization of types, grouping words into classes, specialization of dependencies and of classes and by lexical expansion. In order to have a realistic size and, respectively, to be developed in a reasonable time, it needs the use of “flexible” types (with alternatives, options and partial orders).
    We illustrate this strategy using toy grammars and also a large scale CDG for French developed in a relatively short time. Will also be discussed important aspects of efficient parsing of large scale CDG, in particular, efficient parsing of the flexible types, mixed symbolic-stochastic parsing, training of probabilistic oracles on corpora and development of training corpora.
D. Ryabko: Asymptotically optimal perfect steganographic systems
A steganographic system is proposed for the case when covertexts (containers) are generated by a source that has zero or finite-memory, with unknown statistics. The probability distributions of covertexts with and without hidden information are the same; this means that the proposed stegosystems are perfectly secure, i.e. an observer cannot determine whether hidden information is being transmitted. The speed of transmission of hidden information can be made arbitrary close to the theoretical limit - the Shannon entropy of the source of covertexts. All the proposed algorithms are polynomial-time in all arguments. An interesting feature of the proposed stegosystems is that they do not require any (secret or public) key. In other words, shared secret is not required to obtain perfect steganographic security. In addition, some limitations to steganography will be demonstrated for the case when the source of covertexts does not obey the finite memory assumption.

3.12.2009 at 15.00, Vladimir Vershinin (Montpelier)

On certain objects connected with braids
The following objects will be defined and studied: virtual braids, Brunnian braids, inverse braid monoid, McCool group, etc.

29.10.2009 at 15.00, Stephane Ouvry (LPTMS, Paris-11 Orsay)

Random Aharonov-Bohm vortices and some exact families of integrals

15.10.2009 at 15.00, Michael Pevzner (Lab. Poncelet & Université de Reims)

Rankin-Cohen brackets and covariant quantization
     Particular geometric structure of para-Hermitian symmetric spaces allows the definition of a covariant quantization procedure of these homogeneous manifolds. Composition formulas (sharp-products) of quantized operators give a different interpretation of Rankin-Cohen brackets based on branching laws for infinite dimensional representations and open new perspectives in studying modular forms for groups of a higher rank.

08.10.2009 at 15.00, Serguei Nechaev (LPTMS, Orsay & Lab. Poncelet, and Lebedev Physics Institute, Moscow)

On some physical applications of random hierarchical matrices
     Investigation of spectral properties of block-hierarchical random matrices is connected, for the first time, to dynamical and structural characteristics of complex hierarchical systems with disorder. I will discuss peculiarities of dynamics on random ultrametric energy landscapes, as well as statistics of scale-free and poly-scale networks (depending on their topological characteristics) obtained by a mipmapping procedure.

24.09.2009 at 15.00, Macha Nikolski (LaBRI, Université de Bordeaux & Lab. Poncelet)

Reconstructing ancestral architectures from highly divergent eukaryotic genome sequences

Spring 2009

28.05.2009 at 13.00. Pasquale Zito

The equivariant Drinfeld centre
     The monoidal centre Z(C) of a tensor category C (also known as "Drinfeld centre" or "quantum double") is, under pretty general circumstances, a modular category. After recalling these notions, as well as that of a G-equivariant modular category (after Turaev, Kirillov jr.), I will introduce an equivariant version of the centre construction and use it to sketch a proof of a conjecture regarding inclusions of modular categories.

29.01.2009 at 16:00. Thierry Monteil

Finite blocking property on polygonal billiards and translation surfaces
     A planar polygonal billiard (resp. a translation surface) P is said to have the finite blocking property if for every pair (O,A) of points in P there exists a finite number of "blocking" points B1,...,Bn such that every trajectory from O to A meets one of the Bi's. This property was introduced by Fomin in a problem of the the Leningrad's Olympiad in 1989, and solved there for the squared billiard table. The talk will focus on this property, that can be considered as a property about illumination in P. We will relate it to the geometry of the surface (being a flat torus branched covering) and a property of the directional flow on the surface (pure periodicity). The equivalence between those three notions holds under a homological condition on P. Also, we will give a complete classification for Veech surfaces and the surfaces of genus 2.

22.01.2009 at 14:00. Thomas Fernique (LIF, Marseille)

Quasicrystal growth: a self-correcting self-assembly approach
    Crystals are generally defined as materials with long range order, what is physically revealed by sharp-peaks diffraction figures. For a long time, this long range order have though to just mean periodicity. However, puzzling materials showing sharp-peaks diffraction figures (as crystals do) but with symmetry excluding periodicity have been discovered in 1984, and soon called quasicrystals.
    A widely spread mathematical model for quasicrystals are tilings. Surprisingly, some non-periodic tilings can be finitely enforced by so- called matching rules, i.e., rules that specify the way tiles can locally fit together (as for a jigsaw puzzle). This provides an appealing model for quasicrystal growth: a melt "freezes" by gluing the atoms together according to these matching rules, with a quasicrystals being eventually formed. However, such a growth model does not seem physically realist, since building a tiling tile by tile, according to matching rules, often leads to "dead configurations", that are finite sets of tiles which cannot be extended to an entire tiling, although matching rules are respected.
    In this talk, we will introduce a new growth model. Instead of trying to grow a perfect tiling, we first relax the matching rules in order to allow tilings with (a certain type of) errors, with those being expected to be more easily grown (self-assembly stage). Then, in a second stage (self-correcting), we allow local transformations called flips to be performed on the obtained tiling ; more precisely, the more performing a given flip locally (i.e. on some neighborhood of the tiles involved in the flip) seems to correct the tiling, the higher the probability of effectively performing this flip is.
    We review some open questions risen by this model that we are just starting to study.

Fall 2008

11.12.2008 at 16:30, Thursday. Pascal Ochem

Infinite words avoiding patterns
    Axel Thue proved in the beginning of the last century that there exists an infinite word over a 3-letter alphabet that contains no square as a factor. A square consists in two consecutive occurrences of a non-empty word, for example niania or diadia. He also proved that a (now famous) infinite word over a 2-letter alphabet, the Thue-Morse word, contains no cubes (three consecutive occurrences of a nonempty word). In order to obtain similar results, we can extend the notion of square and cube to the notion of pattern. We consider infinite words over k-letter alphabets. A pattern is a finite word over the alphabet of capital letters A,B,C,... An occurrence of a pattern is obtained by replacing each letter A,B,C,... by a non-empty word. For example, 01011101 is an occurrence of the pattern AABBA with A->01, B -> 1. A word avoids the pattern P if it contains no occurrence of P as a factor. The avoidability index A(P) of the pattern P is the smallest integer k such that there exists an infinite word that avoids P.

30.10.08 at 15.30 Sergei SOLOVIEV (IRIT, Toulouse)

Isomorphism of types
    The problem of isomoprhism of types, for example, A->(B->C) and AxB->C has many applications, such as information retrieval in functional databases, and is linked to many interesting mathematical questions, such as so called "Tarsky High School Algebra Problem". In my talk I intend to present the developments over many years (since the end of 1970-s) and the actual state of the subject (solved problems, applications and new directions).

Spring 2008

18.06.2008 Alexandre Usnich (Paris VI)

Cluster mutations for two variables
    Cluster mutations for two variables acting as birational automorhisms on a rational surface. We consider a cluster surface on which all mutations and the group GL(2,Z) acting regularly. Such a surface is defined over Z, it is infinite type and contains all two-dimensional Fock-Goncharov manifolds. We describe its Picard group and explain its connection to the Thompson group T.

09.06.2008 Boris Kunyavsky (Bar Ilan University, Israel)

Characterization of finite solvable groups using methods of arithmetic geometry

26.03.2008 Thomas Fernique (LIRMM)

Tilings, Continued Fractions and Discrete Geometry
    We show how to associate with a unimodular matrix a map which acts over discretizations of hyperplanes or hypersurfaces as this matrix acts over the corresponding real hyperlanes or hypersurfaces. We use it to compute multi-dimensional continued fraction expansions (namely according to the Brun algorithm) of the normal vector of a given discretization of the hyperplane. This process can then be rather naturally extended to a discretization of hypersurfaces, although they generally do not admit a normal vector. This leads to an algorithm for deciding whether a given discretization of a hypersurface is, in fact, a discretization of hyperplane (widely studied problem in discrete geometry).

20.03.2008 Alexander Kuznetsov (MI RAS and Poncelet Lab)

Derived categories of coherent sheaves and semi-orthogonal decompositions (continuation)

13.03.2008 Alexander Kuznetsov (MI RAS and Poncelet Lab)

Derived categories of coherent sheaves and semi-orthogonal decompositions.

Spring 2007

14.06.2007 Alexandre Postnikov (MIT, USA)

Euler, Grassmann, Schubert, and total positivity.
    We discuss the relationship between total positivity and planar directed networks. The totally nonnegative part of the Grassmannian is a remarkable CW-complex, which is naturally linked to the inverse boundary problem for networks. The cells of this complex form a finer subdivision of the Grassmannian than the Schubert decomposition. They are the positive parts of Gelfand-Serganova strata. Each network corresponds to a cell and gives its parametrization. This study leads to new interesting combinatorial objects such as L-diagrams, decorated permutations, alternating chord diagrams, etc. These objects count various generalizations of Eulerian numbers and Eulerian polynomials. We also mention an intriguing combinatorial connection between smooth Schubert varieties and supersolvable hyperplane arrangements.

29.05.2007 Alexey Zamolodchikov

Dynamic triangulations and two dimensional quantum gravitation. II

23.05.2007 Alexey Zamolodchikov (the Poncelet Lab)

Dynamic triangulations and two dimensional quantum gravitation.
    We discuss the critical behavior of statistic systems on nonregular lattices.

25.04.2007 Maxim Kazarian (MIAN, IUM, and the Poncelet Lab)

Combinatorics of the permutation group and the KP hierarchy.
    Being classical stuff, the theory of integrable hierarchies still looks rather mysterious for many mathematicians not involved to this area. I will present a brief and hopefully clear introduction to the theory of the KP hierarchy with applications to the problem of factorization of a permutation into a product of transpositions.

01.03.2007 Dmitry Lebedev

Givental integrals for classical groups.
    The case of GL(N). In 1996 A. Givental introduced a remarkable integral formula for the common eigenfunction of GL(N)-Toda lattice. In [GKLO] it was shown that the Givental representation naturally arises in the representation theory approach. It is based on a particular parameterization of the upper triangular part of the Gauss decomposition of the group element. This parameterization is closed with respect to the factorization into the product of the elementary Jacobi matrices but is slightly different. We will explain an amusing connection of Givental formula with the Baxter Q-operator formalism. I shall explain all details of our construction in the case of GL(N). Generalization to the case of all classical groups will be done in the second lecture.
    [GKLO] A. Gerasimov, S. Kharchev, D. Lebedev, and S. Oblezin, On a Gauss-Givental Representation of Quantum Toda Chain Wave Function. IMRN, 2006, Article ID 96489, 23 p; arXiv:math.RT/0505310

22.01.2007 Igor Artamkin

Polyhedra simple cycles and cuts in graphs.
    We will discuss an elementary construction which sends graphs to integer reflexive polyhedra. An interesting duality appears in this approach. The construction has roots in toric geometry, namely Fano manifolds with terminal singularities correspond to such polyhedra. When we deal with a graph dual to an algebraic curve with simple singularities and rational irreducible components, the corresponding (due to our construction) Fano manifold turns out to be a canonical compactification of its generalized Jacobian.

Fall 2006

04.12.2006 Anton Khoroshkin

     The Lie algebra cohomology of vector fields that preserve the flag of foliations and characteristic classes of flags of foliations. I will describe how to compute the Lie algebra cohomology of formal vector fields in the symmetric powers of coadjoint representations. The relationship to the charecteristic classes of flags of foliations via formal geometry will also be discussed.

Spring 2006

04.04.2006 A.Sossinsky, M.Vyalyi

Arnold complexity: significance and connections.
    The first lecturer will present Arnold's definition of "complexity" of individual finite binary sequences and his main results on the structure of n bit binary sequences with respect to their "Newton derivative". The second lecturer will give a number-theoretic proof of the "hard part" of Arnold's result and speculate about its relationship to other notions of complexity. The seminar should end in a discussion in which Misha Tsfasman and Grisha Kabatyanskii will lend their expertise to discuss eventual connections with "one-way functions", coding, and cryptography.

20.03.2006 Valentin Shehtman (Institute for Information Transmission Problems)

On Kolmogorov's approach to intuitionistic logic.
    In 1933 Kolmogorov proposed the idea of interpreting intuitionistic propositional formulas as "problems". Since that time Kolmogorov's approach was formalized in many different ways. In this talk, we consider two such interpretations introduced by Medvedev: "finite problems" (1962) and "information types" (1978). For intuitionistic logic (H), both interpretations are sound (every provable formula is "valid"), but incomplete (not all "valid" formulas are provable). So the question arises: how to axiomatize the set of all "valid" formulas? This question happens to be very nontrivial. We give an overview of what is known about the corresponding intermediate logics (LM and LM_1) and related combinatorial problems. On the other hand, we show that after a reasonable modification of Medvedev's "information types", the completeness of H is restored.

13.03.2006 Gregory Kucherov, LIFL/CNRS (Lille, France)

Combinatorial search on graphs motivated by bioinformatics applications: a case study and generalizations
    Identifying an unknown object via indirect queries is a type of problem that occurs very often in various applications. These problems are studied in the general area of combinatorial search or, for some more specific formulations, in its subarea called group testing. The general applicative setting that motivates the present study can be described as follows. Assume we have a set of chemicals and each of them reacts with some others. Assume that we can mix two or several chemicals together and observe if some of them react with each other, or maybe even how many "reacting couples" there are in the mixture. Our goal is to recover all pairs of reacting chemicals by using as few experiments as possible. In bioinformatics, such type of problem arises, for example, in whole genome sequencing projects where contigs (contiguous sequenced fragments of the genome) are separated by gaps and the task consists in identifying the order of the contigs on the genome through a possibly minimal number of polymerase chain reactions (PCR) that reveal some information about the presence and possibly the number) of neighbouring contigs from a given set of contigs. Once chemicals and reactions are represented respectively by vertices and edges of a non-oriented graph, we come up with a problem of graph reconstruction. We first focus on a boolean model of queries where an arbitrary subset of vertices (chemicals) can be queried, yielding a 0-1 information depending on whether or not the subset contains at least two vertices related by an edge (reaction). For this model, we show that non-adaptive algorithms turn out to be less powerful than general adaptive algorithms: for example, Hamiltonian cycles can be reconstructed in $O(n\log n)$ adaptive queries (which is an information-theoretic lower bound), whereas $\Theta(n^2)$ queries are necessary to make by non-adaptive algorithms \cite{alon}. Many other interesting classes of graphs require $\Theta(n^2)$ non-adaptive queries for their reconstruction. We then consider a quantitative model, where a query reveals the number of edges in the subgraph induced by the queried set of vertices. Here, the information-theoretic lower bound for Hamiltonian cycles is only $\Theta(n)$ queries and, somewhat surprisingly, it can be reached by a non-adaptive algorithm. Such an algorithm is based on two intricate combinatorial constructions: $d$-detecting and $d$-separating matrices. We then consider generalizations to some other graph classes that will further illustrate that under the quantitative model, non-adaptive algorithms often reach the asymptotic lower bound. We will end up by mentioning some other bioinformatics problems that lead to combinatorial search formalizations. This is a joint work with Vladimir Grebinski.

06.02.2006 Leonid Rybnikov

Shift of invariants and Gelfand-Tsetlin bases

23.01.2006 Gleb Koshevoy

Weighted colored graphs and crystal bases