• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Seminar of the laboratory

The main aim of the seminar is to discuss both new and classical results in Theoretical Computer Science.

The seminar is held weekly. The recurring topic for the Fall 2016 is "Boolean Fourier Analysis". The information on the talks is given below.

The seminar is held at the Department of Computer Science in HSE on Wednesdays from 18:10 to 19:30 in the room 505.

To attend the seminar one should have a pass to the building. If you don’t have a pass please send your contact information (Surname, name) to Ekaterina Vavilova: evavilova@hse.ru .

 October 19 
A. Skopenkov «Stability of intersections of graphs in the plane and the van Kampen obstruction»

 

A map $\varphi:K\to \R^2$ of a graph $K$ is approximable by embeddings, if for each $\varepsilon>0$ there is an $\varepsilon$-close to $\varphi$ embedding $f:K\to\R^2$. Analogous notions were studied under the names of cluster planarity and weak simplicity. We present criteria for approximability by embeddings (P. Minc, 1997, M. Skopenkov, 2003) and their algorithmic corollaries.
A map $\varphi:K\sqcup L\to \R^2$ of the disjoint union of graphs $K$ and $L$ is {\bf approximable by maps with disjoint images}, if for each $\varepsilon>0$ there is an $\varepsilon$-close to $\varphi$ map $f:K\sqcup L\to\R^2$ such that $f(K)\cap f(L)=\emptyset$. We present open problems on this notion.
We introduce the van Kampen (or Hanani-Tutte) obstructions for these properties, as well as their generalizations to higher dimensions and to $r$-tuple intersections. We present the completeness result of this obstruction (D. Repov\v s and A. Skopenkov, 1998) and its algorithmic corollary.

 


 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!