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? 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.