14 of May, 2013.

14:15 MA B1 524

Pham Thang (Ha Noi, Vietnam)

and Sum – Product estimates over finite rings Z

_{m}, where m is positive integer.

16 of July, 2013.

14:15 MA B1 524

Michael Hoffman (ETH Zurich)

Planar Packing of Binary Trees

In the graph packing problem we are given several graphs and have to map them

into a single host graph G such that each edge of G is used at most

once. Much research has been devoted to the packing of trees, especially to

the case where the host graph must be planar. More formally, the problem is:

Given any two trees T_{1} and T_{2} on n vertices, we want a simple planar

graph G on n vertices such that the edges of G can be colored with two

colors and the subgraph induced by the edges colored i is isomorphic to

T_{i}, for i in {1,2}.

A clear exception that must be made is the star tree which cannot be packed

together with any other tree. But a popular hypothesis states that this is the

only exception, and all other pairs of trees admit a planar packing.

I will present/sketch a proof of this conjecture for binary trees (maximum degree three), which

is joint work with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba Toth.

17 of July, 2013.

14:15 MA B1 524

Andrzej Grzesik (Jagiellonian University, Krakow)

Flag algebras in extremal graph problems

Flag algebras is a concept developed by Aleksander Razborov to formalize and unify several standard techniques of extremal combinatorics. They allow us to approximate densities of combinatorial structures in huge graphs by counting specific small substructures, so-called flags. In a typical application, a density problem is reduced to minimizing an appropriate linear operator. The latter can be highly computerized with the use of linear or semidefinite programming. The method turned out to be extremely powerful and led to solutions of quite a few long-standing problems. In this talk, I will present basic ideas and intuitions behind flag algebras, and show how to apply them to prove some old and new extremal graph-theoretic results.

Andrey Kupavskii (DCG)

Unit distance graphs

A complete (unit) distance graph in *R*^{d}^{ }is a graph whose set of vertices is a finite subset of the *d*-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph in *R** ^{d}* is any subgraph of such a graph. We show that for any fixed

*d*the number of complete distance graphs in

*R**on n labelled vertices is $2*

^{d}^{(1+o(1)) d n \log_2 n}, and give a short proof of the known fact that the number of distance graphs in

*R**on n labelled vertices is 2*

^{d}^{(1-1/\lfloor d/2\rfloor +o(1))n^2/2}. We will also study several other extremal problems involving distance graphs. (Joint work with Noga Alon)

8 of October, 2013.

The union of any $n$ arithmetic progressions, each of length $n$, with

pairwise distinct differences must consist of at least

$c(ε)n

*elements.*

^{2-ε}can observe n arithmetic progressions, each of length n, with pairwise

distinct differences such that the cardinality of their union is o(n

*).*

^{2}We develop some number theoretical tools that are of independent interest.

In particular we give almost tight bounds on the following question: Given

n distinct integers a

_{1},…,a

_{n}at most how many pairs satisfy

aj/ai in [n]$? More tight bounds on natural related problems

This is a joint work with Shoni Gilboa.

We prove that for any positive integer k, every finite set of points

in R^3 can be colored with k colors so that every

translate of the negative octant containing at least k^6 points

contains at least one point of each color. The best previously known

bound was doubly exponential in k. This yields, among other

corollaries, the first polynomial bound for the decomposability of

multiple covers by homothetic triangles. We also investigate related

decomposition problems involving intervals appearing on a line.

This is joint work with Jean Cardinal, Piotr Micek, and

Torsten Ueckerdt.