Rade Živaljević

Topological methods in combinatorics and discrete geometry

R. Živaljević планирует провести 4 занятия.

Доступны 4 видеозаписи курса.

Topological methods can be with great success applied to problems of combinatorics and discrete (combinatorial) geometry. For some problems these are the only methods available. Here is an example.

Suppose we are given five red, five blue, and five white points in the three dimensional space (say 5 red, 5 blue and 5 white stars in the outer space). Then it is always possible to select 9 out of 15 given points (three in each color) and to form three triangles Δ1,Δ2,Δ3 (with vertices of different color) which have a non-empty intersection, 

Our lectures are organized around the so called Configuration Space/Test Map scheme (CS/TM for short) and we closely follow the exposition in Chapter 21 of the latest edition of the Handbook of Discrete and Computational Geometry (reference [1]). The CS/TM scheme is a two step procedure that can be summarized as follows:

Step 1. The problem should give us a clue how to define a «natural» configuration space X and how to rephrase the question in terms of zeros or coincidences of the associated test maps. Alternatively the problem may be divided into several subproblems, in which case one is often led to the question of when the solution subsets of X corresponding to the various subproblems have nonempty intersection.

Step 2. Standard topological techniques are used in the solution of the rephrased problem. The topological technique that is most frequently and consistently used in problems of discrete geometry is based on various forms of generalized Borsuk–Ulam theorems. However many other tools (Lusternik–Schnirelmann category, cup product, cup-length, intersection homology, etc.) have also found important applications.

The emphasis will be on Step 1 (construction of interesting configuration spaces) while the Step 2 provides a tool box which can be applied even without any previous exposure to algebraic topology. The selection of an appropriate configuration space is often the crux of the application of the CS/TM-scheme and the constructions may involve a variety of combinatorial and geometric ideas. Here are some examples.

  1. Alon's «spaces of partitions» (used in the proof of the «necklace-splitting theorem» (Theorem 21.4.3 in [1]), https://en.wikipedia.org/wiki/Necklace_splitting_problem
  2. Gromov's «spaces of partitions» (used in Gromov's proof of the Waist of the Sphere Theorem)
  3. Graph complexes and Kneser's conjecture http://mathworld.wolfram.com/KnesersConjecture.html
  4. Chessboard complexes (used in Tverberg type problems) as illustrated by our example about $15$ colored points in the $3$-space.

 

References

[1] R.T. Živaljević. Topological methods in discrete geometry. Chapter 21 in Handbook of Discrete and Computational Geometry (Third Edition), J.E. Goodman, J. O'Rourke, C.D. Tóth eds, CRC Press LLC. Preliminary version (January 2017),
http://www.csun.edu/~ctoth/Handbook/HDCG3.html
https://www.csun.edu/~ctoth/Handbook/chap21.pdf

[2] J. Matoušek. Using the Borsuk–Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry. Second edition, Universitext, Springer, Heidelberg, 2008.


Organization Committee e-mail:
dubna@mccme.ru