In the fall semester of 2012 the meetings of the interdepartmental seminar will be held in Dolgoprudny on Wednesdays at 18:30–20:00 in room 430 of the Main Building.

The seminar is organized jointly with the Department of Mathematical Principles of Control (Faculty of Control and Applied Mathematics) and the Department of Higher Mathematics of the Moscow Institute of Physics and Technology.

The seminar is supported by the Laboratory of structural methods of data analysis in predictive modeling (PreMoLab), Moscow Institute of Physics and Technology, and grant No. 11.G34.31.0073 of the Government of Russian Federation.

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 5th 2012

**I. Sabitov. “Bendable polyhedra”**

November 28th 2012

**V. Gurvich. “n-graphs, games of n players and the ?-conjecture”
**Annotation

Watch online

The notion of an n-graph is introduced, and certain properties and applications of n-graphs are discussed. In particular, n-graphs allow for a characterization of non-repeating Boolean functions (n=2), normal form tables of positional games of n players with complete information, and normal box packings. A ?-conjecture on n-graphs is formulated. If proved, this conjecture would allow a reduction of n-dimensional normal packings to the two-dimensional case.

November 21 2012

**A. Zahakarov, A. Savvateev**** “The Matroska theorem”
**Watch online

A “most general model of a dynamic game” (where the players make simultaneous moves step-by-step) will be constructed.

This game can be viewed as a formalization of an entire series of applied problems in new political economy, as well as other areas of theoretical economics. Our model generalizes the classical formulation of the dynamic programming problem for an infinite horizon, Markov games, ordinary games of several players, and, finally, the standard model of an infinite repeating game.

The proof of the theorem is based on “nested” theorems on existence of stationary points: the principle of contracting mappings on the inside, and Kakutani’s theorem on the outside. Because of this construction, we dubbed it the “Matroska theorem”.

November 7th 2012

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

Watch online

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?

Theory of hypergraphs is a rapidly developing chapter of mathematics originating on the fringe of combinatorics, topology, and programming.

We are going to start by an elementary treatment of the problem of stability of self-intersections of a planar path (http://www.turgor.ru/lktg/2008/5/index.php, Sekliutski 1969, Repovsh and A. Skopenkov 1998, Mintz 1997, M. Skopenkov 2003).

Using this few-dimensional example, we will familiarize ourselves with the main idea of the van Kampen obstacle to embedding n-dimensional hypergraphs in a 2n-dimensional space.

The main results presented in the talk are the theorem on the existence of a polynomial algorithm to identify embeddability of n-dimensional hypergraphs in a 2n-dimensional space for n>2 and the nonexistence of such algorithm for n=2 (Van Kampen 1932, Shapiro 1957, Woo 1957, Matousek-Tancer-Wagner, 2008, http://www.mccme.ru/circles/oim/algor.pdf).

A popular review of the topic will be presented, including basic ideas of proofs accessible to non-specialists (specifically, students). The most of the talk will be accessible to first-year students.

All necessary definitions (hypergraph, embeddability, homology groups, Van Kampen obstacle, etc.) will be included in the talk. The basic ideas will be presented through “mathematics olympiad” problems: in two dimensions, for the simplest special cases, free of technical details and reduced to a necessary minimum of algebraic terminology.

October 24th 2012

**A. Raigorodsky “On Borsuk’s conjecture”**

Watch online

In my lecture I will present a classical conjecture of Borsuk on partitioning of sets in metric spaces into parts of smaller diameter. I will discuss both well-established results and new developments: for example, the refutation of Borsuk’s conjecture on spheres of small radius and on existence of diameter graphs with a large girth (without cycles of a length smaller than a certain predetermined value). A number of unsolved problems will be presented, many of which can be solved by a first-year student.

October 17th 2012, room 214 of the Left Building

**17:05 – 18:25: А. Shen “Aperiodic tilings of a plane”**

Watch online

Back in the beginning of 1960, Hao Wan posed the following question: given a collection of square tiles with colored edges, fill a plane with their shifted copies so that every edge common to two tiles also has a common color. This is sometimes possible and sometimes not. If such a tiling exists, does there also exist a periodic tiling (here periodicity is defined by requiring that a tiling maps to itself when shifted by a certain vector)? A negative answer to that question was given by Berger in 1966, and many other aperiodic tilings have been constructed since then.

The talk will include the history of this problem and present constructions of certain aperiodic tilings.

**18:30 – 20:00: I. Ivanov-Pogodaev, A. Kanel-Belov “Finitely defined nil-halfgroups and aperiodic tilings”**

Watch online

The talk is devoted to Burnside-like conjectures—the proof of Shevrin’s conjecture on existence of an infinite finitely defined nil-halfgroup and construction of a skew field finitely defined as a ring (a joint result with I. Rips).

October 10th 2012

**G. Kabatyanski “How are finite fields relevant to the real world?”**

Download

October 3rd 2012

**I. Shkredov. “Problems in additive combinatorics” (continued)**

Download

Watch online

We are going to make a short survey of problems in additive combinatorics and present some of the available results.

The talk will include the following topics:

1. Linear equations over dense sets.

2. Freiman’s theorem.

3. Additive structures in sums.

4. Sums of products.

September 26th 2012

**I. Shkredov. “Problems in additive combinatorics”**

Download

Watch online

We are going to make a short survey of problems in additive combinatorics and present some of the available results.

The talk will include the following topics:

1. Linear equations over dense sets.

2. Freiman’s theorem.

3. Additive structures in sums.

4. Sums of products.

September 19th 2012

**A. Garber. “Voronoi’s conjecture about parallelohedra”**

Download

Watch online

Voronoi’s conjecture states that any parallelohedron, i.e., a polyhedron that allows for a partitioning of a space into its parallel copies, is affine equivalent to a Dirichlet-Voronoi polyhedron for some lattice.

Certain results concerning Voronoi’s conjecture will be presented in this talk. In particular, the talk will include a plan and possibly some details of the proof of Voronoi’s conjecture in a new special case where the surface of the parallelohedron remains connected when a certain class of facets of codimension 2 is removed.

The talk is based on the results obtained jointly by the speaker, A. Gavrilyuk and A. Magazinov.

September 12 2012

**The seminar was not held.**

September 5th 2012

**A. Kanel-Belov “On combinatorics of words and symbolic dynamics”**

Download