March 14, 2018 (Wednesday) at 10:00, Hanna Furmańczyk (University of Gdańsk)
“Equitable coloring of graphs – the basic model and some extensions”
Abstract.
A graph G is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one.
Since the model of equitable graph coloring has many practical applications (every time when we have to divide a system with binary conflict relations into equal or almost equal conflict-free subsystems we can model this situation by means of equitable graph coloring), it is well known in the literature and some new extensions have been appeared. For example, there is also known the concept of semi-equitable coloring. An n-vertex graph G has a semi-equitable k-coloring, if there exists a partition of its vertices into independent sets V1,…,Vk⊆V such that one of these subsets, say Vi, is of size ∉{⎣n/k⎦, ⎡n/k⎤}, and the remaining subgraph G-Vi is equitably (k-1)-colorable. Another possible extension/generalization of equitable coloring is r-equitable coloring. A graph G is r-equitably k-colorable, with r≥1 and k≥2, if there exists a partition of V into k independent sets V1,…,Vk such that ||Vi|-|Vj|| ≤ r for any i,j∈[k]. If r=1, we simply say that graph is equitably k-colorable.
In the talk we give some survey, mainly on equitable and semi-equitable coloring, with particular emphasis on the complexity of the problems, known algorithms and their application to task scheduling problems.
February 13, 2018 (Tuesday) at 15:00, Oliver Roche-Newton (RICAM, Linz)
“On the size of the set AA+A over the reals”
Abstract.
In the spirit of the Erdős-Szemerédi sum-product conjecture, it is widely believed that sets defined by a combination of additive and multiplicative operations on a finite set A are significantly larger in size than the original set. One of the first questions of this type that arises concerns the size of the set AA+A. This talk will discuss some new bounds for this problem.
January 31, 2018 (Wednesday) at 14:00, Alexey Balitskiy (MIT)
“Covering polygonal lines and Minkowski billiards”
Abstract.
We will start from the following elementary-looking question: Given a family of closed curves in Rd, what is the minimal volume of the convex body that can be translated in order to cover any given curve from the family? In general, this problem is very hard. The answer is not even known in the plane for the family of all curves of length 1. We will take a look at a few special cases, for which the answer is known. The question has applications for the study of billiards in normed spaces. I’ll describe some of them in elementary geometric terms.
