[Facets-of-complexity] Invitation to two Monday Lectures May 30

[Günter Rote <rote@inf.fu-berlin.de>]

Our next Monday Lectures will take place on May 30,
in attendance, at 14:15 at FU Berlin. There will be TWO lectures.

_ATTENTION! Changed Location_

Hörsaal A
Institut für Mathematik
Arnimallee 22
14195 Berlin (across the street from the usual location)

_Time_: Monday, May 30, 2022 - 14:15

_First Lecture_: János Pach (Rényi Institute, Budapest)

_Title_: *Facets of Simplicity*

_Abstract_:
We discuss some notoriously hard combinatorial problems for large classes of graphs and 
hypergraphs arising in geometric, algebraic, and practical applications. These structures 
are of bounded complexity: they can be embedded in a bounded-dimensional space, or have 
small VC-dimension, or a short algebraic description. What are the advantages of low 
complexity? I will suggest a few possible answers to this question, and illustrate them 
with classical examples.

*_Coffee & Tea Break_: Inner yard of Arnimallee 22

_Time_: Monday, May 30 - 16:00

_Second Lecture_: Imre Bárány (Rényi Institute, Budapest)

_Title_: *Cells in the box and a hyperplane*

_Abstract_:
It is well known that a line can intersect at most 2n−1 cells of the n×n chessboard. What 
happens in higher dimensions: how many cells of the d-dimensional box [0,n]^d can a 
hyperplane intersect? We answer this question asymptotically. We also prove the integer 
analogue of the following fact. If K,L are convex bodies in R^d and K ⊂ L, then the 
surface area K is smaller than that of L. This is joint work with Péter Frankl.