Labo J.V.Poncelet: seminars
Oragnizer: Gleb Koshevoy (Lab. Poncelet & CIEM, Moscow)
Organizers: Gregory
Kucherov (LIFL, Lille & Lab. Poncelet, Moscow) & Andrei
Sobolevski (Lab. Poncelet & IITP, Moscow; sobolevski@iitp.ru)
Fall 2012
 12.09.2012 (Wednesday) at 15.30 (Independent University of
Moscow) Thomas Fernique(Laboratoire d'Informatique de ParisNord, UMR nº7030 du CNRS, Institut Galilée  Université ParisNord, France)
The AmmannBeenker Tilings Revisited

We introduce two tiles whose tilings form a oneparameter family of
tilings which can all be seen as digitization of twodimensional planes
in the fourdimensional Euclidean space. This family contains the
AmmannBeenker tilings as the solution of a simple optimization problem.
WinterSpring 2012
 15.03.2012 (Thursday) at 14.30 (Independent University of
Moscow) A.B.Sossinsky (Independent University of Moscow Laboratoire Poncelet, CNRSUIM):
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 socalled 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.
WinterSpring 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 AixMarseille 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 socalled
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 nonrandom potentials on selfsimilar 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
irregularlyshaped 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 ParisSud, France and Poncelet Laboratory, Moscow):
CalogeroSutherland 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 CalogeroSutherland Hamiltonians. This study was initially motivated by the computation of manybody wavefunctions of (nonAbelian) Fractional Quantum Hall systems. In particular we showed a duality between the particle and quasihole wavefunctions. These results hint to new structures of the CalogeroSutherland model which concern duality transformations and nonpolynomial 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 gmodules into sums of fmodules 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é ParisNord, 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):
FussCatalan 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 centrallysymmetric polytopes, and some generalizations of this construction.
This leads to a construction of duality on the set of reflexive centrallysymmetric 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 computergenerated sources
of information. Much of these data is quite complex and highdimensional,
which is different from the classical statistical setting, where the data typically reside in low dimensions.
To address highdimensionality and nonlinearity of the data, a new class
of techniques based on the notion of a Riemannian manifold has recently
become popular in machine learning and highdimensional statistics. In
this talk I will discuss the role of geometry and, in particular, the
LaplaceBeltrami operator, in machine learning and statistical inference.
I will present some practical algorithms based on these ideas as well as
certain theoretical results.
WinterSpring 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 wellknown 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 rcgraphs.
It turns out that these pipe dreams have many interesting combinatorial properties which relate them, among others, to plane partitions (=threedimensional 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 GelfandZetlin 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:
KardarParisiZhang (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
twodimensional flows. We pay a special attention to the random stirring protocol
and study the timedependent behavior of the variance of the braiding exponent.
We show that this behavior belongs to the KardarParisiZhang 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
(AubryMather) 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$ realvalued 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
 Nonabelian 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 nonAbelian 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 ReadRezayi states, which
play a paradigmatic role in the physics of nonAbelian 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_{k1}$ 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 DeligneLusztig varieties
 Let k be an algebraically closed field of characteristic p>0.
Endow k with sigma defined as a nonzero 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 DeligneLusztig 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 cocycles 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 suchandsuch 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 symbolicstochastic 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 finitememory,
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 polynomialtime 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, Paris11
Orsay)
 Random AharonovBohm vortices and some exact families of
integrals
 15.10.2009 at 15.00, Michael
Pevzner (Lab. Poncelet & Université de Reims)
 RankinCohen brackets and covariant quantization
Particular geometric structure of
paraHermitian symmetric spaces allows the definition of a covariant
quantization procedure of these homogeneous manifolds. Composition
formulas (sharpproducts) of quantized operators give a different
interpretation of RankinCohen 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 blockhierarchical 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 scalefree and polyscale
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
Organizer: Gleb Koshevoy (Lab. Poncelet & CIEM, Moscow)
 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 Gequivariant 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 selfcorrecting selfassembly approach
Crystals are generally defined as materials with long range order,
what is physically revealed by sharppeaks diffraction figures. For a
long time, this long range order have though to just mean periodicity.
However, puzzling materials showing sharppeaks 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 nonperiodic 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 (selfassembly stage). Then, in a
second stage (selfcorrecting), 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 3letter alphabet that contains no square as a factor.
A square consists in two consecutive occurrences
of a nonempty word, for example niania or diadia.
He also proved that a (now famous) infinite word over
a 2letter alphabet, the ThueMorse 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 kletter 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 nonempty 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
1970s) 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 twodimensional FockGoncharov 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 multidimensional 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 semiorthogonal decompositions (continuation)
 13.03.2008 Alexander Kuznetsov (MI RAS and Poncelet Lab)
 Derived categories of coherent sheaves and semiorthogonal 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 CWcomplex, 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 GelfandSerganova strata. Each network corresponds to a cell and gives its parametrization. This study leads to new interesting combinatorial objects such as Ldiagrams, 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
Qoperator 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 GaussGivental 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 numbertheoretic 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 "oneway 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 nonoriented 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 01 information depending on whether or not the subset contains at least two vertices related by an edge (reaction). For this model, we show that nonadaptive 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 informationtheoretic lower bound), whereas $\Theta(n^2)$ queries are necessary to make by nonadaptive algorithms \cite{alon}. Many other interesting classes of graphs require $\Theta(n^2)$ nonadaptive 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 informationtheoretic lower bound for Hamiltonian cycles is only $\Theta(n)$ queries and, somewhat surprisingly, it can be reached by a nonadaptive 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, nonadaptive 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 GelfandTsetlin bases
 23.01.2006 Gleb Koshevoy
 Weighted colored graphs and crystal bases