The Departmental Seminar is held on Tuesdays at Yandex Company offices (metro station Park Kultury, Lva Tolstogo st., 16).

You can subscribe to an RSS or Livejournal feed of this seminar (and several other seminars on similar subjects) at http://combalg.ru/seminars.

### Past meetings:

December 11th 2012, 18:30–20:00

**A. Skopenkov. “Algorithms to indentify realizability of hypergraphs”**

There is a well-known fast (linear, to be exact) algorithm to determine whether a given graph is planar, i.e., whether it can be drawn on a plane so that there are no intersections or self-intersections of its edges.

We are going to consider a similar problem for hypergraphs in spaces of arbitrary dimensions: how to determine whether an $n$-dimensional hypergraph (i.e., a simplicial complex) can be embedded in an $m$-dimensional space?

It is known that for $6< 2m < 3n+3$ the above problem of determining the possibility of an embedding a hypergraph in a space is NP-hard (Matousek et al, http://arxiv.org/abs/math/0807.0336); a sketch of the proof will be presented at the talk. This result indicates that it is probably impossible to construct a fast algorithm to solve this embedding problem. The proof will be based on reducing a certain problem defined in terms of Boolean functions (which is known to be NP-hard) to the hypergraph embedding problem. For $2m \ge 3n+3$, a fast algorithm to determine if a given hypergraph can be embedded in a given space will be constructed, and a similar problem—algorithmic identification of knottedness—will be discussed

November 27th 2012, 18:30–20:00

**A. Voronenko “Theory of nonrepeating functions”**

In 2002–2012 a number of mathematicians researched the nondegenerate problem of nonrepeating function testing. The principal results of this research will be presented in the talk.

November 20th 2012, 18:30–20:00

**E. Dashkov “Algebras of provability of theories with validity verification”**

Formal theories, including those connected to mathematical research (e.g., Peano Arithmetic PA), can be mapped to ordinal numbers that, in some way, express the “strength” of these theories. Gentzen’s classical result states that if a certain primitively recursive system of ordinal notation is chosen, then PA proves the scheme of transfinite induction to any $\alpha < \epsilon_0$. However, the same scheme for $\epsilon_0$ yields the consistency of PA itself.

The choice of a particular complete ordering is important. For instance, it is possible to construct a primitively recursive complete ordering of type only $\omega$, such that induction w.r.t. this ordering will yield the consistency of PA. The same construction can be applied to many other theories strictly stronger or weaker than PA.

Thus, we arrive at a problem of finding a certain canonical system of ordinal notation which would allow us to map theories to ordinals in a meaningful manner.

L. Beklemishev proposed that the systems of ordinal notation were extracted from a natural object connected with the theory: the so-called provability algebra, i.e., the Lindenbaum algebra augmented by certain provability operators. In particular, this approach allowed them to obtain a new proof of PA consistency.

Further developments imply analysis of stronger theories, such as various second order arithmetic subsystems. It is convenient to represent such theories by augmenting PA by Tarski validity predicates. Such extensions are in themselves interesting mathematical objects.

Currently, I am devoting most of my time to studying their provability algebras.

December 4th 2012, 18:30–20:00

**A. Glibichuk “Quasi-polynomial Freiman–Ruzsa theorem”**

The famous polynomial hypothesis of Freiman and Ruzsa states that if $A$ is a subset of an arbitrary Abelian group with the property $|A+A|\le k|A|$ (i.e., it is of small doubling), then it contains a polynomially large subset $A^{‘}\subset A, |A^{‘}|>|A|/K^ {C}$, where $C$ is an absolute constant, such that it is contained in a generalized progression of a polynomial size (unlike $A$ itself, which, in general, may be contained in a progression of exponential size w.r.t. $K$). In 2010 T. Sanders obtained the best known result related to the Freiman–Ruzsa hypothesis. His estimate replaced polynomials with the expression $K^{\log^6(K)}$. Later, Shachar Lovett considerably simplified Sanders’s proof and obtained a slight improvement of the result (achieving $K^{\log^3(K)}$) in the case where $A$ is a subset of the space $\mathbb{F}_2^{n}$. The talk will present Lovett’s elegant proof and explain the interesting method of Kroot and Sisask, which lies in the foundation of Sanders’s result.

October 23rd 2012, 18:30–20:00

**M. Zhukovski “Zero-one laws”**

The talk will be devoted to limit characteristics of probabilities of first order properties of random Erdos-Renyi graphs. The main part of the talk deals with the case p=exp(-a lnN), where p is the probability of an edge, and N is the number of graph vertices. We will discuss values of the parameter $a$ such that the zero-one law is satisfied and such that the limits of property probabilities exist, depending on the limit on the quantifier depth of formulas.

October 16th 2012, 18:30–20:00. The meeting was held at MSU (the seminar of Adyan and Beklemishev, room 16-04).

**A. Kupavski. “Distance graphs with a large girth and a large chromatic number”**

In 1959, Erdos proved that for all positive integers l and k there exists a graph with its chromatic number larger than k and its girth (the length of the shortest cycle) larger than l. The following fact will be proved at the talk: for any l there exists a sequence of distance graphs with girths larger than l such that their chromatic numbers increase asymptotically as (c+o(1))^n, where c>1, and n is the dimension of the underlying space.

October 9th 2012, 18:30–20:30

**D. Shabanov “Two approaches to obtaining estimates in Van der Waerden’s theorem”**

The famous Van der Waerden’s theorem states that for all positive integers n>2, r>1 there exists a minimal number W(n,r) such that in any coloring of the set of integers between 1 and W(n,r) into r colors there exists a length n arithmetic progression of one color. The quantity W(n,r) defined by Van der Waerden’s theorem is called Van der Waerden’s function. The considerable and longstanding research effort to find W(n,r) and to solve other similar problems has led to an emergence of an entire new direction in modern mathematics—additive combinatorics. The talk will present two approaches to obtaining lower estimates of Van der Waerden’s function. The first is related to the theorem on symmetry and dense problems in additive combinatorics. The second approach is connected to extremal problems in hypergraph coloring. A new lower bound for W(n,r) based on the second approach will be presented.

October 2nd 2012, 19:00–20:30

**A. Kudinov “Modal logic in topological spaces”**

I will attempt an accessible description of the basic notions of modal logic. The talk will be devoted to propositional modal logic, which is essentially the classical logic of statements, expanded by one or more one-place connectives. Topological semantic for modal logics will be defined, where a modal connective is interpreted as taking an interior of a set. First, I will present classical results obtained in 1994 by McKinsey & Tarski. Then we will discuss augmenting the expressive power of a language by adding new modalities: the universal modality, the modality of inequality, and the modality of an arbitrary set.

September 25th 2012, 18:30–20:00

**G. Gusev “Solving a nondegenerate system of $n$ equations in $n$ complex variables, where the system has a unique root in a complex torus”**

I will present a theorem proved jointly with Sasha Esterov a couple week ago. From theoretical geometry we know that the number of solutions of a nondegenerate system of polynomial equations is the same as the mixed volume of Newton polytopes of the polynomials that define the system. Two natural questions arise: when is this volume equal to zero, and when is it equal to 1? The answer to the first question can be easily obtained by a university student, whereas the second question gives rise to a rather complicated theorem of classification, which is going to be the subject of my talk. It is notable that this theorem can be stated in a rather concise manner, and that the theorem leads to a simple and intuitive algorithm of finding the unique solution of the corresponding system of equations.