Speaker: Signe Lundqvist, Umeå University
14.15-15.00, MIT.B.372 MIT-building
Abstract: A geometric dominating set in an n by n grid is a set of points such that every grid point lies on a line defined by two points in the set. The geometric dominating set problem asks for the smallest geometric dominating set in an n by n-grid. We can also consider the same problem with the additional requirement that no three of the points in the set lie on a line. A geometric dominating set such that no three points lie on a line is said to be in general position.
This talk will follow a paper by Aichholzer, Eppstein and Hainzl, where the authors show both lower and upper bounds on the size of minimal geometric dominating sets in an n by n grid. Furthermore, the authors provide optimal geometric dominating sets in general position for grids of size up to 12 by 12. They also consider the same problem on the discrete torus, where they prove upper bounds on the size of geometric dominating sets.
Speaker: Joannes Vermant, Umeå university
15.15-16.00, MIT.B.372 MIT-building
Abstract: In this seminar I will go through the proof of a theorem from a paper of Balogh and Solymosi, in which some progress on the following question is made. Suppose we are given a set S of n points such that no four points are collinear. How small can the largest subset S’ of S which is in general position be? Balogh and Solymosi proved the upper bound of n^(5/6 + o(1)). The proof is based on the hypergraph container method.
